Summary
A navigation mesh (navmesh) represents walkable space as a set of convex polygons (or polyhedra in 3D) connected in a topological graph. Agents pathfind across this graph then move freely within each polygon at any angle, combining the planning efficiency of a sparse graph with the movement freedom of continuous space. This page covers how navmeshes are constructed — from raw geometry to a queryable data structure — including Unity’s Recast-based system and advanced precomputed variants.
(Hale and Youngblood, Game AI Pro 360, Ch. 3; Gravot, Yokoyama, and Miyake, Ch. 4; see source-game-ai-pro-360-movement-pathfinding)
Key ideas
A navmesh provides:
- Planning — A* across polygon nodes is fast because a large world may need only hundreds of polygons rather than millions of grid cells.
- Smooth movement — agents are free to walk at any angle within and across polygons; combined with the funnel algorithm this produces natural paths.
- Accurate world representation — non-axis-aligned walls, slopes, and organic shapes are represented precisely.
- Localisation — given an agent’s world position, a point-in-polygon test identifies which polygon it occupies.
The key limitation: minimum-region decomposition is NP-Hard (Lingas, 1982). No algorithm finds the provably optimal (fewest polygon) decomposition; all practical approaches approximate it.
Construction approaches
Triangulation-based (Delaunay + Hertel–Mehlhorn)
The most common approach:
- Compute a Delaunay triangulation of obstacle boundaries.
- Merge adjacent triangles using the Hertel–Mehlhorn algorithm to reduce triangle count.
Pros: well understood, fast, produces connected meshes. Cons: leaves many near-degenerate regions — “fan” patterns of triangles converging at single points, thin slivers. These cause agent localisation failures (an agent near a confluence point cannot reliably determine which polygon it occupies) and create pathfinding artefacts.
Voxel-based (Recast)
Recast (Mikko Mononen, open source) is the industry standard, used by Unity, Unreal, and many commercial engines:
- Voxelise the level geometry into a height-field grid.
- Identify walkable voxels based on slope and headroom.
- Generate a compact height-field (merge vertical column voxels).
- Erode the walkable area by the agent radius.
- Partition the eroded region into simple shapes (watershed or monotone partition).
- Triangulate each shape and merge triangles into larger convex polygons.
- Build the Detour adjacency graph for pathfinding queries.
Unity’s NavMesh Bake pipeline is a Recast implementation. Designers control agent radius, max slope, step height, and manual inclusion/exclusion volumes. The result is stored as a set of convex polygons with shared edges (portals) between them.
Wavefront Edge Expansion (research)
An alternative growth-based algorithm that addresses the Delaunay confluence problem:
- Place seed regions next to every exposed obstruction edge.
- For each seed, classify obstruction edges into directional categories and find potential expansion event points.
- Expand the region in jumps to each event point in order of distance.
- Reseed unclaimed traversable space and repeat until no traversable space remains.
Key property: at most five regions can meet at any single point (proved in Hale, 2011). This eliminates the degenerate confluence regions that plague triangulation approaches. The algorithm’s runtime scales with world complexity (number of obstructions) rather than world size, making it efficient for large sparse environments.
Tile-based navmesh
For large open worlds, a single monolithic navmesh is impractical. The standard solution is tiled navmesh generation:
- Divide the world into a regular grid of tiles (e.g., 32×32 metres in Final Fantasy XIV).
- Generate the navmesh for each tile independently.
- Store tile connectivity at tile borders; portals link adjacent tiles.
This enables:
- Incremental re-baking (only rebuild affected tiles when the world changes).
- Streaming (only load tiles near the player).
- Multi-threaded baking of independent tiles.
Unity’s navmesh supports NavMesh Surface tiles and NavMesh Link components for connecting them.
Precomputed lookup tables
For server-side AI in MMOs with static worlds (Final Fantasy XIV, Gravot et al., Ch. 4), the navmesh can power a precomputed hierarchical lookup table:
Structure
At the lowest level, each polygon stores its next-edge index toward every goal polygon in its local neighbourhood. Higher hierarchy levels group connected polygons into components — component centres serve as nodes at the next abstraction level.
Node → Component → Super-component → ...
Path queries proceed top-down: the highest layer quickly identifies a sequence of components along the route, then lower layers refine the path locally as the agent approaches each component.
Performance
- Queries run in ~4 microseconds for a 4 km² world with thousands of NPCs.
- Memory footprint reduced from ~400 MB (flat) to ~8–9 MB with 3 hierarchy levels.
- Trade-off: static geometry only; door open/close states are handled by runtime polygon accessibility flags, not by table rebuild.
Funnel algorithm
Once the lookup table provides a polygon sequence, the funnel algorithm converts it into a smooth walkable path:
- Identify the portal edges shared between consecutive polygons.
- Progressively tighten a “funnel” (triangular region) from the agent position through each portal.
- Each time the funnel degenerates, emit the apex of the old funnel as a waypoint.
The funnel also applies the agent’s radius, pushing the path away from polygon boundaries to prevent the agent clipping corners.
In practice (Unity)
Unity’s navigation pipeline is built on Recast/Detour:
| Tool | Purpose |
|---|---|
| NavMesh Surface (component) | Defines the bake area and agent settings |
| NavMesh Obstacle (component) | Carves holes at runtime (static or moving) |
| NavMesh Link (component) | Manual connections (jump links, ladders) |
| NavMeshAgent (component) | Queries the navmesh, follows paths |
| NavMesh.SamplePosition (API) | Finds the nearest valid navmesh point |
For tile-based streaming in large worlds, Recast/Detour can be integrated directly via the open-source C++ library with a Unity C# wrapper.
Gotchas:
- Navmesh bake uses agent radius to erode walkable space — if the radius is too large, narrow passages disappear.
- NavMesh Obstacles with “Carve” enabled rebuild affected tiles every time the obstacle moves — disable carving for frequently moving objects and use local avoidance instead.
- Non-uniform terrain slopes require careful
Max Slopecalibration; slopes just below the threshold can create slivers that trap agents.
Trade-offs vs other representations
| Concern | Grid | Navmesh |
|---|---|---|
| Implementation time | Low | High (though Recast handles most of it) |
| Memory for large worlds | High | Low |
| Path quality (naturalness) | Requires post-smoothing | Natural without post-processing |
| Dynamic modification | Easy (flip bits) | Hard (tile rebuild) |
| Localization cost | O(1) (divide by cell size) | O(log n) with spatial index |
| Slope and 3D support | Possible but complex | Built-in |
Related
- unity-navmesh — the engine-facing tool reference for NavMesh Surface, Agent, Obstacle, and Link
- pathfinding-algorithms — A*, JPS+, Theta* that operate on the resulting graph
- game-ai-agent-design — NavMeshAgent, the 3-layer AI model
- steering-behaviours — local movement after the navmesh provides a waypoint path
- npc-performance-at-scale — hierarchical pathfinding, precomputed tables, scalability
- source-game-ai-pro-360-movement-pathfinding — primary source