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 :)

Finding Navmesh Polygons Touching a Convex Shape

I added new query method to dtNavMesh to find polygons which touch a convex shape, findPolysAroundShape().

The function is similar to findPolysAround(), but with different boundary condition. As a matter of fact, I also renamed the findPolysAround() to findPolysAroundCircle() to make it less confusing. The function can be useful for creating some gameplay features such as doors.

The new method is somewhat slower than findPolysAroundCircle() because it uses polygon-segment intersection test to see if an edge should be visited.

Available in R186.

Constrained Movement Along Navmesh pt. 3

The most boring topic of the year makes a comeback! I have been struggling a bit to make robust movement along navigation mesh, but I think I finally nailed it.

Why should you care?

The basis of solid navigation loop is good collision handling. For navigation meshes this means a way to handle movement along connected graph of convex polygons. That is, how to move from one polygon to another and how to handle the case when the desired move collides with blocking navigation mesh edge.

The method should also return the polygons it walked through during the movement. This is used to fixup the path corridor so that on next update we have valid path to follow again.

First idea: Raycast

My very first implementation of movement code used raycasts. I used similar iterative code as the good 'ol ellipsoid vs. trimesh collision detection. The problem with that solution was that the rays end up being parallel to the polygon edges when sliding or hit vertices when aiming for next corner. I ended up running into a lot of floating point accuracy errors and quite interesting special case hacks to get rid of them.

Second idea: Point in Polygon

My second attempt changed the whole idea upside down. I can calculate the sliding movement inside a convex polygon by clamping the target point to be the nearest point in the polygon. To handle the connected graph of convex polygons (like navmesh) we can check if the nearest point would lie on an edge which leads to neighbor polygon, and follow that until the goal polygon has been found.

While the basic idea is sound, here area a couple of cases where it does not produce desired result. Firstly there are some corner cases where it will miss potential move to neighbour polygon because it does not check visibility (see my previous post). Interestingly this is not a problem when using triangles.

Second, nasty problem is that it does not handle well the case that the nearest point is at a polygon vertex. In this case either edge are equally good candidate to follow and I could not find goo heuristic which would handle all the corner cases I had in mind.

This method is a bit similar to the jump-and-walk algorithm which is used to locate triangles in triangulation. It is known to work on triangulations which have convex boundary.

Third idea: Search

This idea extends the previous by making it breath first search instead of iterative loop. That nicely solves the problem of trying to choose good branching at each iteration, all branches are followed instead.

The search expands to all edges which touch circle containing the start and goal location (start+delta). The search is stopped when the goal polygon is found or no more polygons can be visited. In case the goal is inside a polygon, the goal location is accepted, else the nearest point to all visited blocked polygon edges is chosen.

In pseudo code it looks something like this:

// Applies constrained movement from startPos to goalPos.
// The result is stored in clampedPos.
// Returns number of visited polygons.
int Navmesh::navmeshMoveAlong(Vec3 startPos, PolyRef startRef, Vec3 goalPos,
               PolyRef* visited, Vec3& clampedPos)
{
   Stack stack(16);          // Tiny stack
   ClosedList closed(32);    // Tiny closed list
   Vec3 bestPos, p;
   float bestDist = FLT_MAX, d;
   PolyRef bestRef = UNDEF;   
   // Search constraint
   Vec3 searchPos = (startPos+goalPos)/2;
   const float searchRadius = vdist(startPos,goalPos)/2;
    // Init
    bestp = start;
   stack.push(startRef);
   closed.add(startRef,startRef); // Self ref, start maker.

   while (!stack.empty())
   {
        // Pop front.
        PolyRef cur = stack.pop();
       Poly* poly = getPoly(cur);
       // If target is inside the poly, stop search.
       if (pointInPoly(goalPos, poly))
       {
           bestRef = cur;
           bestPos = goalPos;
           break;
       }
        // Follow edges or keep track of nearest point on blocking edge.
        for (int i=0, j=poly->nv; i<poly->nv; j=i++)
       {
           const PolyRef neiRef = poly->nei[j];
           const Vec3& sp = getVertex(poly->v[j]);
           const Vec3& sq = getVertex(poly->v[i]);
          
           if (neiRef == UNDEF)
           {
                // Blocked edge, calc distance.
                p = closestPtPtSeg(goalPos, sp,sq);
               d = vdist(p,goalPos);
               if (d < bestd)
               {
                    // Update nearest distance.
                    bestPos = p;
                   bestDist = d;
                   bestRef = cur;
               }
           }
           else
           {
                // Skip already visited.
                if (closed.find(neiRef)) continue;
                // Store to closed with parent for trace back.
                closed.add(neiRef,cur);
                // Non-blocked edge, follow if within search radius.
                p = closestPtPtSeg(searchPos, sp,sq);
               d = vdist(p, searchPos);
               if (d <= searchRadius)
                   stack.push(neiRef);
           }
       }
   }
    // Trace back and store visited polygons.
    followVisited(bestRef,visited,closed);
    // Store best movement position.
    clampedPos = bestPos;
    // Return number of visited polys.
    return visited.size();
}

