Source metadata
- Type: Academic anthology / professional handbook
- Editor: Steve Rabin
- Publisher: CRC Press / Taylor & Francis, 2020
- ISBN: 978-0-367-15111-9 (paperback)
- Derived from: Game AI Pro volumes 1–3 (2013–2017), articles selected and republished
Key takeaways
- A* implementations can vary by two orders of magnitude in speed depending on architectural choices — heuristic quality is the most important single factor (Rabin and Sturtevant, Ch. 1).
- The three primary search space representations are grids, waypoint graphs, and navigation meshes — each has distinct trade-offs in memory, plan quality, smoothing, and dynamic modification (Sturtevant, Ch. 2).
- Context Steering (Fray, Ch. 14) replaces traditional steering behaviour vectors with 1D “context maps” (danger map + interest map), guaranteeing collision avoidance while keeping individual behaviours small and stateless.
- JPS+ (Rabin and Silva, Ch. 10) preprocesses a uniform-cost grid to store jump-point distances, achieving up to 116× speedup over traditional A* while remaining optimal.
- Theta* (Nash and Koenig, Ch. 12) allows any-angle pathfinding by propagating paths along grid edges without constraining paths to grid edges — paths are approximately 4% shorter than A* with minimal implementation change.
- Flow field pathfinding (Emerson, Ch. 7; Pentheny, Ch. 8) amortises path cost across many agents sharing a goal — O(1) per additional unit once the field is built.
- ORCA (Sunshine-Hill, Ch. 22) resolves multi-agent collision avoidance through a velocity-space linear programming approach; agents each independently find the nearest collision-free velocity.
- Path smoothing using convex optimisation (Langerak, Ch. 23) produces globally smooth paths that respect start/goal facing direction and obstacle clearance simultaneously.
- Precomputed hierarchical lookup tables (Gravot et al., Ch. 4) enable 4-microsecond path queries for Final Fantasy XIV’s MMO servers, at the cost of requiring static world geometry.
- Formation movement using steering circles (Bjore, Ch. 5) generates paths that arrive at a target with a specified orientation, respecting the formation’s minimum turn radius.
Notable claims
“Given hundreds of students… the fastest implementations are 2 orders of magnitude faster than the slowest implementations (a 100× difference).” — Rabin and Sturtevant, Ch. 1
“By altering the weight [on the heuristic], we can tune how A* behaves. If the weight is zero, then the formula reduces down to just g(x), which is identical to the Dijkstra search algorithm.” — Ch. 1
“Context steering behaviors are small and stateless and guarantee any desired movement constraint. When used to replace steering behaviors on the game F1 2011, the codebase shrunk by 4000 lines, yet the AI were better at avoiding collisions, overtaking, and performing other interesting behaviors.” — Fray, Ch. 14
“Theta* is approximately two to three times slower than A* with the octile distance heuristic [but] finds paths that have nearly the same length as the shortest paths in the continuous environments without the need for postprocessing techniques.” — Nash and Koenig, Ch. 12
“[JPS+] In this example, JPS+ was 116× faster than traditional A*, while remaining perfectly optimal.” — Rabin and Silva, Ch. 10
“Flow fields can be thought of as a [pathfinding] system where the information is amortised across all agents — constant complexity per agent once the field is built.” — Pentheny, Ch. 8 (paraphrase)
Relevance
This source directly informs:
| Topic | Pages |
|---|---|
| A* algorithm, heuristics, optimisations | pathfinding-algorithms |
| Search space representations (grid/navmesh/waypoint) | pathfinding-algorithms, navigation-mesh-construction, unity-navmesh |
| Navigation mesh construction algorithms | navigation-mesh-construction, unity-navmesh |
| Context Steering | context-steering |
| Flow field pathfinding | steering-behaviours |
| Crowd simulation, formation movement | steering-behaviours, npc-performance-at-scale |
| RVO/ORCA collision avoidance | context-steering, steering-behaviours |
| Path smoothing | pathfinding-algorithms |
| Precomputed pathfinding | npc-performance-at-scale |
Open questions raised
- At what agent count does flow field pathfinding become cheaper than individual A* per agent in Unity?
- Does Theta* have a Unity NavMesh analogue, or must it be implemented from scratch on a custom grid?
- How does Unity’s NavMesh local avoidance (ORCA variant) differ from the full ORCA described in Ch. 22?
- Context maps are described in 2D (racing and open-plane) — how well do they extend to 3D environments?
Links
- pathfinding-algorithms — pages created from Ch. 1, 2, 10, 12, 25, 26
- navigation-mesh-construction — pages created from Ch. 3, 4
- unity-navmesh — engine-facing reference for Unity’s NavMesh workflow
- context-steering — page created from Ch. 14
- steering-behaviours — updated with context steering reference, formation movement, RVO
- npc-performance-at-scale — relates to Ch. 4 (precomputed), Ch. 13 (congestion maps)