Module 11 · Classical control

Pathfinding: A* and NavMesh

How "move toward the player" turns into graph search — and why navigation is a mesh of polygons rather than a grid of cells.

🏠 lab~15 min

The gist in 20 seconds

A* finds the shortest path through a graph by expanding nodes in order of f(n) = g(n) + h(n) — cost so far plus a heuristic estimate of what is left. If the heuristic is admissible (never overestimates), A* returns the optimum while expanding as few nodes as possible. Games don't walk on cells, they walk on a NavMesh — a mesh of convex polygons covering the walkable space; A* runs over it and path smoothing (string-pulling) takes out the zigzags.

How A* works

Dijkstra expands nodes by g(n) (distance from the start) in every direction. A* adds h(n) — an estimate of "how much is left to the goal" — and pulls the search toward the goal:

f(n) = g(n) + h(n) → expand the node with the smallest f

The key property is admissibility: if h never overestimates the true cost, the path is optimal. On a grid you use Manhattan distance (4-connectivity) or Euclidean/octile (8-connectivity). The closer h gets to the truth without exceeding it, the fewer nodes A* expands — in the limit h = true cost → you walk straight to the goal.

NavMesh — why not cells

A grid of cells is precise but expensive: an open field is thousands of nodes about nothing. A NavMesh covers the walkable space with a small number of convex polygons; inside a polygon you can walk in a straight line. A* runs over the polygon graph (dozens, not thousands), and string-pulling (the funnel algorithm) straightens the path instead of leaving a staircase through cell centers. That is why navigation in 3D games is almost always a NavMesh (Recast/Detour, the built-in navigation in Unreal/Unity/Godot).

🕹 Games to play — and what to notice

One question — "how do I get to the goal" — with different answers under different constraints, from "no search at all" to 3D voxels. For each: how it is done, and what to play to see it with your own eyes.

Pac-Man 1980 · simplest 2D, no A*

The ghosts don't build a path at all. At each junction every ghost greedily picks the direction that minimizes straight-line distance to its own target tile (Blinky targets Pac-Man's tile, Pinky aims 4 tiles ahead of him, Inky and Clyde have their own rules). One tile of lookahead, no reversing, no memory — O(1), because 1980 hardware allowed nothing more.

🎮 Play: fire up Pac-Man (any browser port). Corner the ghosts and watch them split into different directions at junctions — each has its own target. This is "pathfinding" with no path in it.

Tile-based A* 2D · grid

A uniform grid, 4/8-connectivity — exactly what the lab above does. Early RTS, roguelikes, tactics games: the map is known and static → the classical approach beats everything.

🎮 Play: open the A* lab and draw some walls — that is literally it. Or a classic like the first Warcraft / Heroes of Might & Magic.

Minecraft 3D · voxels

A* over blocks in 3D. Neighbors are "where you can step": a 1-block step up, a drop within the fall limit, a jump across a gap. Nodes are scored by a NodeEvaluator with penalties (malus): water and lava carry a huge cost and get routed around, fire/fences/doors have their own weights. The search is capped by a node budget (not the whole world) and throttled across ticks — otherwise 3D A* per mob would kill the server. Flying and swimming mobs use a volumetric variant instead of "standing on a block".

🎮 Play: in Minecraft, spawn a zombie or a pig and ring it with a lava moat or a fence — watch it route around the danger and climb block steps. Dig a 2–3 block pit and it gets stuck (jump height limit / node budget). That is 3D pathfinding in your hands.

3D shooters and RPGs NavMesh

In a continuous 3D world voxel A* is far too expensive. You bake a NavMesh (polygons of walkable surface, Recast), run A* over the polygon graph and add the funnel for a smooth path. Minecraft differs because its world already is a grid of blocks — voxels are the natural fit there.

🎮 Watch: in a Godot/Unity navigation demo (or any game with a dev console) turn on navmesh debug drawing — you will see the walkable polygons laid over the level and the funneled path.

RTS at scale thousands of units

A* per unit does not survive hundreds of them. Supreme Commander and StarCraft II use flow fields (one field computed from the goal → a direction in every cell, everyone follows it) plus local collision avoidance (boids / ORCA). One search per goal instead of one search per unit.

🎮 Play: in StarCraft II, or any RTS, select 50+ units and send them across a narrow bridge — you will see them flow as one stream and jostle each other rather than each computing its own route.

Deep end: why A* is optimal — and where consistency comes inskippable

Admissibility: h(n) ≤ h*(n) — the heuristic never overestimates the true cost to the goal. Claim: A* (tree search) with an admissible h returns an optimal path.

Proof sketch

Suppose A* is about to return a goal G₂ with g(G₂) > C* (suboptimal; C* is the optimal cost). At that moment the frontier contains a node n on an optimal path, for which

f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*

(the first step is admissibility, the second is that n lies on an optimal path). But A* picked G₂ with f(G₂) = g(G₂) > C* ≥ f(n) — so it was obliged to expand n before G₂. Contradiction. ∎

Admissibility vs consistency

Consistency (monotonicity): h(n) ≤ c(n,n′) + h(n′) for every edge. Consistency ⇒ admissibility, and ⇒ f is non-decreasing along a path ⇒ when A* expands a node its g is already optimal ⇒ graph search with a closed set never needs to reopen nodes. A heuristic that is admissible but not consistent may require reopening closed nodes, otherwise optimality is lost. So you aim for a consistent h (Manhattan on 4-connectivity, octile/Euclidean on 8-connectivity — all consistent).

Why a sharper heuristic is provably cheaper

A* expands every node with f(n) < C* and none with f(n) > C*. If h₂ ≥ h₁ everywhere (both consistent), h₂ dominates: {f₂ < C*} ⊆ {f₁ < C*} → it expands no more nodes. In the limit h = h* only the nodes on an optimal path get expanded.

