Spawn points don't guarantee distribution

[Erik Ogenvik]

When spawning into a spawn point, the entity should be placed within a random place within the are use by the spawn point.

The main issue is however that since there's no good way to get a random position within an arbitrary WFMath shape, the code has to use a more naive solution whereby it tries to generate a random position ten times, and check if any of these positions are contained within the shape.

For the path that the settlers are set to use this will in almost all cases fail (since the 2d box area of the path is way much larger than the area itself). The result is that settlers pretty much always are created at the same position.

Fixing this is non trivial. It would be possible to use a better way of generating a random position within the area, but that depends on WFMath having methods through which we could get the location of a collision (i.e. we could probe the area with lines or vectors from different directions to better figure out where to place the entity). Such methods are however lacking, and I don't foresee us having the resources to put any work into adding such methods.
One option further on is to revisit this issue if and when we decide to replace WFMath with a math library which is more actively maintained, and provide at least the same features, and more.

Another option would be to not use a shape such as the rather elongated path, instead defining something more square as the spawn point.

[Al Riddoch (alriddoch)]

I have suddenly worked out why some of my spawn locations are so confusing. I didn't realise that the spawn area was defined by such a long, odd shaped area.

Obviously an immediate fix in the default world would be to switch to something with a more reasonable shape, but I'd also like to create a general solution that does allow for this. The "try ten times, and hope to eventually get an intersect" algorithm never felt right, but I had to get it done before my 6 month sabatical, and six months later I'd forgotten about it.

[Erik Ogenvik (erik-ogenvik)]

The world defined in https://github.com/worldforge/worlds/tree/master/mason/island has a more circular "landing area". I've also put some thought into having the landing area more game play friendly. Now, I haven't really done any work on that world in quite a time. Mainly because I've been preoccupied with other WF work.

[Erik Ogenvik (erik-ogenvik)]

Given any polygon there are ways of picking a random position within it. Usually by decomposing the polygon into triangles.
We shouldn't need to reinvent the wheel here; this might help. http://www.cgal.org/