Game AI: Navmesh & Steering

01Why not a grid

The simplest map of where an agent can walk is a grid: chop the floor into square cells, mark each one walkable or blocked, and search from cell to neighboring cell, with 4 or 8 neighbors per cell. It's the right structure for tile-based games (the world is a grid) and is simple to build and query. For continuous 3D worlds a navmesh, a set of walkable polygons covering the floor (§2), has three advantages, though grids remain the right choice when the game itself is made of tiles:

• 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, which multiplies the cell count everywhere.
• The blocky path: an 8-connected grid path is limited to 8 directions, so off-axis routes come out as staircases that need post-smoothing. A navmesh corridor plus the funnel (§4) gives a path that heads straight for each corner at any angle.
• 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

The guard needs to know where it can stand and how those places connect, in a form a search can walk quickly. 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 movement within a polygon 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.
constexpr int MAX_VERTS   = 6;    // Detour's DT_VERTS_PER_POLYGON
constexpr int NO_NEIGHBOR = -1;

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; neighbor[] feeds A*
};

// 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.
const MAX_VERTS: usize = 6;     // Detour's DT_VERTS_PER_POLYGON
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>, // nodes of the dual graph; neighbor[] feeds A*
}

03Generating it

Nobody wants to place polygons by hand over a 2 km level, and level geometry is rarely clean: walls overlap, floors have gaps, props intersect. The common automatic approach (Mononen's Recast, which powers the navigation in Unity, Unreal, Godot, and O3DE according to its README) is a voxelization pipeline, run at bake time^[2]. The stages below follow Recast's own sample build^[2]; Unity's documentation describes its bake in the same terms: rasterize to voxels, extract walkable surfaces, build the mesh^[11].

1. Mark and rasterize: flag triangles too steep to walk on (the slope limit), then rasterize the collision triangles into a solid heightfield of voxel spans.
2. Filter walkable spans: keep low obstacles the agent can step over (climb height), drop ledges higher than the climb height, and drop spans without head clearance (agent height).
3. Build a compact heightfield, erode the walkable area by the agent radius, and build a distance field (distance to the nearest border).
4. Region-segment the walkable area (watershed in Recast's sample; monotone or layer partitioning as faster 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

A* hands back a list of polygons, and the obvious way to walk it, through the middle of each doorway, makes the guard weave like it's lost. Run A*, the shortest-path search guided by an estimate of the distance left, on the polygon dual graph. Each step needs a cost and a heuristic: Detour measures cost between the midpoints of the shared edges the path crosses (polygon centers are the simpler alternative) and uses straight-line distance to the goal as the heuristic, which is admissible since no path is shorter than a straight line. The Graph Traversal tutorial covers A* and the admissibility theorem, so this page builds on it. The key point: A* returns a polygon corridor (an ordered strip of polygons), not a line.

The navmesh below is four rectangular polygons joined through three gaps in the walls, the portals; the corridor A* returns is all four. Drag the start (blue, in the first polygon) and the goal (amber, in the last), switch between the two paths, and press walk:

// Twice the signed area of triangle abc, with Mononen's sign convention: in a y-up
// frame it is positive when c lies to the RIGHT of the ray a->b (the negated 2D cross
// product). Portals give left/right as seen walking along the corridor. With the
// ordinary cross product the comparisons below would all flip.
float triArea2(Vec2 a, Vec2 b, Vec2 c) { return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y); }

// portals[0] is the start point (left == right == start); the last portal is the goal.
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 apexIndex = 0, leftIndex = 0, rightIndex = 0;
    path.push_back(apex);
    for (int i = 1; i < static_cast<int>(portals.size()); ++i) {
        Vec2 newLeft = portals[i].left, newRight = portals[i].right;
        if (triArea2(apex, right, newRight) <= 0) {          // right foot moves inward (or stays)
            if (apex == right || triArea2(apex, left, newRight) > 0) {
                right = newRight; rightIndex = i;                    // narrow the funnel
            } else {                                                 // right crossed over left:
                path.push_back(left);                                // the left foot is a corner
                apex = left; apexIndex = leftIndex;                  // restart the funnel there
                left = apex; right = apex; leftIndex = apexIndex; rightIndex = apexIndex;
                i = apexIndex;                                       // ++i resumes after the new apex
                continue;
            }
        }
        if (triArea2(apex, left, newLeft) >= 0) {            // left foot: the mirror image
            if (apex == left || triArea2(apex, right, newLeft) < 0) {
                left = newLeft; leftIndex = i;
            } else {
                path.push_back(right);
                apex = right; apexIndex = rightIndex;
                left = apex; right = apex; leftIndex = apexIndex; rightIndex = apexIndex;
                i = apexIndex;
                continue;
            }
        }
    }
    if (!(path.back() == portals.back().left))   // the goal can already be the last corner
        path.push_back(portals.back().left);
    return path;
}

