Pretty much title. How do I get a random position inside a given polygin to spawn something?
I think for a polygon, especially if it’s potentially not convex, you’re going to have to do some custom coding. If you were just using a CollisionShape then it’s underlying Shape2D resource has a get_rect() method which returns a Rect2 object indicating its size; you could then just use randf to generate x and y values within that size to make a vector 2 and add it to the CollisionShape’s position.
But off the top of my head, I don’t see a clean way to get something within a CollisionPolygon. Here’s one thought for custom code: If the position of the collisionpolygon is the center of the actual polygon shape and you also have a clean line from the center to any point on the boundary (such as when it is convex), then you can use that as an origin, and select a random angle from 0 to 2*pi. Then I think you could ray cast from that point with parameters set to raycast from inside allowed (which I think is a thing?) to find the distance to the edge. Then select a random number from 0 to that distance. Now you have a unique point in your shape given in polar coordinates (angle and distance from center). Use the polar to cartesian formula to get x,y coordinates relative to the position of the CollisionPolygon.
Here is a pure GDScript implementation. Maybe we can get this added to the engine!
I was looking at your code in that proposal and I have a few questions.
Geometry2D.triangulate_polygon() already builds an array of triangles.
Could you not just pick one of those (start at a random index in the returned array) and return a point in that?
It looks like you are giving the larger triangles better odds of being selected. Is this the only reason to rebuild a triangles array?
I wonder if the original call to Geometry2D.triangulate_polygon is even necessary; if it could be short circuited by a triangle built on a random point of the polygon?
@sancho2 The algorithm goes like this:
- Triangulate the polygon
- Select a random triangle, proportionally to it’s size
- Select a random point within that triangle
Could you not just pick one of those (start at a random index in the returned array) and return a point in that?
That would give extra weight to the small triangles. Imagine some polygon that was triangulated into two triangles: A) at 10% and B) at 90%.
If you pick between the two triangles randomly, then the smaller triangle would be over represented.
It looks like you are giving the larger triangles better odds of being selected.
In fact, I am doing the opposite of this. By selecting a triangle propotionally to it’s weight, I can ensure that "large"triangles get more points. It results in a uniform point sampling across the whole polygon.
I wonder if the original call to Geometry2D.triangulate_polygon is even necessary
I provide two versions of the API, because triangulating polygons is expensive. By supplying the version that takes in a pre-triangulated polygon, I can allow external callers to cache the triangulated polygon themself, and skip an expensive step.