Game AI: Navmesh & Steering

01Why not a grid

A uniform grid runs search on the 4- or 8-connected cell graph. It's the right structure for tile-based games (the world is a grid) and is dead simple. For continuous 3D worlds the navmesh wins on three counts, but this is a "more compact and better paths," not "grids are wrong":

• Memory/resolution: grid cost scales with area at a fixed cell size; a big open room is one navmesh polygon but thousands of cells, and the cell size has to shrink to fit narrow gaps, blowing up the whole grid.
• The blocky path: an 8-connected grid path is limited to 8 directions, so diagonals come out as staircases needing post-smoothing (the Graph Traversal octile note). The navmesh just doesn't introduce that artifact.
• 3D / multi-level / slopes: a 2D grid can't natively represent ramps, bridges over bridges, or overlapping floors; a navmesh is polygons in 3D space.

02The navigation mesh

A navmesh represents the walkable surface as convex polygons that tile it. Adjacent polygons sharing an edge are linked into the dual graph: each polygon is a node, each shared edge a link^[1]. Convexity is load-bearing, for any two points inside one convex polygon, the straight segment between them stays inside, so intra-polygon movement is collision-free by construction and needs no search. Search only happens between polygons.

// Each polygon stores its vertices AND, per edge, the neighbor polygon across
// that edge (or NO_NEIGHBOR for a wall). The neighbor array IS the dual graph A* walks.
struct NavPoly {
    std::array<int, MAX_VERTS> vertIndex;   // indices into the shared vertex pool
    std::array<int, MAX_VERTS> neighbor;    // neighbor poly per edge, or NO_NEIGHBOR
    int vertCount;                          // 3..6 (Recast emits up to 6-gons)
};
struct NavMesh {
    std::vector<Vec3>    vertices;             // shared vertex pool
    std::vector<NavPoly> polys;                // nodes of the dual graph; neighbors[] feed A*
};

const NO_NEIGHBOR: i32 = -1;

struct NavPoly {
    vert_index: [i32; MAX_VERTS],   // indices into the shared vertex pool
    neighbor:   [i32; MAX_VERTS],   // neighbor poly per edge, or NO_NEIGHBOR
    vert_count: usize,             // 3..6
}
struct NavMesh {
    vertices: Vec<Vec3>,   // shared vertex pool
    polys:    Vec<NavPoly>, // dual-graph nodes
}

03Generating it

The modern automatic approach (Mononen's Recast, the de-facto standard behind Unity and Unreal navigation) is a voxelization pipeline, run at bake time^[2]:

1. Rasterize the collision triangles into a solid heightfield of voxel spans.
2. Filter walkable spans by slope (surface angle), clearance (agent height), and ledge erosion (agent radius), plus low-clearance filters.
3. Build a compact heightfield and a distance field (distance to the nearest border).
4. Region-segment the walkable area (watershed by default; monotone or layer as alternatives).
5. Trace and simplify contours around each region.
6. Polygonize the contours into convex polygons (≤6 verts); a detail mesh adds height samples.

04Corridor to taut path

Run A* on the polygon dual graph (cost = distance between polygon centers, heuristic = straight-line distance, admissible). The Graph Traversal tutorial already builds A* and proves admissibility, so this defers to it. The key point: A* returns a polygon corridor (an ordered strip of polygons), not a line.

Drag the start and goal. Toggle the naive poly-center path against the funnel, then watch the agent walk:

// triArea2 = signed 2x triangle area (the 2D cross product); its sign = left/right of a line.
float triArea2(Vec2 a, Vec2 b, Vec2 c) { return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); }

std::vector<Vec2> stringPull(const std::vector<Portal>& portals) {
    std::vector<Vec2> path;
    Vec2 apex = portals[0].left, left = portals[0].left, right = portals[0].right;
    int apexI = 0, leftI = 0, rightI = 0;
    path.push_back(apex);
    for (int i = 1; i < (int)portals.size(); ++i) {
        Vec2 l = portals[i].left, r = portals[i].right;
        if (triArea2(apex, right, r) <= 0) {                    // tighten the right foot
            if (apex == right || triArea2(apex, left, r) > 0) { right = r; rightI = i; }  // narrow
            else { path.push_back(left); apex = left; apexI = leftI;     // right crossed left -> corner
                   left = apex; right = apex; leftI = apexI; rightI = apexI; i = apexI; continue; }
        }
        if (triArea2(apex, left, l) >= 0) {                     // tighten the left foot (mirror)
            if (apex == left || triArea2(apex, right, l) < 0) { left = l; leftI = i; }    // narrow
            else { path.push_back(right); apex = right; apexI = rightI;
                   left = apex; right = apex; leftI = apexI; rightI = apexI; i = apexI; continue; }
        }
    }
    path.push_back(portals.back().left);   // goal
    return path;
}