// Twice the signed area of triangle abc, Mononen's sign: positive when c is to the
// RIGHT of a->b in a y-up frame. Portals give left/right as seen walking the corridor.
fn tri_area2(a: Vec2, b: Vec2, c: Vec2) -> f32 { (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y) }

// portals[0] is the start point (left == right == start); the last portal is the goal.
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 left_index, mut right_index) = (0usize, 0usize);
    let mut apex_index: usize;   // set whenever a corner is found
    path.push(apex);
    let mut i = 1;
    while i < portals.len() {
        let (new_left, new_right) = (portals[i].left, portals[i].right);
        if tri_area2(apex, right, new_right) <= 0.0 {          // right foot moves inward (or stays)
            if apex == right || tri_area2(apex, left, new_right) > 0.0 {
                right = new_right; right_index = i;                   // narrow the funnel
            } else {                                                  // right crossed over left:
                path.push(left);                                      // the left foot is a corner
                apex = left; apex_index = left_index;                 // restart the funnel there
                left = apex; right = apex; left_index = apex_index; right_index = apex_index;
                i = apex_index + 1;                                  // resume after the new apex
                continue;
            }
        }
        if tri_area2(apex, left, new_left) >= 0.0 {            // left foot: the mirror image
            if apex == left || tri_area2(apex, right, new_left) < 0.0 {
                left = new_left; left_index = i;
            } else {
                path.push(right);
                apex = right; apex_index = right_index;
                left = apex; right = apex; left_index = apex_index; right_index = apex_index;
                i = apex_index + 1;
                continue;
            }
        }
        i += 1;
    }
    let goal = portals[portals.len() - 1].left;
    if path.last() != Some(&goal) { path.push(goal); }   // the goal can already be the last corner
    path
}

05Path to motion: steering

The guard now has a list of corners. Snap its velocity straight at each one and it turns instantly, runs at full speed into the last corner and stops dead, which looks robotic. 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. In an engine, steering stops at that velocity: the character controller (§8) moves the agent and owns its position. The widgets below have no physics, so they advance position from the velocity themselves.

The target hops to a new spot every few seconds (or drag it yourself). Compare seek, which overshoots, with arrive, which brakes, and with 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
}
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);
}
// Steering writes velocity only (forward Euler on velocity). The physics character
// controller takes a.velocity as its desired velocity and owns the position:
// it moves and collides (collide-and-slide, slopes, step-up) and writes the result.
void applySteering(Agent& a, Vec2 steering, float dt) {
    a.velocity = clampMag(a.velocity + steering * dt, a.maxSpeed);
}

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 -> overshoots
}
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)
}
// Steering writes velocity only (forward Euler on velocity). The physics character
// controller takes a.velocity as its desired velocity and owns the position.
fn apply_steering(a: &mut Agent, steering: Vec2, dt: f32) {
    a.velocity = clamp_mag(a.velocity + steering * dt, a.max_speed);
}

06Combining & flocking

A sheep in a flock wants to stay near the others, not bump into them, and head the same way, all in the same frame. So each agent runs several steering behaviors at once, and their outputs have to become one acceleration. 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 and danger into directional bins, and the agent picks the best bin)^[13]. 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

Two guards walk down the same corridor in opposite directions. Each one's path is fine; together they're about to walk through each other, and neither path knew the other existed. A velocity obstacle (VO) is the set of an agent's velocities that, relative to a neighbor, lead to a collision: a cone in velocity space with its apex at the neighbor's velocity, cut off at a time horizon in most game implementations. Pick a velocity outside it and you avoid the collision, provided the neighbor keeps its velocity. The concept comes from Fiorini and Shiller's robotics work^[6].

The first mode is boids with separation, cohesion, and alignment. The second has two agents crossing head-on, each choosing its velocity with a velocity obstacle; the checkbox switches between plain VO and RVO:

08Crowds & the BT seam

