Unit Pathfinding
Navigation intelligence
How a game moves a unit from A to B on its own. Wargames were finding the cheapest route across terrain by 1983, Paradroid ran its robots on hand-keyed patrol routes, and by the late 1990s the 'pathfinding problem' was the standing complaint against real-time strategy.
Getting from A to B on the machine’s own initiative. A unit the player has told to go somewhere has to work out a route around walls, trees, water and every other unit trying to do the same, and it has to do it fast enough that nobody notices. In turn-based wargames the computer had time to think; in real-time strategy it did not, and “the pathfinding problem” became the genre’s standing complaint.
Fast facts
- Automatic routing by movement cost: in SSI’s RDF 1985 (1983) the player could hand a unit to the computer, which took “the shortest route (in terms of the movement costs needed to enter various types of terrain)”.
- Pre-set routes instead of search: Andrew Braybrook’s Paradroid (1985) ran its robots on patrol routes and junctions keyed in by hand, packed three bytes to one.
- The complaint: by 2004 Computer Gaming World called the “pathfinding problem” one of the oldest clichés in game reviewing, “a cliché because so few people do it right”.
- The fix as a selling point: Ensemble, Blizzard, Westwood, Bungie and Cavedog all advertised or patched their pathfinding between 1998 and 1999.
Patrol routes before search
On an 8-bit machine the cheap answer was not to search at all. Braybrook’s Zzap!64 diary for Paradroid records the robots’ movement being designed as a table rather than an algorithm. On 6 June 1985 a colleague suggested “a neat way of compressing three bytes of information into one”, which “gives me a lot of patrol routes and junctions”. On 19 June he “worked out some lively-looking routes for patrolling robots to zoom about on, and marked them on my maps”, walked his own robot round to every junction to note the coordinates, and “keyed the points and valid directions from them into the assembler”. By 27 June the robots “pause at junctions as if they are looking around, then move off”, and wait for doors to open before passing through them. The table was small enough that the memory it saved later paid for the title screen.
The same shape — a fixed network of waypoints, with a choice made at each junction — is what most arcade and action games of the period used, and it is why enemies in them run on rails. See enemy design and ghost AI.
The computer finds the route
Wargames were the first games that needed the computer to find a route for the player rather than for its own pieces. Reviewing SSI’s RDF 1985 for Electronic Games in September 1983, Neil Shapiro described the choice: “On the hexagonal grid, you can move in six directions with the press of a key. Or, you can automatically move a unit by instructing the computer what area of the map it should move toward by taking the shortest route (in terms of the movement costs needed to enter various types of terrain).” Cost-weighted shortest paths were ordinary computing by then — the same month, 80 Micro was reviewing a TRS-80 business package whose “Program Unit III.5: Minimum Distance or Cost Path” used Dijkstra’s algorithm on a distance matrix — and a turn-based game could afford to run one per move.
The RTS pathfinding problem
Real-time strategy took away the time. Dozens of units, each ordered somewhere, each needing a route through terrain that the other units were also moving across, on a mid-1990s PC. The result was a reviewer’s vocabulary. In September 1996 Computer Gaming World reported that Eidos’s Total Mayhem patch “significantly upgrades your units’ pathfinding” to fix “cyborgs getting stuck behind walls and trees”. Its April 1997 review of Blood & Magic found “a horrible unit pathfinding AI. Your troops will bump into each other and even lose their way”. Loyd Case on Tribal Rage in October 1998: “units routinely get hung up only a couple of pixels to one side of an obvious path”. PC Gamer’s September 1997 feature on Dark Reign had Auran listing what to fix from Warcraft II — “Better unit pathfinding. Include massive range of user definable waypoints to help.” Sierra’s own magazine explained SWAT 2 to its readers as having “three main types of AI … pathfinding, strategic, and unit”.
By 2004 the magazine was calling it “one of the oldest clichés in game reviewing … a cliché because so few people do it right”, and noting the standard workaround: “Normally, you can work around bad pathfinding by baby-sitting your units.” In 2005 it was “the never-ending RTS complaint of ‘bad pathfinding’”, illustrated by Empire Earth II’s battleships.
Developers fix it
Because the complaint was so common, fixing it became something to announce. In March 1998 Computer Gaming World reported that Ensemble “has completed a patch for Age of Empires that greatly enhances AI and unit pathfinding”, and that StarCraft had slipped to January 1998 because “some minor tweaks in unit path-finding and AI were apparently needed. Blizzard admitted as much”. Rise of Rome, previewed that October, promised that “pathfinding has been improved, and, in fact, there are different options for pathfinding now in the game settings”. Bungie’s Myth II was to have “better pathfinding so formations won’t get tangled up”.
Mark Terrano told the magazine in January 1999 that Age of Empires II’s AI was being rewritten so that “units will be smart enough to find their way to any accessible location”, and that “all units will have equal pathfinding, so the computer player won’t have the upper hand” — an admission that the computer player’s units had previously found routes the player’s could not. The next month Westwood’s Bret Ambrose told Edge that in Tiberian Sun the pathfinding had “been completely ripped out and replaced with superior implementations” while other systems were kept from earlier Command & Conquer games. By September 1999 Edge could write of Total Annihilation: Kingdoms that “the perennial RTS pathfinding bug is practically eradicated”.
How it works
The general approach behind all of these is a search over a grid. Each cell carries a cost to enter — open ground cheap, forest or hills dear, water or walls impassable — and the search expands outward from the unit, always extending the cheapest route found so far, until it reaches the destination. With a good estimate of the remaining distance the search can be steered towards the goal rather than flooding the whole map, which is what makes it fast enough to run for many units at once. The hard parts are the ones the reviews describe: other units are obstacles that move, a route that was clear when it was planned can close before the unit arrives, and a group ordered to the same place will queue, jam and wander unless the game handles formations separately from the search.