Navigation meshes (navmesh)

A navigation mesh (navmesh) is "a collection of two-dimensional convex polygons" that tells AI characters where they can walk; pathfinding then runs across those polygons instead of across the raw level geometry (Wikipedia: Navigation mesh). The idea is usually credited to Greg Snook's article in Game Programming Gems (2000) (Wikipedia: Navigation mesh).

Players never see the navmesh, but they see what goes wrong when it is wrong: enemies that cannot follow you up a ramp, or that walk into a wall where a prop was added late. That is why level designers and environment artists need to know how it is built.

#How a navmesh is generated

Most engines use Recast, an open-source library that "powers AI navigation features in Unity, Unreal, Godot, O3DE and countless AAA and indie games" (GitHub: Recast Navigation). Recast builds the mesh in four steps (GitHub: Recast Navigation):

1. It "rasterizes the input triangle meshes into voxels".
2. Voxels where agents cannot move are filtered out.
3. The walkable voxels are divided into polygonal regions.
4. Those regions are re-triangulated into the final navmesh.

The input is your level: floors, walls, props and their collision. The agent settings decide which parts survive the filtering step.

#Agent radius, height, step height and slope

A navmesh describes only where the centre of an agent can stand. Godot puts it plainly: "A navigation mesh only describes a traversable area for an agent's center position" (Godot Engine documentation: Using navigation meshes). Each setting removes part of the walkable surface:

The radius rule has a direct consequence for layout. Because the mesh shrinks by one radius from every wall, a gap narrower than twice the agent radius closes completely. A 0.5 m radius, for example, needs a gap of more than 1 m before any navmesh passes through it.

#Which geometry the navmesh reads

Engines differ in what they feed into step 1:

• Unity lets you choose on the NavMesh Surface: Render Meshes ("Use geometry from Render Meshes and Terrains") or Physics Colliders; with colliders, agents "can move closer to the edge of the physical bounds of the environment" (Unity documentation: NavMesh Surface component reference).
• Godot can parse "geometry parsed from visual meshes, from physics collision", or both, through parsed_geometry_type, with a collision_mask to filter colliders (Godot Engine documentation: Using navigation meshes).
• Unreal generates from collision. Epic recommends "Use Simple Collision when possible for Static Meshes", because fewer collision triangles generate faster (Unreal Engine documentation: Optimizing Navigation Mesh Generation Speed…).

#What artists and level designers should keep in mind

• Collision decides walkability. Missing collision leaves holes in the navmesh; a lip or bump in collision can break a connection that looks fine visually. See collision meshes.
• Small props. Every prop that affects navigation cuts a hole. In Unreal, turn off Can Ever Affect Navigation for actors "that should not affect the Navigation Mesh", such as small or moving actors in unreachable areas (Unreal Engine documentation: Optimizing Navigation Mesh Generation Speed…).
• Build to the agent metrics. Doorways, corridors, stair steps and ramp angles should fit the agent settings with margin. Agree these numbers in your metrics and test them in a gym level.
• Several agent sizes. Large enemies need their own navmesh. Sunset Overdrive had one for humanoids (2 m tall, 0.5 m radius) and one for large bots (4.5 m tall, 1.35 m radius) (GameDev.net: A Thread About Navigation Mesh and Sunset…).
• Off-mesh links cover jumps, ladders and vaults that the mesh cannot represent. At Insomniac, these "nav clues" were placed by artists and designers and built into prefabs for railings and cars (GameDev.net: A Thread About Navigation Mesh and Sunset…).
• Late changes to set dressing and art passes can break paths that worked in the blockout. Rebuild and check the navmesh after every art pass.

#How to set one up

Unreal Engine 5 (Unreal Engine documentation: Basic Navigation in Unreal Engine; Unreal Engine documentation: ARecastNavMesh; Unreal Engine documentation: Optimizing Navigation Mesh Generation Speed…):

1. In the Place Actors panel, search for NavMeshBoundsVolume and drag it into the level.
2. Scale it to cover the walkable area (Epic's example uses X = 20, Y = 20, Z = 5). The navmesh is generated as soon as the volume is added.
3. Press P to show the navmesh in the viewport (green by default).
4. Select RecastNavMesh-Default in the Outliner. Set Agent Radius, Agent Height and Agent Max Slope to match your character, and enable Draw Poly Edges and Draw Tile Bounds under Display to check the result.
5. Keep cell size "as large as possible while maintaining the required precision for your Agents", and tile size "between 32 to 128 cells per side".
6. Turn off Can Ever Affect Navigation on props that should not cut holes.

Unity (AI Navigation 2.0) (Unity documentation: Create a NavMesh; Unity documentation: NavMesh Surface component reference):

1. Select the scene geometry and choose Add Component > Navigation > NavMesh Surface.
2. Pick the Agent Type, and set Collect Objects, Include Layers and Use Geometry (Render Meshes or Physics Colliders).
3. Click Bake. The result appears as a blue overlay when the Navigation window is open.
4. Use Minimum Region Area to remove small disconnected islands.

Godot 4 (Godot Engine documentation: Using navigation meshes):

1. Add a NavigationRegion3D and assign a new NavigationMesh resource.
2. Set agent_radius, agent_height, agent_max_climb, agent_max_slope, and a cell_size that matches the navigation map.
3. Choose parsed_geometry_type (meshes, static colliders or both) and bake. Avoid very small cells: they "can create so many voxels that it has the potential to freeze the game or even crash".

#Video tutorials

#Use in recent games

#In different tools

#Further reading and watching

Related pages: collision meshes, player collision capsule, grids and metrics, gym levels and metrics maps, layout and flow, blockout.