Guide

Game pathfinding and navmesh explained

A guard that runs into a wall, an RTS unit that clips through a cliff, a companion NPC stuck on a stair lip — bad pathfinding is one of the fastest ways players notice your AI is fake. Production navigation is not one algorithm; it is a stack: a search graph (grid, navmesh, or waypoint network), a planner like A* that finds a coarse route, and a movement layer that follows corners with steering and local avoidance. This guide covers graph types, navmesh baking and agent radii, dynamic obstacles, hierarchical and flow-field shortcuts, integration with behavior trees, multiplayer authority, performance budgets, common mistakes, and a checklist for shipping navigation that survives real levels.

What pathfinding solves

Pathfinding answers: given a start pose and a goal pose, which sequence of walkable positions gets an agent there? It does not answer how the character animates, accelerates, or jumps — that is locomotion. Separating planning from movement is the core design choice: the planner produces a polyline or node list; the motor layer turns it into velocity each frame.

Three failure modes dominate player complaints:

No path found when a valid route exists (bad graph or agent radius).
Ugly paths — zigzags, hugging walls, U-turns at every corner.
Stuck agents — local minima, dynamic blockers, or avoidance deadlock.

Good navigation feels invisible. Players only notice it when an enemy takes a believable flank or when your companion cleanly paths around furniture during combat.

Graph representations: grid, navmesh, waypoints

Every pathfinder searches a graph: nodes (places you can stand) and edges (legal moves between them). The graph choice drives memory, bake time, and path quality.

Grid graphs

Tile the world into cells; mark each cell walkable or blocked. Simple to implement, easy to serialize for turn-based games and roguelikes. Weaknesses: memory grows with map area, diagonal moves need corner-cutting rules, and large open fields produce staircase paths unless you add smoothing or jump-point search.

Waypoint networks

Designers place nodes by hand and connect them with edges. Cheap at runtime and predictable for scripted patrols. Weaknesses: maintenance burden, gaps when geometry changes, and agents that only know designer-approved routes — fine for racing splines, painful for open worlds.

Navigation meshes (navmeshes)

A navmesh is a convex polygon soup covering walkable surfaces, generated from level collision. Agents path across polygon adjacency — far fewer nodes than a fine grid, naturally respecting slopes and stairs within bake rules. Unity, Unreal, Godot, and Recast/Detour all center on navmesh workflows for 3D action games. This is the default choice for most modern 3D titles.

Graph type	Best for	Watch out for
Grid	2D tile games, tactics, procedural roguelikes	Memory, diagonal corners, smooth paths
Waypoint	Rails, racing, heavily scripted levels	Manual upkeep, coverage gaps
Navmesh	3D action, open hubs, dynamic combat arenas	Bake time, agent radius tuning, vertical layers

A* search in plain terms

A* (A-star) is the workhorse shortest-path algorithm in games. It explores the graph outward from the start, always expanding the node that minimizes:

f(n) = g(n) + h(n)

g(n) — actual cost from start to node n (distance, terrain weight).
h(n) — heuristic estimate from n to goal (usually Euclidean or Manhattan distance).

When the heuristic is admissible (never overestimates true cost), A* returns an optimal path. In practice, games inflate h slightly for faster search at the cost of marginally longer routes — acceptable in 60 FPS budgets.

Optimizations you will see in shipping code:

Binary heaps or priority queues for the open set.
Node pooling — reuse search nodes instead of allocating per query.
Partial paths — if the goal is unreachable, return the closest node explored (useful for chase AI).
String pulling / funnel algorithm — post-process the polygon corridor into a straight polyline hugging corners.

For hundreds of agents querying every frame, batch requests, stagger updates across frames, or switch to cheaper algorithms for distant crowds.

Navmesh baking: walkable surfaces and agent dimensions

Baking converts static collision geometry into polygons tagged with area types (walk, jump, swim, crouch). Key bake parameters:

Agent radius and height — inflates obstacles so paths respect shoulder width; mismatched radius causes clipping or false “no path.”
Max slope and step height — stairs within step limit become walkable; steeper slopes get excluded or separate areas.
Voxel cell size — finer voxels capture tight doorways but increase bake time and polygon count.
Off-mesh links — manual edges for jumps, ladders, elevators, and teleporters between disconnected islands.

Bake whenever static geometry changes. In live-service games, partition levels into streaming chunks with portal connections so you rebake only the edited tile. Level designers should know bake limits — a doorway one voxel too narrow becomes a hard blocker for every AI in the scene.

Area costs and modifiers

Tag polygons with costs: mud slower than stone, cover preferable for stealth AI, danger zones avoided unless desperate. A* multiplies edge weights by area cost — same search, different tactical preferences. Dynamic modifiers (fire spreading, player-placed barricades) mark regions temporarily unwalkable or high-cost.

Following the path: steering and local avoidance

A polyline is not movement. The motor layer typically:

Picks the next corner or lookahead point on the path.
Steers toward it using seek/arrive behaviors with acceleration caps.
Runs local avoidance (RVO, ORCA, or simple separation) so agents do not stack on the same point.
Repaths when deviation exceeds a threshold or a dynamic blocker appears.

