Game Dev Mechanics: Navigation Meshes (NavMesh) — How It Works

What Is a Navigation Mesh?

A Navigation Mesh (NavMesh) is a data structure that represents the walkable surfaces of a game world as a collection of convex polygons. Rather than subdividing the world into thousands of tiny grid cells, a NavMesh uses larger, irregular polygonal regions that closely conform to the actual geometry of the environment (floors, ramps, ledges, and open areas), while excluding walls, obstacles, and hazards.

If you've ever watched an NPC in The Last of Us, Skyrim, or Halo smoothly navigate around furniture, through doorways, and across open plazas without getting stuck on corners, you've seen a NavMesh at work. It is the standard approach for 3D game AI navigation, and understanding how it works is worth the time for any developer building agents that move through complex environments.

Why NavMeshes Instead of Grids?

The simplest approach to pathfinding is to overlay a 2D grid on the game world and run A* on it. This works for many games: tile-based RPGs, top-down shooters, and strategy games. But grids have significant drawbacks in 3D environments:

• Memory overhead: A fine-grained grid for a large open-world map can require millions of cells. Each cell needs to store walkability data, costs, and potentially multiple layers for multi-story structures.
• Jagged paths: Grid-based paths follow cell centers, producing staircase-like movement unless you add heavy post-processing to smooth them out.
• Resolution tradeoff: Coarse grids miss narrow passages; fine grids explode in memory and search time. You are always compromising.
• Poor 3D support: Grids struggle with slopes, bridges, multi-level structures, and non-planar surfaces without complex extensions.

NavMeshes solve all of these problems. A single large convex polygon can represent an entire open room that would require hundreds of grid cells. This dramatically reduces the node count for pathfinding, resulting in faster queries. Paths follow polygon edges and can be smoothed using the funnel algorithm, producing natural-looking movement without the zigzag artifacts of grid paths.

Consider the numbers: a $100 \times 100$ meter arena at 0.5m grid resolution requires 40,000 cells. The same space represented as a NavMesh might need only 50 to 200 polygons, depending on obstacle complexity. Running A* on 200 nodes versus 40,000 nodes is orders of magnitude faster.

How NavMeshes Are Generated

The most widely used NavMesh generation algorithm is Recast, created by Mikko Mononen and now integrated into Unity, Unreal Engine, and Godot. The process transforms arbitrary 3D level geometry into a clean, walkable polygon mesh through several stages.

Stage 1: Voxelization

The input geometry (all static meshes, terrain, and colliders in the scene) is rasterized into a 3D voxel grid, a heightfield. Each column of voxels records the spans of solid and open space. This is conceptually similar to how a 3D printer slices a model into layers.

The voxel cell size determines the NavMesh resolution. A typical cell size is 0.1 to 0.3 meters. Smaller cells capture finer detail but consume more memory and processing time.

Stage 2: Walkable Surface Identification

The algorithm identifies which voxel surfaces are walkable by checking two criteria:

• Slope angle: The surface normal must be within a maximum walkable slope angle (typically 45 degrees). A surface with normal $\vec{n}$ is walkable if $\vec{n} \cdot \hat{y} \geq \cos(\theta_{\max})$, where $\hat{y}$ is the up vector.
• Clearance height: There must be enough vertical clearance above the surface for the agent to stand. For a 2-meter tall agent, at least 2 meters of empty space is required above the walkable voxel.

Stage 3: Region Building

Walkable voxels are grouped into contiguous regions using a watershed algorithm. Each region represents a connected area of walkable space. The algorithm erodes the walkable area inward by the agent's radius to ensure the agent won't clip through walls.

The erosion distance $d_{\text{erode}}$ equals the agent radius $r_{\text{agent}}$. After erosion, the walkable area is shrunk by $r_{\text{agent}}$ on all sides, ensuring the agent's collision cylinder never intersects geometry.

Stage 4: Contour Tracing and Polygon Generation

The boundaries of each region are traced to produce simplified contours. These contours are reduced using the Douglas-Peucker line simplification algorithm, then triangulated and merged into convex polygons. Convexity is the key property: within any convex polygon, you can travel in a straight line between any two points without leaving the polygon. This is what makes NavMesh pathfinding efficient: once you know which polygon you're in, you can move freely within it.

The final result is a set of convex polygons, each storing vertex positions, references to neighboring polygons (the adjacency graph), and portal information: the shared edges between adjacent polygons that agents cross when moving between them.

Pathfinding on a NavMesh

Once the NavMesh is generated, pathfinding becomes a two-phase process.

Phase 1: Polygon Corridor Search

Each polygon in the NavMesh is treated as a node in a graph. Two polygons are connected if they share an edge (a portal). A* is run on this polygon graph to find the sequence of polygons from the agent's current polygon to the goal polygon.

The heuristic function uses the Euclidean distance between polygon centroids:

$$h(n) = \| \text{centroid}(n) - \text{centroid}(\text{goal}) \|$$

The edge cost between adjacent polygons is the distance between their shared edge midpoints:

$$g(n, m) = \| \text{mid}(\text{portal}_{n,m}) - \text{mid}(\text{portal}_{\text{prev},n}) \|$$

Because the polygon count is small (typically hundreds, not thousands), A* completes almost instantly, often in microseconds.

