Pathfinding in games explained

Pathfinding vs steering vs collision

Three systems often get conflated. Keep them separate:

• Pathfinding — compute a polyline or waypoint list through static (or slowly changing) obstacles. Output is a plan, not motion.
• Steering / locomotion — follow the plan with velocity, acceleration limits, and animation blending. Handles "how do I move along this curve smoothly?"
• Collision detection — detect when the agent's body overlaps geometry during movement; triggers replans, slides along walls, or damage events.

A common pipeline: pathfinder returns waypoints, a steering behavior (seek, arrive, obstacle avoidance) moves the entity, collision checks catch drift from dynamic obstacles the planner did not know about, and a replan fires when the route is blocked. In an entity component system, store the current path on a PathComponent, advance waypoints in a movement system, and let a separate collision system raise "path blocked" events.

Representing walkable space as a graph

Every pathfinding algorithm searches a graph: nodes (places you can stand) and edges (legal moves between them, each with a cost). How you build that graph dominates both quality and performance.

Grid maps

Tile-based games rasterize the world into cells. Each open cell is a node; edges connect to four or eight neighbors. Grids are easy to author, serialize, and debug — paint walls on a layer, run A*, done. Downsides: memory grows with map area, diagonal movement needs careful cost tuning, and units wider than one tile need clearance checks (mark a cell blocked if any overlapping tile is solid).

Navigation meshes (navmeshes)

A navmesh is a polygonal partition of walkable floor. Nodes are convex polygons (or their centers); edges are portals between adjacent polygons. Fewer nodes than a fine grid on large open areas, naturally supports arbitrary floor shapes, and handles agent radius via mesh erosion at bake time. Unity, Unreal, and Godot ship navmesh bakers; browser games often precompute offline or use Recast-style tools. Trade-off: dynamic obstacles require carving holes or local grid overlays.

Waypoint graphs and visibility graphs

Hand-placed nodes at doorways and corners work for small levels. Visibility graphs connect nodes that see each other — optimal for sparse environments but expensive to build. Most production titles use grids for 2D tile games and navmeshes for 3D levels.

A* search step by step

A* maintains two scores for each node n:

• g(n) — actual cost from the start to n (sum of edge weights).
• h(n) — estimated cost from n to the goal (the heuristic).
• f(n) = g(n) + h(n) — priority for the frontier.

The algorithm keeps an open set (nodes to explore, ordered by lowest f) and a closed set (nodes already expanded). Pseudocode sketch:

1. Initialize open set with the start node; g(start) = 0.
2. While open set is not empty, pop the node with smallest f.
3. If it is the goal, reconstruct the path by following parent pointers backward.
4. For each neighbor, tentative g' = g(current) + edge_cost.
5. If g' improves the neighbor's recorded g, update parent, set g and f = g + h, and enqueue the neighbor.

Use a priority queue (binary heap) for the open set — O(log n) inserts and pops. Store g scores in a hash map keyed by node ID; grid cells can use flat arrays indexed by y * width + x for cache friendliness. Cap expansions per frame in real-time games: spread a heavy search across multiple ticks or run it on a background thread and consume the result when ready (watch thread safety with world mutations).

Heuristics: steering search without breaking optimality

The heuristic is what makes A* fast. A perfect heuristic would be the true remaining distance — then A* goes straight to the goal. Approximations trade accuracy for speed, but must obey rules:

