Choosing random location on navmesh

I added two methods to generate random points on navmesh to Detour. The first method generates random points anywhere in the mesh based on query filter, and the second method generates random points around a specified location. The first one is good for choosing just some random location, and the second one is good for finding a location which is guaranteed to be connected to the start location.

dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius, const dtQueryFilter* filter, float (*frand)(), dtPolyRef* randomRef, float* randomPt) const;

There were two tricky parts on choosing a good random location. The first was how to make sure that the random samples are more or less uniform, that is, the area of a polygon needs to be considered. Secondly, the filters and off-mesh connections make picking random polygon quite hard.

In general the filtering can be used to prevent generating random points in disabled areas, but you can also mark certain areas (i.e. spawn locations) and restrict the point generation only to those locations using filter flags.

I wanted to avoid allocations, so I started to look for a "streaming" random selection algorithm. The solution turned out to be Reservoir Sampling. I modified it a bit to make it consider the area of a polygon.

Area weighted reservoir sampling looks something like this:

poly = nil
areaSum = 0.0
foreach p in polygons {
    area = p.area()
    areaSum += area
    if (frand()*areaSum <= area) {
        poly = p
    }
}

Where frand() returns a random number in range [0..1). The basic idea is that each polygon is chosen at decreasing probability relative to the polygon area.

The good thing is that this algorithm works great in practice, the bad thing is that it is a bit slow. It needs to visit all polygons and calculate their area. This could be sped up by caching the calculations, but different filter types make this quite cumbersome in practice.

The code was committed in R331.