Sunday, February 26, 2012

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.

7 comments:

  1. Mikko, I'm really excited to see this new feature. I have needed to generate uniform random locations on the mesh for dynamic spawning of AI and assigning destinations. I've taken the approach of volumetric random sampling and then testing for a "hit" on the nav mesh - which is very inefficient for sparse meshes, if you want don't want to bias towards edges. In a GTA-like situation, those cycles really add up! An area-aware sample generator did seem to be required and with the overheads involved, a reservoir of samples had occurred to me too.
    I look forward to trying this out and ditching my slow code!

    ReplyDelete
  2. Wait, I see.. Reservoir sampling is not what I assumed, it's a clever bit of math. Nice find!

    ReplyDelete
  3. This question probably doesn't belong here, but I didn't know how else to reach you.

    I've been using Recast for the pathfinding of an upcoming game at my company, and we are currently dealing with the issue of destructible objects. We feed the objects in as areas for recast to avoid, but when they are destroyed, that leaves us with a situation of either needing to re-run Recast or have a non-navigable area where the building used to be.

    We currently have Unity calling an altered Recast program that takes arguments and loads certain settings, but we don't change the functionality behind the main function at all.

    What I would like is a way to feed the Recast functionality with a list of vertices (and even borders between vertices if possible) that have to be in the final mesh. This would allow us to grab those triangles once we are in the game and mark the borders in our engine as non-crossable during pathfinding.

    Our current top idea for going around this is to no longer mark out buildings as non-navigable area and instead run a function that divides the polygons under it into an area that guarantees, no matter how many times it has to divide and recombine, that we have a square area beneath the building that we can grab and make non-crossable. This obviously is vastly inefficient in comparison with the functionality I described above.

    Is there any chance Recast has an ability like the one I described? If not, is there any chance of it coming in a future build?

    ReplyDelete
  4. There's relatively active Recast discussion group at:
    http://groups.google.com/group/recastnavigation

    Have you looked into the area marking code? It allows you to "bake" areas in the navmesh. There is a convex area tool in the RecastDemo which allows you to play with the feature.

    ReplyDelete
  5. https://plus.google.com/photos/107009077626886918062/albums/5732481485109385313?authkey=CIHhkJ6w4-L1jQE

    This is a test I did with the "Create Convex Volumes" system within the Recast demo. My first concern is that it seems to have a random chance of creating something similar to the shape of the convex volume instead of being strict as I would have hoped.

    My other concern is that while this test seemed to successfully create separate polygons for each convex volume even when they were close, I am not sure if that is guaranteed by the functionality. Since we are looking to have a lot of destructible objects near each other, I want to ensure that the area that Recast marks off for them is specifically for the individual object on that area, and not a polygon shared between two objects that were close to each other. Could you confirm this either way?

    ReplyDelete
  6. Actually, I just confirmed that it isn't guaranteed to create separate polygons for each volume, which changes my question. Is there an option in your code to make it guarantee a separate polygon list for each convex volume places in the map?

    NOTE: The second picture, the volumes at the bottom left of the image are close enough that you can see the triangle at the bottom left is shard between them.

    https://plus.google.com/photos/107009077626886918062/albums/5732481485109385313?authkey=CIHhkJ6w4-L1jQE

    ReplyDelete
  7. I continued the discussion at Recat forums:
    http://groups.google.com/group/recastnavigation/browse_thread/thread/457d3b153b7c2e96

    ReplyDelete