Finding Local 2D Neighborhood of Navmesh

As part of my quest to move the multi-agent navigation to Detour I have been testing a little how to find local 2D neighbour of a navmesh. The method should answer the question that given a point on the navmesh and certain small radius, what are the potential navmesh edges to avoid. Since the Detour navmesh is sort of 2.5D structure, it is possible that the returned polygons may curl over itself close to bridge like structures.

My initial idea was to find visibility polygon from a single source point, but practical implementations are prone to the usual floating point accuracy issues, plus you would need to do that query every time an agent moves, which has the potential to become the bottleneck of the whole local avoidance.

Instead, I though I'd try to find a good way to eliminate the polygons which cause the problems. Finding the nearest polygons is simple using dtNavMesh.findPolysAroundCircle(), finding overlapping polygons is quick using SAT. But in case of overlap which polygon to keep?

One interesting feature of findPolysAroundCircle() function is that it returns the polygons from nearest distance to the furthest. Under the hood the method uses Dijkstra to find the polygons around. The method was designed to return the most relevant information up to the buffer limit the caller passes.

Since we have this information around, we can make the polygon culling so that if two polygons overlap, the latter–or furthest from the current location—polygon is always removed. So depending on situation the most irrelevant polygon is removed.

This seems to work great in practice as you can see from the image at the top of the post. If the start location is close to the ground plane, the ground polygons are chosen the the bridge is culled and vice versa.

Below is the code that I used for testing. The function arePolysNeighbour(), which check if there is a link from the first poly to the next poly, since they are two convex polygons, they cannot overlap if they are neighbours. The function testPolyCollision() does 2D poly-poly SAT collision check on XZ-plane.

float pa[DT_VERTS_PER_POLYGON*3];
float pb[DT_VERTS_PER_POLYGON*3];
npolys = m_navMesh->findPolysAroundCircle(startRef, startPos, radius, &filter, polys, m_parent, 0, MAX_POLYS);
for (int i = 0; i < npolys; ++i)
{
   bool valid = true;
   const int npa = getPolyVerts(m_navMesh, polys[i], pa);
   for (int j = 0; j < i; ++j)
   {
       if (arePolysNeighbour(m_navMesh, polys[i], polys[j]))
           continue;
       const int npb = getPolyVerts(m_navMesh, polys[j], pb);
       if (testPolyCollision(pa,npa, pb,npb))
       {
           valid = false;
           break;
       }
   }
   polyflag[i] = valid;
}

I'm a little worried about the performance, but it is not necessary to update the neighbourhood every tick, so several optimization methods may apply. I have to do some more testing, whether there are some corner cases which are not yet handled using the code. And I will need to check the performance more in detail too.

All in all, I think I have pretty much all the ingredients to build multi-agent navigation for Detour. The rest is just API design and hard work :)