fn tri_area2(a: Vec2, b: Vec2, c: Vec2) -> f32 { (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) }

fn string_pull(portals: &[Portal]) -> Vec<Vec2> {
    let mut path = Vec::new();
    let (mut apex, mut left, mut right) = (portals[0].left, portals[0].left, portals[0].right);
    let (mut apex_i, mut left_i, mut right_i) = (0usize, 0usize, 0usize);
    path.push(apex);
    let mut i = 1;
    while i < portals.len() {
        let (l, r) = (portals[i].left, portals[i].right);
        if tri_area2(apex, right, r) <= 0.0 {
            if apex == right || tri_area2(apex, left, r) > 0.0 { right = r; right_i = i; }
            else { path.push(left); apex = left; apex_i = left_i;
                   left = apex; right = apex; left_i = apex_i; right_i = apex_i; i = apex_i + 1; continue; }
        }
        if tri_area2(apex, left, l) >= 0.0 {
            if apex == left || tri_area2(apex, right, l) < 0.0 { left = l; left_i = i; }
            else { path.push(right); apex = right; apex_i = right_i;
                   left = apex; right = apex; left_i = apex_i; right_i = apex_i; i = apex_i + 1; continue; }
        }
        i += 1;
    }
    path.push(portals[portals.len()-1].left);   // goal
    path
}

05Path to motion: steering

Pathfinding is global and discrete (which polygons, computed occasionally). Steering is local and continuous (how to accelerate this frame, every frame). The path supplies the corners (from the funnel); steering produces smooth acceleration toward the current one using Reynolds' simple vehicle model^[4]: a steering force clamped to a max, integrated into a velocity clamped to a max speed.

Drag the target. Toggle seek (orbits) against arrive (brakes), and add wander:

// clampMag truncates a vector to a max length. Reynolds' simple vehicle (mass = 1).
Vec2 seek(const Agent& a, Vec2 target) {
    Vec2 desired = normalize(target - a.position) * a.maxSpeed;  // full speed at the target
    return clampMag(desired - a.velocity, a.maxForce);          // no braking -> overshoots/orbits
}
Vec2 arrive(const Agent& a, Vec2 target, float slowingRadius) {
    Vec2 offset = target - a.position; float dist = length(offset);
    if (dist < 1e-4f) return {0,0};
    float speed = min(a.maxSpeed * (dist / slowingRadius), a.maxSpeed);  // ramp down near target
    Vec2 desired = offset * (speed / dist);
    return clampMag(desired - a.velocity, a.maxForce);
}
void integrate(Agent& a, Vec2 steering, float dt) {       // forward Euler
    a.velocity = clampMag(a.velocity + steering * dt, a.maxSpeed);
    a.position = a.position + a.velocity * dt;
}

fn seek(a: &Agent, target: Vec2) -> Vec2 {
    let desired = (target - a.position).normalize() * a.max_speed;  // full speed at target
    clamp_mag(desired - a.velocity, a.max_force)                  // no braking -> orbits
}
fn arrive(a: &Agent, target: Vec2, slowing_radius: f32) -> Vec2 {
    let offset = target - a.position; let dist = offset.length();
    if dist < 1e-4 { return Vec2::ZERO; }
    let speed = (a.max_speed * (dist / slowing_radius)).min(a.max_speed);  // ramp down
    let desired = offset * (speed / dist);
    clamp_mag(desired - a.velocity, a.max_force)
}
fn integrate(a: &mut Agent, steering: Vec2, dt: f32) {        // forward Euler
    a.velocity = clamp_mag(a.velocity + steering * dt, a.max_speed);
    a.position += a.velocity * dt;
}

06Combining & flocking