Thirty guards in one courtyard all want the same doorway. Steering each one in isolation gives a pile-up; something has to plan their corridors, spacing and avoidance together. A crowd manager runs many agents together: path-corridor following, local avoidance, radius-based separation, and replanning. Detour's dtCrowd is the open-source reference. Its avoidance scores sampled candidate velocities against RVO-style velocity obstacles rather than solving ORCA's LP, and its documentation puts the practical maximum at 20 to 30 agents under one crowd manager, which takes over their positions entirely^[9]. For hundreds to thousands of units, one documented approach is flow-field tiles (a shared vector field per goal, shipped in Supreme Commander 2) in place of per-agent pathfinding^[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, Netcode & Rollback, connects players across the wire with prediction, reconciliation, interpolation, lag compensation and rollback. Tooling and the 3D-game capstone follow. The full path is on the series hub.

1. Greg Snook. "Simplified 3D Movement and Pathfinding Using Navigation Meshes." Game Programming Gems (2000). An early, widely cited description of navigation meshes for games: convex polygons, the straight-line-traversable interior, and A* on adjacency.
2. Mikko Mononen et al. Recast & Detour. github.com/recastnavigation. The README states that Recast "powers AI navigation features in Unity, Unreal, Godot, O3DE and countless AAA and indie games and engines." The build stages in §3 follow the repository's RecastDemo/Source/Sample_SoloMesh.cpp, and DT_VERTS_PER_POLYGON = 6 is in DetourNavMesh.h.
3. Mikko Mononen. "The Simple Stupid Funnel Algorithm." Digesting Duck (2010). digestingduck.blogspot.com. The compact apex/left/right portal funnel the §4 code follows, including its triarea2 sign convention; the post notes that it restarts the scan from the new apex after each corner, recomputing some portals.
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." IEEE International Conference on Robotics and Automation (ICRA 2008), pp. 1928–1935. DOI: 10.1109/ROBOT.2008.4543489. PDF (archived copy of the authors' page). Reviews Fiorini and Shiller's velocity obstacle, shows it oscillates between two agents, and proves RVO's half-responsibility choice collision-free, oscillation-free, and same-sided for two agents; separates that oscillation from "reciprocal dances."
7. Jur van den Berg, Stephen J. Guy, Ming Lin, Dinesh Manocha. "Reciprocal n-Body Collision Avoidance" (ORCA). Robotics Research: The 14th International Symposium ISRR (2009), Springer Tracts in Advanced Robotics 70, 2011, pp. 3–19. gamma.cs.unc.edu/ORCA/publications/ORCA.pdf. Half-plane per neighbor plus a low-dimensional linear program; when that LP is infeasible, a 3-D LP picks the "safest possible" velocity.
8. Ben Sunshine-Hill. "RVO and ORCA: How They Really Work." Game AI Pro 3, ch. 19, 2017. gameaipro.com (chapter PDF). Calls RVO and its descendants the standard for collision avoidance in games; walks through VO's two-agent oscillation and RVO's three-agent failure case, and notes that the reference ORCA library is named RVO2.
9. Mikko Mononen. DetourCrowd. recastnav.com. The crowd manager: corridor following, avoidance, and separation. The documentation gives "between 20 and 30" as the maximum agents under crowd management and requires handing position control to the crowd; DetourObstacleAvoidance.cpp scores sampled velocities (grid or adaptive sampling) against RVO-style obstacles.
10. Elijah Emerson. "Crowd Pathfinding and Steering Using Flow Field Tiles." Game AI Pro, ch. 23, 2013. gameaipro.com (chapter PDF). The flow-field tile system used in Supreme Commander 2 for moving hundreds to thousands of units.
11. Unity Technologies. "Inner Workings of the Navigation System." AI Navigation 2.0 manual. docs.unity3d.com. The bake "rasterizes the scene into voxels, then it extracts the walkable surfaces"; agents use reciprocal velocity obstacles; moving obstacles belong to local avoidance and stationary ones to the navmesh (carving). Also Epic Games, "Navigation System in Unreal Engine," dev.epicgames.com, which lists "Reciprocal Velocity Obstacles (RVO), and the Detour Crowd Manager" as its two avoidance methods.
12. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert E. Tarjan. "Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons." Algorithmica 2:209–233, 1987. DOI: 10.1007/BF01840360. link.springer.com/article/10.1007/BF01840360. Shortest paths inside a triangulated simple polygon in linear time, the bound the funnel method achieves.
13. Andrew Fray. "Context Steering: Behavior-Driven Steering at the Macro Scale." Game AI Pro 2, ch. 18, 2015. gameaipro.com (chapter PDF). Interest and danger maps over a ring of directions, and the cancellation problem of summed steering forces.