The library is actually two libraries. Recast is the section that deals with generating a navigation mesh, and Detour is the section that deals with finding a path on a navmesh.
The way Recast works, basically, is that it creates a large voxel array that subdivides your pathfinding space into arbitrarily-sized cells. You specify the parameters such as cell size and world size to guide the construction of the voxel array. Once the voxel mesh is created, you can begin rasterizing polygons into the array, using basic rasterize triangle calls. Polygons can be rasterized and flagged Walkable, Non-walkable, etc...
Other parameters that are specifiable include Agent Radius (which should be a close median radius for all the agents that use the navmesh; agents significantly larger than the median should use a different navmesh, built using a larger median radius). Agent Radius triggers the shrinkage of the rasterized navigation polygons in order to account for the radius of an actor. If the actor stays within the region of the navmesh polygons, then it will not collide with any walls. You can also specify a Maximum Step Up (max climb) that determines the maximum number of navmesh cells that an agent can climb up or step up on. This parameter controls the creation of ledges and such, which the agent can not climb up on. You also specify the minimum slope that is climbable by agents; anything greater in slope than this minimum is flagged as unwalkable.
There are also parameters which control the navmesh creation, such as maximum number of verts per polygon, area merge parameters, etc... These can all be tweaked as needed.
Recast allows navmeshes to be created in chunks, or tiles. The whole navmesh is represented as a collection of tiles, and tiles can be added in and taken out at will in order to incorporate such features as stream-loading of levels, etc...
Once the polygons are rasterized, a sequence of processing steps takes place, involving condensing the voxel array into a smaller, more compressed chunk, then peeling off regions and adding them to the nav mesh. There are a number of parameters guiding this process. The end result of the process are two meshes: the Navmesh and the Detail Mesh.
The navmesh, of course, is a mesh of walkable, connected polygons representing the path search space. The detail mesh is a more highly detailed mesh that corresponds to the navmesh, and can be used for obtaining more accurate locations and tests against the terrain. For example, you can call a function to obtain the closest point on the navmesh to another point, and the detail mesh will ensure that this location is fairly accurate, since the navmesh itself is relatively low resolution.
Once the path mesh and detail mesh are created, they can be saved or stored, to be loaded later by Detour. (Or, they can be handed directly to Detour, if the navmesh generation is done as a preprocessing step).
Detour allows some interesting operations. You can query detour as described above, to find the point on the navmesh nearest to a given point in world space, good for placing or spawning objects into the world to ensure that they are spawned on the mesh.
You can, of course, generate a path from one location to another. This is a multi-part process. The first stage involves finding the chain of polygons that must be traversed to get from Start to End. This is a very fast operation that does a graph search of connected polys, and fills a passed array with polygons. The search can be given a maximum polys count so that it will only find N polys in the path, useful for limiting large searches or keeping searches of large length from overrunning the path array.
You can also generate a straight path using the poly path obtained in the previous step. The point path is simply a list of straight-line points or locations the actor must travel to in sequence to get from Start to End, and represents the straightest path to follow.
While it is easy to obtain entire paths for unit navigation, Detour also supports partial path queries in order to implement what is called a "navigation loop." If an actor is trying to follow a "moving target", then it can be a waste of resources to constantly generate the entire straight line path, only to have to recreate it when the target moves. By doing a partial query instead, you perform a much faster path search that will only generate the first straight-line point to which you must path in order to draw nearer your target. This way, you only "look ahead" one step, so you can more efficiently track a moving target without the overhead of a full path search.
The library has support for what are called off-mesh connections. These are things such as teleporters, elevaters, area transitions, and so forth, that connect disconnected navmeshes together, and path searching will handle off-mesh connections easily.
The library is in active development; currently, the author is experimenting with crowd behaviors and the like. I found the library to be quite handy, and once I figured it out from perusing the sample app (given the lack of comprehensive documentation) I was literally able to just drop it in to my existing library of stuffs, write a thin wrapper class to abstract out some of the gritty details, and replace my old grid-based A* in the space of a couple hours.
I'm still working on the techniques I promised in the last post. Next episode: more shiny screenshots!
Thanks for a great read!