Multiple behaviors blend by weighted sum (add each steering vector × weight, truncate), priority arbitration (take the highest-priority non-trivial behavior), or context steering (each behavior writes interest/danger into directional bins, pick the best bin). Flocking (Reynolds' boids) is three behaviors over local neighbors^[5]: separation (steer away from neighbors' positions), cohesion (steer toward their centroid), alignment (match their heading).

07Local avoidance

Agents must not walk through each other. A velocity obstacle (VO) is the set of an agent's velocities that, relative to a neighbor, lead to a collision within a time horizon, a cone in velocity space. Pick a velocity outside it and you avoid the collision (under a constant-velocity assumption).

Boids with separation/cohesion/alignment, plus two agents crossing, toggle reciprocity to see the dance vs a clean pass:

08Crowds & the BT seam

A crowd manager runs many agents together: path-corridor following + local avoidance + radius/separation + replanning. Detour's dtCrowd is the reference, but it uses sampling-based velocity-obstacle avoidance (score candidate velocities), not an exact ORCA LP, and it's practical for roughly 20 to 30 agents per crowd in typical configurations while taking over their positions^[9]. For thousands of units, the documented approach is flow-field tiles (a shared vector field, shipped in Supreme Commander 2, built on Continuum Crowds), not per-agent steering^[10].

Wrong answers, and why: a zig-zag is a corridor-extraction problem fixed by the funnel (not the heuristic or polygon convexity); and agents stuck in concave geometry need a global path (local avoidance is never a planner; reciprocity and horizon don't add a map).

09Pitfalls

10What's next

Agents can think (behavior trees), find a route (pathfinding), and now move and avoid each other. The next module connects players across the wire: Networking, netcode and rollback (prediction, reconciliation, interpolation, lag compensation, and rollback), then tooling and the 3D-game capstone. The full path is on the series hub.

1. Greg Snook. "Simplified 3D Movement and Pathfinding Using Navigation Meshes." Game Programming Gems (2000). The origin of navmesh-in-games: convex polygons, the straight-line-traversable interior, and A* on adjacency.
2. Mikko Mononen et al. Recast & Detour. github.com/recastnavigation. The de-facto navmesh toolset (generation pipeline + runtime) behind Unity, Unreal, Godot, and others.
3. Mikko Mononen. "The Simple Stupid Funnel Algorithm." Digesting Duck (2010). digestingduck.blogspot.com. The canonical compact apex/left/right portal funnel, O(n) over the corridor.
4. Craig Reynolds. "Steering Behaviors For Autonomous Characters." GDC 1999. red3d.com. Seek, flee, arrive, pursue, evade, wander, and the simple vehicle model.
5. Craig Reynolds. "Flocks, Herds, and Schools: A Distributed Behavioral Model." SIGGRAPH 1987. red3d.com. Separation, cohesion, alignment, emergent flocking from local rules.
6. Jur van den Berg, Ming Lin, Dinesh Manocha. "Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation." ICRA 2008. gamma.cs.unc.edu. Half-responsibility velocity averaging, fixing the naive-VO oscillation.
7. Jur van den Berg, Stephen Guy, Jamie Snape, Ming Lin, Dinesh Manocha. "Reciprocal n-Body Collision Avoidance" (ORCA). ISRR 2011. gamma.cs.unc.edu. Half-plane per neighbor + a low-dimensional linear program; the safest-velocity fallback.
8. Ben Sunshine-Hill. "RVO and ORCA: How They Really Work." Game AI Pro 3, ch. 19. gameaipro.com. The games-side explanation of VO/RVO/ORCA and the oscillation.
9. Mikko Mononen. DetourCrowd. recastnav.com. The crowd manager: corridor following + sampling-based avoidance + separation; practical at ~20 to 30 agents.
10. Elijah Emerson. "Crowd Pathfinding and Steering Using Flow Field Tiles." Game AI Pro, ch. 23. gameaipro.com. Flow-field tiles for thousands of units (Supreme Commander 2), built on Treuille et al.'s Continuum Crowds (SIGGRAPH 2006).
11. Jason Gregory. Game Engine Architecture, 3rd ed. (the path finding / navigation chapter). gameenginebook.com. Runtime navigation, path smoothing, the agent-vs-collision seam.
12. Unity, "Inner Workings of the Navigation System," and Unreal navigation (Recast & Detour). docs.unity3d.com. Both engines build a Recast navmesh and use RVO-style avoidance, the de-facto standard.