Pure path following without avoidance produces trains of enemies on identical routes. Pure avoidance without global paths produces wandering blobs that never reach objectives. Layer both: global planner every 0.5–2 seconds (or on events), local avoidance every frame.

Character controllers may need corner cutting disabled near ledges — the funnel algorithm assumes cylindrical agents; your capsule may need probe checks before sliding along navmesh borders.

Dynamic obstacles and destructible worlds

Static navmeshes do not know about a door the player just closed or a crate explosion. Common patterns:

Navmesh obstacles / carving — runtime boolean volumes subtract walkable area; engines rebake local tiles or use dynamic modifiers.
Physics-driven blockers — treat large moving objects as avoidance targets without rebaking; repath when LOS to goal is lost.
Door state components — toggle edge connectivity or off-mesh link activation instead of full rebake.

Budget repaths: a destroyed wall should invalidate paths once, not every agent every frame. Broadcast a NavDirty event; agents within a radius requeue planning.

Scale tricks: hierarchical paths and flow fields

When agent counts spike (tower defense swarms, battle royale circles), upgrade the stack:

Hierarchical pathfinding — coarse cluster graph for long routes, fine mesh search only near start and goal. Cuts search nodes by orders of magnitude.
Flow fields — precompute a direction vector per cell toward a goal; thousands of units read one field instead of individual A* runs. Ideal for single shared objective (capture point, exit gate). Rebuild field when goals move.
Path sharing — squad leader plans; followers use offset steering along the same corridor with separation.

Match algorithm to query pattern: occasional unique goals favor A*; horde toward one target favors flow fields.

Integration with AI and perception

Pathfinding is a service, not a brain. Behavior trees call MoveTo(Location) as a task node; success/failure feeds back into selectors (flank failed → fall back to ranged attack). Tie into perception: last known position becomes a path goal; lost targets clear the path and switch to search.

Combat strafing often disables strict path following — use short local probes and circle-strafe steering while keeping the navmesh for long repositioning. Stealth games need cover-aware costs: prefer shadow polygons, penalize lit floor during hide states.

Multiplayer and determinism

In authoritative server models, the server plans paths (or validates client requests) and replicates waypoints or velocity, not every micro-steer. Clients may predict movement for smoothness but snap on correction. Keep search deterministic where gameplay depends on it — same graph, same tie-breaking rule, fixed random seeds for crowd jitter.

Avoid server-side full rebakes every physics tick; batch dynamic carving and send delta updates. For large player counts, cap simultaneous repaths per tick and queue the rest — invisible lag beats a frame spike.

Performance budgets

Queries per frame — profile with worst-case combat; stagger AI tiers (boss every frame, grunts every 3–5 frames).
Polygon count — over-tessellated navmeshes slow funnel and ray tests; simplify in open plains.
Async planning — jobify A* on worker threads; apply results next frame with “thinking” animation if needed.
Early outs — straight-line LOS check before expensive search; if clear, skip graph entirely.
Memory pools — path requests from pooled buffers to avoid GC spikes on mobile and WebGL.

Common mistakes

Agent radius smaller than collision capsule — paths exist but body clips walls.
Repathing every frame — jittery motion and CPU waste; use deviation thresholds.
Ignoring off-mesh links — AI cannot use ladders or jumps players take for granted.
One navmesh for all creature sizes — spiders and tanks need separate agent types or area masks.
No partial path fallback — chase AI freezes when goal is behind a closed door instead of closing distance.
Skipping playtest on streamed chunks — seams between baked tiles create one-voxel gaps agents cannot cross.

Decision table: pick your navigation stack

Scenario	Recommended approach
2D tile roguelike	Grid A* + corner smoothing; optional jump-point search
3D action / RPG hub	Baked navmesh + funnel string pulling + RVO avoidance
RTS horde to one goal	Flow field + light separation
Rail shooter enemies	Waypoint splines; pathfinding optional
Destructible arena	Navmesh carving on events + throttled repath queue
Large open world	Hierarchical clusters + streaming chunk portals

Production checklist

Documented agent types — radius, height, slope, step per creature class.
Bake CI step — fail build if navmesh missing or doorways below min width.
Off-mesh links catalog — jumps, ladders, elevators wired to gameplay state.
Repath policy — deviation threshold, max frequency, partial path behavior.
Avoidance layer — tuned so squads spread without orbit deadlock.
Dynamic obstacle events — single broadcast, radius-limited invalidation.
Debug draw — polyline, search nodes, area costs visible in QA builds.
Stress test — 2× expected agent count at lowest target hardware.
Multiplayer authority doc — who plans, what replicates, correction rules.

Key takeaways

Plan globally, move locally — A* (or flow fields) plus steering/avoidance each frame.
Navmeshes are the default for 3D; grids win for tile-native games; waypoints for rails.
Agent radius and bake voxel size are design parameters — involve level art early.
Dynamic worlds need carving or connectivity toggles, not static-only bakes.
Performance is scheduling: stagger queries, pool memory, LOS early-outs.