So it is a tiny special case pathfinder. The result is movement which can quite liberally move along the navmesh and if it encounters walls it will slide. The slack is necessary when you need to shortcut a little for example when very close to the next corner along the path.

The code above is meant to perform well when you do really small increments. It aims to be faster than regular pathfinder which is tuned to perform well with potentially thousands of nodes.

For such local case you may maintain the open list (stack) and closed lists using simple arrays. There are many cases in the code which may trash your cache (accessing the navmesh data), but by using small arrays for open and closed lists you can avoid some of it. Since we expect the lists to be small, we can potentially use simple linear searches which simplifies the code.

Next Step

My next task is to figure out nice way to calculate 2D local collision environment from 2.5D navmesh. This is to be used with velocity obstacles. Then I should be ready move on porting the VO code to Detour.

Recast Area Types Per Triangle

I just committed a change (R185) which allows you to pass area type per triangle for rasterization.

API Changes

From Flags to Areas

Firstly, the flags are now gone from the rasterization functions and area type is used instead. Now same concept of marking things walkable or not is used throughout the pipeline.

If you want to make a triangle non-passable, use area type of RC_NULL_AREA. If you don't care about area types at all, you should use general RC_WALKABLE_AREA.

rcMarkWalkableTriangles() uses that area type that to keep the existing behavior. I also added rcClearUnwalkableTriangles() which does the opposite, that is sets the area types of a triangle to RC_NULL_AREA if the triangle slope is too steep. Handy if you have an array of area types to start with.

The change to the rasterize methods is minimal, instead of passing a flags now you pass an area type.

Compacting Heightfield

When the heightfield is processed to compact heightfield, there used to be a flag parameter. This is gone now, so flags parameter from rcGetHeightFieldSpanCount() and rcBuildCompactHeightfield() are omitted now. Every voxel that has are type other than RC_NULL_AREA will be included in the span count as well as in the compact heightfield.

Filtering

The area eroding function used to have a trace of some old ideas of mine which required you to pass area type to it. The area type is removed now. I changed the function name to rcErodeWalkableArea() to better reflect what it is actually doing.

Aliasing

The new feature comes with a new set of problems. One problem is aliasing. In many ways voxelization works the same way as z-buffer. When surfaces are intersecting each other at low angle or almost parallel we will get aliasing error usually referred as "z-fighting".

This can cause nasty noise at the boundaries of different types of areas. One simple way to fight this is to apply media filter to remove the speckles. I have added rcMedianFilterWalkableArea() just for that.

Median filtering will smooth things out a bit, so if you want to keep as sharp as possible outlines for rcMarkConvexPolyArea() you may want to apply the filtering before you mark the areas. Otherwise I recommend to apply the filtering just before you build the distance field and build regions.

Median filtering is not super expensive, but not free either. On average add 1-2% to the generation time (that is, 10ms on 1000ms generation process).

Accuracy

In order to not to increase the memory footprint of voxelization process, I took some bits from the height range and moved them to the area types in rcSpan structure. This basically reduces the height range from 32k to 8k.

For majority of the users this is fine. One of my test levels which goes 6 stories above and below the ground uses max height of 1450 (human sized character, cell height 0.2).

If you run out of bits there, you can adjust the bits in rcSpan struct (remember to also change RC_SPAN_HEIGHT_BITS). This is likely to increase the rcSpan size from 8 bytes to 12 bytes (on 32 bit machines) and that will reflect in memory consumption.


Sorry for the API breakage, but I hope this will make things more flexible for many people!

Sumo vs. Ninja

Steering Behaviors is interesting method to create life-like behaviors for agents. It is tempting to use it for local avoidance. It is simple and intuitive to understand, but it comes with one really fatal drawback. When it breaks–and it will–it is eventually impossible to tune to get the desired behavior.

Velocity based collision avoidance methods on the other hand are a bit harder to get up and running, but get past the point where steering behavior based local avoidance fails. They sure come with their own share of problems too, like all sorts of jittering and feedback effects. But those problems are manageable and tunable to greater depth than anything based steering behaviors.

One way to look at describe the difference between these two methods is that steering behaviors based avoidance is basically a sumo-suit your character wears. As you bump into something, you are gradually pushed away. But when things get tight, you get stuck, and just tumble around.

One the other hand you want your characters to be suave like ninja, slipping through even the tightest of all encounters.

Eventually you want the agents to be as forward looking as an octopus, so that they can plan their avoidance velocities even better.

Custom Memory Allocator for Recast and Detour pt. 2

Ok, the update of the last post got kind out of hands. I did not expect to get this all done today.

The custom memory allocator for both Recast and Detour are submitted in R178 in SVN. The latest update also fixes the Visual Studio project and one array allocation bug which surfaced in VC.