function findPolygonPath(navMesh, startPoly, goalPoly) {
  const openSet = new PriorityQueue();
  const cameFrom = new Map();
  const gScore = new Map();

  gScore.set(startPoly.id, 0);
  openSet.enqueue(startPoly, heuristic(startPoly, goalPoly));

  while (!openSet.isEmpty()) {
    const current = openSet.dequeue();

    if (current === goalPoly) {
      return reconstructPath(cameFrom, current);
    }

    for (const neighbor of current.neighbors) {
      const tentativeG = gScore.get(current.id)
        + edgeCost(current, neighbor);

      if (tentativeG < (gScore.get(neighbor.id) ?? Infinity)) {
        cameFrom.set(neighbor.id, current);
        gScore.set(neighbor.id, tentativeG);
        const f = tentativeG + heuristic(neighbor, goalPoly);
        openSet.enqueue(neighbor, f);
      }
    }
  }

  return null; // No path found
}

Phase 2: The Funnel Algorithm (String Pulling)

The A* search returns a corridor, a sequence of polygons. But we don't want the agent to walk through polygon centroids in a zigzag. We want the shortest, smoothest path through the corridor. This is where the funnel algorithm (also called string pulling) comes in.

Imagine threading a string through the corridor of polygons and then pulling it taut. The string would take the shortest path, cutting corners where possible while staying within the corridor boundaries. That is exactly what the funnel algorithm computes.

The algorithm maintains a funnel defined by a left boundary edge and a right boundary edge, both originating from the current apex point. As it processes each portal (the shared edge between consecutive polygons), it narrows the funnel. When one side of the funnel crosses over the other, a new waypoint is added and the funnel resets from that point.

function funnelPath(portals, start, end) {
  const pts = [start];
  let apex = start, apexIdx = 0;
  let left = start, right = start;
  let leftIdx = 0, rightIdx = 0;

  for (let i = 1; i < portals.length; i++) {
    const pL = portals[i].left;
    const pR = portals[i].right;

    // Tighten the right side
    if (triArea2D(apex, right, pR) <= 0) {
      if (vEqual(apex, right) || triArea2D(apex, left, pR) > 0) {
        right = pR; rightIdx = i;
      } else {
        pts.push(left);
        apex = left; apexIdx = leftIdx;
        left = apex; right = apex;
        i = apexIdx + 1; continue;
      }
    }

    // Tighten the left side
    if (triArea2D(apex, left, pL) >= 0) {
      if (vEqual(apex, left) || triArea2D(apex, right, pL) < 0) {
        left = pL; leftIdx = i;
      } else {
        pts.push(right);
        apex = right; apexIdx = rightIdx;
        left = apex; right = apex;
        i = apexIdx + 1; continue;
      }
    }
  }

  pts.push(end);
  return pts;
}

// Signed area of triangle in 2D (XZ plane)
function triArea2D(a, b, c) {
  return (b.x - a.x) * (c.z - a.z)
       - (c.x - a.x) * (b.z - a.z);
}

The triArea2D function computes twice the signed area of the triangle formed by three points in the XZ plane. Positive values mean point $c$ is to the left of the line $\overrightarrow{ab}$, negative means it is to the right. This geometric test drives the funnel narrowing. The result is a sequence of waypoints forming the shortest path through the polygon corridor.

Handling Dynamic Obstacles

Static NavMeshes work well for fixed level geometry, but games often have dynamic obstacles: moving platforms, destructible walls, doors that open and close. Several approaches handle these:

• NavMesh cutting: Dynamically carve holes in the NavMesh where obstacles appear. Unity's NavMeshObstacle component does this by re-triangulating locally around the obstacle at runtime.
• Local avoidance: Use a separate system like ORCA (Optimal Reciprocal Collision Avoidance) to dodge dynamic obstacles at runtime without modifying the NavMesh. The NavMesh handles macro-level pathfinding; local avoidance handles micro-level steering.
• Partial re-baking: Regenerate only the affected region of the NavMesh when geometry changes. This is more expensive but produces cleaner results than runtime cutting.
• Off-mesh links: Represent special traversal actions (jumping gaps, climbing ladders, dropping off ledges) as explicit connections between otherwise disconnected NavMesh regions.

Real-World Implementations

Unity includes a built-in NavMesh system based on Recast. You mark objects as "Navigation Static," configure agent parameters (radius, height, step height, max slope), and bake the NavMesh. At runtime, NavMeshAgent components handle pathfinding and movement automatically.

Unreal Engine uses its NavigationSystem with NavMeshBoundsVolume actors. Unreal supports dynamic NavMesh regeneration and runtime obstacle avoidance through its Detour Crowd AI controller.

Godot 4 provides NavigationServer3D with support for multiple navigation maps, agent avoidance, and baked NavMeshes via NavigationRegion3D nodes.

The original Recast & Detour library by Mikko Mononen remains the most widely used open-source NavMesh implementation. Recast handles mesh generation while Detour handles runtime pathfinding, crowd simulation, and dynamic obstacle avoidance. Most commercial engines wrap or extend this library directly.

Performance Considerations

NavMesh pathfinding is fast, but several optimizations are worth knowing about:

• Hierarchical pathfinding: For very large worlds, group polygons into clusters and run A* at the cluster level first, then refine within clusters. This is the NavMesh equivalent of HPA*.
• Path caching: If many agents are heading to the same destination, cache and reuse polygon corridor results.
• Query batching: Process pathfinding requests over multiple frames to avoid CPU spikes when many agents need new paths simultaneously.
• Multi-layer NavMeshes: For multi-story buildings, bridges, and overpasses, stack multiple NavMesh layers vertically with connections between them.

NavMeshes work by reducing 3D spatial navigation to a graph search over convex polygons. Understanding the generation pipeline and query phases gives you the foundation to build AI agents that move through your game worlds naturally.