Introduction

What is a Navmesh and how does it work?

Most modern, complex 3D games rely on navmeshes to drive their pathfinding and AI agent movement and navigation.

A navmesh is a simplified view of the traversable area of a game world, optimized for AI pathfiding and movement calculations. Navmeshes are usually built from the physics colliders of the world, since they define the areas an AI can legally exist.

Triangles in a navmesh represent nodes in the pathfinding graph, and edges between adjacent polygons define connections between these nodes. Pathfinding queries first construct a path consisting of a strip of adjacent polygons. This represents the "corridor" of space that leads the agent to their goal. That polygonal path is refined into sequence of line-segments through a string-pulling algorithm. Agents can then follow this sequence of waypoints to reach their goal.

Agent Attributes

A navmesh is usually tailored to a specific type of AI agent with a specific size and set of movement capabilities. After all, the areas that a huge ogre, or a medium human, or a tiny mouse can move in are very different. Because of this, it's often necessary to build multiple navmeshes for the same environment to accommodate different agent types.

AI size is the most important attribute and is defined in Recast as a radius and height. You can think of these values as representing either a cylinder or a capsule.

A maximum slope value defines the steepest angle geometry a character can walk. This helps ensure it doesn't try to walk up or down steep cliffs.

Finally, a maximum "step up" height defines the highest obstacle an AI agent can step up. This helps Recast know that an AI shouldn't get stuck thinking it can't step over a small curb or up a flight of stairs.

What is a Navmesh not?

While a navmesh is a simplified version of a world's collision geometry, it is solving a fundamentally different problem. Very often, navmesh generation will sacrifice some accuracy in favor of geometry simplification. With navmesh pathfinding in games, it's more often than not better to have faster, slightly less accurate queries, than extremely-precise optimal paths.

For these reasons you should not use the navmesh or paths generated by the navmesh as collision geometry or animation splines. Detour provides an AI movement controller that demonstrates how path-following should work with the paths generated by navmesh path queries.

What is Recast Navigation?

Recast is a set of tools for fully automating the navmesh building process, loading and streaming navmesh data, pathfidning and querying navmeshes at runtime, controlling AI agent movement, and more. It was originally created by Mikko Mononen in 2009 and has shipped in countless indie games, AAA titles, and commercial and open-source game engines such as Unity, Unreal, Godot, and O3DE.

Recast is roughly divided into two parts. "Recast" is the process that automates the navmesh building process, and is what most games and game engines use. "Detour" is the set of runtime systems for working with navmesh data, performing path queries, and controlling agent movement.

High-level overview of the Recast Navmesh-Building Process

Recast builds navmeshes utilizing an mesh rasterization process. This process takes your input geometry, converts it to voxels, performs transformations to refine and filter the voxel data, and then re-triangulates voxels into an output navmesh. This has a number of benefits:

• Robustly handles large amounts of overlapping geometry, small triangles, and imperfect geometry.
• Allows for large amounts of customization and specialization of the navigation data. Recasts's process allows you to hook in your own code for things like automated cover-point generation.
• Clear, fine-grained performance/quality tradeoff. By modifying the rasterization voxel size, it's possible to significantly alter the generation time and quality of the resulting navmesh to suit specific workflow or budget needs.
• Issues with navmesh generation are easy to debug and visualize as voxels, rather than large sets of complex geometry.
• The voxelization process allows for straightforward mesh re-building and streaming.

Recast showcases two approaches to building navmeshes in the "RecastDemo" project.

Sample_SoloMesh.cpp shows the basics of building a single navmesh for a small game world. This process is the simplest version of working with Recast. The build process is outlined in Sample_SoloMesh::handleBuild, but essentially breaks down to calling the following functions:

// Figure out how big the raster voxel grid will be based on the input geometry bounds.
rcCalcGridSize
 
// Voxelize the input geometry
rcAllocHeightfield
rcCreateHeightfield
rcMarkWalkableTriangles
rcRasterizeTriangles
 
// Clean up the voxel data and filter out non-walkable areas.
rcFilterLowHangingWalkableObstacles
rcFilterLedgeSpans
rcFilterWalkableLowHeightSpans
 
// Consolidate the voxel data into a more compact representation
rcAllocCompactHeightfield
rcBuildCompactHeightfield
 
// Further refine the voxel representation
rcErodeWalkableArea
rcBuildDistanceField
rcBuildRegions
 
// Triangulate the navmesh polygons from the voxel data
rcAllocContourSet
rcBuildContours
rcAllocPolyMesh
rcBuildPolyMesh
 
// Package the mesh with additional metadata that's useful at runtime.
rcAllocPolyMeshDetail
rcBuildPolyMeshDetail
 
// Cleanup
rcFreeHeightField
rcFreeCompactHeightfield
rcFreeContourSet