• Admissible — never overestimates true cost. Guarantees A* finds an optimal path (if one exists).
• Consistent (monotonic) — for every edge (n, n'), h(n) ≤ cost(n, n') + h(n'). Implies admissibility and avoids re-expanding nodes unnecessarily.

Common heuristics on grids

• Manhattan — |dx| + |dy| times step cost. Admissible for 4-directional movement without diagonals.
• Euclidean — straight-line distance. Admissible when diagonal moves cost at least the Euclidean segment length.
• Octile / diagonal — for 8-directional grids with cost 1 for cardinals and √2 (or 1.414) for diagonals: compute minimum diagonal steps plus remaining cardinal steps. Matches the true shortest path cost on uniform grids and dramatically reduces explored nodes vs Manhattan on open maps.

Weighted A* uses f = g + w·h with w > 1 to favor speed over optimality — useful for crowds of NPCs where "good enough" paths look fine. Tie-breaking — adding a tiny ε·h bias toward the goal — reduces zig-zag expansions on equal-f fronts.

When to use BFS, Dijkstra, or A*

All three are related; picking the wrong one wastes CPU:

• Breadth-first search (BFS) — uniform edge cost of 1. Finds fewest hops, not fewest meters. Perfect for unweighted grids ("how many rooms away?") and flood-fill reachability.
• Dijkstra — handles varying edge weights, no heuristic. Equivalent to A* with h = 0. Use when no useful estimate to the goal exists, or when finding distance from one source to all nodes (tower placement range, influence maps).
• A* — Dijkstra plus a goal-directed heuristic. Best default for point-to-point queries on maps with obstacles. Explores far fewer nodes than Dijkstra on large open areas.

Jump Point Search (JPS) prunes symmetric paths on uniform-cost grids — a big win for strategy games with hundreds of units. Hierarchical pathfinding precomputes cluster-level routes (path between regions) and refines locally; MMORPGs and RTS titles use this to amortize search cost.

From jagged paths to smooth movement

Grid A* returns a staircase of cell centers. Players notice. Post-process:

• String pulling / funnel algorithm — on a navmesh, walk the corridor between portals and pull the path tight against corners.
• Line-of-sight shortcuts — on grids, skip intermediate waypoints if a ray from the current point to a farther waypoint never crosses blocked tiles (Bresenham or grid raycast).
• Bezier or spline smoothing — fit curves for visual polish; verify clearance so the smoothed arc does not clip through walls.

Dynamic obstacles (other players, moving crates) invalidate segments. Lightweight games re-run A* only when blocked; larger titles maintain local avoidance (ORCA, RVO) for crowds while the global path stays coarse.

Performance checklist for real-time games

1. Reuse data structures — pool priority queues and clear visited arrays between searches instead of allocating fresh each query.
2. Limit simultaneous searches — queue path requests; stagger NPCs so fifty enemies do not all expand on the same frame.
3. Cache paths — identical start/goal on a static map can memoize; invalidate cache entries when terrain changes.
4. Coarser graphs for distant agents — low-detail navmesh or cluster graph for far-away units; refine when they approach the player.
5. Compile hot loops to WASM — A* inner loops benefit from WebAssembly on the web when hundreds of agents path per tick.
6. Profile expansions, not just wall time — if nodes explored spikes, fix the heuristic or graph resolution before micro-optimizing the heap.

Common pitfalls

• Inadmissible heuristics — overstimating distance makes A* skip the true shortest route. Diagonal movement with Manhattan h is a frequent bug.
• Forgetting agent size — a one-tile-wide corridor is not walkable for a two-tile-wide boss unless you bake clearance into the graph.
• Replanning every frame — thrashes CPU and makes NPCs jitter. Replan on timers, on collision events, or when the goal moves significantly.
• Floating-point navmesh portals — tiny gaps between polygons trap agents; snap endpoints and validate adjacency at bake time.
• Ignoring dynamic layers — doors, elevators, and destructible walls need events that mark graph edges blocked or open.

Key takeaways

• Pathfinding plans routes; steering and collision handle motion and contact — keep the pipeline modular.
• Grids suit tile games; navmeshes scale better on large 3D floors with irregular geometry.
• A* is the default point-to-point algorithm: prioritize by f = g + h with an admissible heuristic.
• Octile heuristics on 8-connected grids and path smoothing after search dramatically improve both speed and appearance.
• Cap searches per frame, cache static routes, and escalate to hierarchical or JPS methods when unit counts grow.

Related reading

• Collision detection in games — overlap tests that trigger path replans
• Game loop and frame timing — scheduling AI work inside the frame budget
• Entity component system (ECS) — storing paths and movement as components
• WebAssembly (WASM) — accelerating hot pathfinding loops in the browser