Weighted A* — trading optimality for speed

With f = g + w·h (w ≥ 1) the search is greedier and faster, but suboptimal by a bounded amount: cost ≤ w·C*. One knob spans the spectrum: w=0 → Dijkstra (g only), w→∞ → greedy best-first (h only), w=1 → A*.

Deep end · engineering: pathfinding in production at scaleskippable

Time-slicing: budget N searches per frame and spread the queue across frames — otherwise you get a spike the moment 50 units request a path at once.
Hierarchy (HPA*): a coarse graph of regions plus local search inside them — orders of magnitude cheaper than flat A* on large maps.
Local avoidance ≠ the global path: A* builds the route, but "don't walk into your neighbors" is a separate layer (ORCA/boids/steering). Every other junior conflates the two.
The NavMesh is baked at build time (Recast); the runtime only queries it; dynamic obstacles → partial re-bake or local avoidance.
Cache paths for common routes; a full recompute every frame is an antipattern.

Analogy

Dijkstra is a flood: water spreads equally in every direction until it reaches the goal. A* is water on a slope toward the goal: the heuristic tilts the surface, so the flow runs straighter and covers less ground. A NavMesh is a map of districts instead of a map of every sidewalk: inside a district you cut straight across, and you plan the route district by district.

Why it matters

Pathfinding is the most invisible AI there is: the player notices it only when it breaks (an NPC wedged in a corner). Understanding heuristic admissibility, and why a NavMesh is cheaper than a grid, is the difference between "it works" and "it works for 200 units in an RTS at 60 FPS".

🔁 Beyond games — where this transfers

A* is informed search (branch-and-bound with a heuristic), and a flow field is "one computation for many" (amortization). Both transfer widely:

Optimization / search: A* is everywhere in planning, routing and compilers (register allocation is graph search); the heuristic is the lower bound in branch-and-bound.

ML / AI: beam search in LLM decoding is the same informed tree search; MCTS (AlphaGo) is search plus a learned value heuristic; "when A* beats RL" is "when the classical approach beats ML". Flow field = batching: one solve from the goal for all agents ≈ one forward pass per batch instead of per example — the basis of efficient inference.

Backend / systems: shortest paths in service graphs, packet routing; time-slicing a search is the latency budget of a service.

The principle: don't compute per agent when you can compute once for all of them; and reach for the expensive tool only when the cheap one fundamentally cannot cope.

🏠 Lab — A* live

An interactive lab with no code: draw walls, drag the start and goal, switch between Dijkstra / A* / Greedy / Weighted — and watch the expanded-node counter. Heuristic dominance, but seen rather than proved. Open the lab →

Best moment: compare the node counts of Dijkstra and A* on the same path — A* is several times leaner. If you want it in code, A* vs Q-learning is written up in labs/lab-11b-astar-vs-rl/.

🔧 Run it and poke at it — on your home machine

What to play is above (🕹). This part is for people who want to get inside the engine:

🔧 Poke at it (debug) ~40 min, Godot

Open Godot and the NavigationServer / Navigation2D demo. Place an agent, a goal and obstacles, then turn on navmesh and path debug drawing. Move an obstacle at runtime — you will see the path recomputed. Break it: remove the mesh connectivity and the agent stops dead.

🧪 Test it (with QA eyes) ~15 min

Hunt for the classic navigation bugs: getting wedged in corners, jitter along an obstacle edge, cutting through thin walls, a crowd locking itself in a doorway. That is the standard QA checklist for AI navigation.

Checklist: saw flow-field behavior in a crowd; turned on navmesh debug in Godot; found at least one navigation bug.

Connections

foundation

FSMs and Behavior Trees — the "move to target" action in a behavior tree calls A* under the hood.

contrast

Classical vs ML — A* vs RL on navigation: with a known map, A* wins outright.

Questions worth asking

Is the Manhattan heuristic still admissible on an 8-connected grid?

No. Diagonally the real cost of a move is ≈1.41 (or 1 under Chebyshev movement), while Manhattan counts it as 2 — it overestimates → inadmissible → A* may return a path that is not the shortest. On 8-connectivity you use octile distance (or Euclidean) — both admissible and consistent. The classic trap of "works, but occasionally cuts suboptimally".

Are A*, Dijkstra and greedy best-first really one algorithm?

Yes, points on the scale f = g + w·h: w=0 → Dijkstra (cost so far only; optimal, but it floods the map), w→∞ → greedy (heuristic only; fast, not optimal), w=1 → A*. Turning the weight slides you between "reliable and slow" and "fast and approximate" (see the deep end on weighted A*).

JPS (Jump Point Search) — why can you "jump" over nodes on a grid?

On a uniform grid huge numbers of paths are symmetric (same cost, different move order). JPS kills the symmetry: instead of expanding every neighbor it "jumps" along a direction until it hits a point with a forced neighbor. The result is identical to A*, but the open list holds an order of magnitude fewer nodes. Uniform-cost grids only — it does not apply to a NavMesh.

Is a flow field for 500 units still A*?

No, it inverts the problem: you solve one single-source shortest path from the shared goal to every cell (Dijkstra/BFS, or the eikonal equation for smooth fields) → a direction field that every unit follows in O(1). A* per unit = O(units × search); a flow field = O(search) + O(units). That is why an RTS with thousands of units walks a field rather than an A* per unit.

Why is RL almost never used for navigation in shipped games?

A* gives you the optimum immediately, is deterministic and debuggable in O(E log V); RL has to be trained, is non-deterministic and falls apart on unseen maps. Paying with training where an exact polynomial algorithm exists makes no sense. RL earns its place only when there is no model or map — continuous control with dynamics, partial observability.