Unit Pathfinding

Unit pathfinding works out how a game character or vehicle can reach a destination. It is only part of navigation: the unit must also follow that route, respond to obstructions and avoid becoming stuck among other moving units.¹²

Routes have costs

A route can be shortest in distance without being cheapest to travel. Reviewing SSI’s RDF 1985 for the Apple II in September 1983, Neil Shapiro described automatic movement across its hexagonal map. The computer chose a route according to terrain movement costs rather than simply counting the fewest hexes.³

A pathfinder can represent a map as a graph: locations connected by permitted moves. A grid is one possible graph, not a requirement. Connections can carry costs for distance, terrain or other movement rules.¹

Dijkstra’s algorithm searches by the accumulated cost from the start. A* adds an estimate of the remaining cost to prioritise promising routes. With a suitable implementation and an estimate that never exceeds the true remaining cost, A* can find a least-cost path. That guarantee concerns the supplied graph and costs; it does not guarantee that a crowd will move smoothly.¹

A patrol is a different job

Andrew Braybrook’s Paradroid development diary describes hand-designed patrol routes. On 19 June 1985 he recorded junction coordinates and valid directions, then entered them into the assembler. By 27 June the robots followed their courses, paused at junctions and waited for doors.⁴

That is evidence for authored patrol behaviour in this game. It is not evidence that most 8-bit games used the same system, or that following stored routes requires no algorithm. Choosing where an enemy should patrol and finding a route to a destination specified by the player are different design problems.

Why units still get stuck

Loyd Case’s October 1998 Computer Gaming World review of Tribal Rage criticised units which became stuck beside apparently clear paths. The symptom matters to the player regardless of whether the underlying fault is route search, collision handling or movement along the route.⁵

EA’s released Command & Conquer: Remastered Collection source shows some of the extra work. In the Red Alert vehicle code, a failed route search can lead to stopping near enough to the target rather than repeatedly trying to occupy its exact location. Other logic asks friendly temporary obstructions to move aside. These are explicit movement decisions around the route finder.²

Developers also replaced the search itself. In Edge’s February 1999 AI feature, Westwood programmer Bret Ambrose said Tiberian Sun had a new pathfinding implementation while retaining and extending other unit systems. That is a development account, not proof that every navigation problem disappeared.⁶

See also

• Command & Conquer
• StarCraft
• Age of Empires
• Paradroid
• Enemy design
• Ghost AI

Footnotes

1. Amit J. Patel, “Introduction to the A* Algorithm”, Red Blob Games, first published 2014 and subsequently updated. An original illustrated implementation guide; especially map representation, movement costs and the limits of graph search. ↩ ↩² ↩³

2. Electronic Arts, Command & Conquer: Remastered Collection, REDALERT/DRIVE.CPP, branches around Basic_Path, CloseEnoughDistance and friendly temporary blockages. This is the published remaster source, not a claim of byte-for-byte identity with the original executable. ↩ ↩²

3. Neil Shapiro, “RDF 1985: Invade the Persian Gulf!”, Electronic Games, September 1983, pp. 76–80, automatic movement discussion on p. 78. The review establishes the observed feature, not the underlying algorithm’s identity. ↩

4. Andrew Braybrook, “Birth of a Paradroid”, part 3, ZZAP!64 development diary reproduced by Codetapper, entries for 19 and 27 June 1985. ↩

5. Loyd Case, Tribal Rage review, Computer Gaming World 171, October 1998, “Star-Cross’d Rage Incubates”. ↩

6. Edge 68, February 1999, AI feature, printed p. 63, interview with Bret Ambrose. ↩