As highlighted in the previous post, the API has changed on how the objects are required to be constructed. There is now alloc and free functions for each object (dtNavMesh, rcHeightField, etc). I used the same pattern all over the place, so it should be easy to spot.

[EDIT] Few more bugs were still there. Folks living at the SVN edge, please try R183.

Custom Memory Allocator for Detour

I just checked in custom memory allocator code for Detour (R176, or once googlecode stops giving me error 500).

I opted for similar method that is used by other open source libraries such as Bullet Physics or Box 2D. I initially wanted to use an interface which would be passed to each of the allocation functions, but the implementation became really ugly and confusing for those who don't care about it.

If you have a strong case why it should not be handled that way and have good example how to do it better (or pointer to some lib which does it great) let me know.

Thanks to Cameron Hart for initial patch and discussion.

I really don't like how C++ handles memory allocation. It is so half heartedly build into the language. Even the standard library has its' own way of circumventing it.

I'm planning to give the same treatment to Recast too soon.

[EDIT] Added similar support for Recast in R177.

NOTE: From now on the Recast objects (i.e. rcHeightField, rcPolyMesh etc) are required to be allocated and freed using special functions (rcAllocHeightfield() and rcFreeHeightField() respectively). The samples are up to date, in case of confusion check them out.

My Paris Game AI Conference Presentation

I have now successfully vacated my vacation, purged the most urgent work related queue, and finally got some time to clean up the "slides" from my AIGD10 presentation. Without further due, here's link to the presentation code and executables for Windows and OSX:

• AIGD10_MikkoMononen_NavLoop.zip

Use right mouse button to navigate the presentation. Some of the diagrams are interactive, I have included some usage notes below them. It is not meant to be intuitive, just a quickly hacked version of what I hope powerpoint would be :)

The code is quite ugly at points and probably not as efficient as you might like. I have tried to make comments around the important chunks of code where things need improvement. I left some things unoptimized for the sake of readability.

I'm still wondering what might be the best way to transcript the presentation. Here's quick overview of the navigation loop idea.

Navigation Loop

The idea of navigation loop is to cover all the things from A* to velocity selection which are needed to make character move in the world. One of the main goals was to make the agent movement as flexible as possible so that you can concentrate on movement styles or even multi-agent navigation instead of focusing all your energy to try to stay on path (that naked tight rope dancer is that).

Your system will get horribly, horribly, horribly convoluted when you try to follow (linear) spline path and especially when you mix and match collision representations!

The path to the goal is represented all the time as linear array of connected polygons. We never find straight string pulled path to the goal location. This linear array of polygons is found before we start to move the character. You can use your favorite search method to do that. It probably will be A*, I use breath first search in the demo.

Foreach (Simulation Step) {

At each simulation step you first calculate the next corner to move to. This can be implemented efficiently using the Funnel Algorithm. Instead of trying to stay on path, we can always query the next sub-goal towards the target using Funnel Algorithm.

The next step is to apply steering. The demo contain a couple of different styles from robotic straight path moving, to smooth path movement to drunken movement.

The next step is to move the agent. This is done so that the agent is always constrained to the navmesh. The result from this movement step is a linear array of polygons that we visited through when we moved the agent [1].

As final step is to finally fix up the corridor based on the visited array. Most of the time this fix up will shrink the path corridor, but in case the movement lead the character outside the corridor, new polygons will be added in the beginning of the array.

The result of this loop is that no matter how we steer, we are always able to query the next subgoal. If the steering is not totally stupid, the agent will reach the target with certain probability.

Later in the presentation you can find how to extend the loop to contain velocity planning stage.

Data Dependancies

The navigation loop idea assumes certain things about the data. The dynamic obstacles are always assumed to be traversable in one way or another. The system tries its' best to resolve collision conflicts, but in certain cases you need to detect dead-locks and figure alternative ways to handle them, i.e. disable collisions or use special animations to switch places.

The local velocity planning cannot deal with local minima (pockets, U-shapes, etc). If you have larger or more complicated obstacles they need to represented in the navigation graph.

Conclusion

I'd like to thanks David Miles and Thomas Young for laying down the ground work on their earlier articles and talks. I have not seen similar complete system represented before, but I don't claim it to be particularly unique. Such holistic systems as quite common in motion planning literature.

The sort of "anti-points" of this presentation were: 1) A* != navigation, 2) (Linear)Spline is horrible representation of a path. Unfortunately I know that the old fragments of wisdom on navigation will stick with us for years to come .

___

[1] I have blogged a couple of times about constrained movement along navigation meshes. I think the idea is sound, but I'm still figuring out a couple of implementation details.

Firstly, the idea works really when on triangles, but not so well on polys.

Secondly there are certain cases where the demo implementation fails when the next clamped location is at a vertex and both of the neighbour edges are valid exit edges. Need to have better heuristic for this. The system is always able to resolve this the next update, but it is annoying nonetheless.