Unit Pathfinding

Overview

Getting from A to B, intelligently. Pathfinding seems simple until hundreds of units need simultaneous routes through dynamic terrain while avoiding each other. RTS games pushed pathfinding algorithms to their limits—A* became industry standard, flow fields handled mass movement, and hierarchical approaches managed computational cost. Bad pathfinding ruins otherwise excellent games.

Fast facts

• Core algorithm: A* (A-star).
• Challenge: Scale and performance.
• Modern approach: Flow fields, hierarchical.
• Failure mode: Units stuck, wrong routes.

A* algorithm

Component	Function
Open list	Nodes to evaluate
Closed list	Evaluated nodes
Heuristic	Distance estimation
Cost function	Path optimisation

RTS challenges

Problem	Difficulty
Unit count	Hundreds simultaneously
Dynamic obstacles	Moving units
Terrain variation	Different costs
Formation keeping	Group movement

Flow fields

Advantage	Application
Shared calculation	Mass movement
Scalability	Any unit count
Smooth paths	Natural movement
Pre-computation	Performance gain

Hierarchical pathfinding

Level	Function
Strategic	Region navigation
Tactical	Local movement
Reactive	Immediate avoidance

Common failures

Issue	Player experience
Stuck units	Frustration
Suboptimal routes	Inefficiency
Traffic jams	Bottlenecks
Formation breaking	Tactical loss

Notable implementations

Game	Achievement
Age of Empires II	Smooth group movement
StarCraft II	Responsive micro
Supreme Commander	Thousands of units

See also

• Age of Empires
• Total Annihilation
• RTS Genre