Chapter 15
Subgoal Graphs for Fast Optimal Pathfinding
Tansel Uras and Sven Koenig
15.1 Introduction
Paths for game agents are often found by representing the map that the agents move on as a graph and using a search algorithm, such as A*, to search this graph. Pathfinding in games needs to be fast, especially if many agents are moving on the map. To speed up path planning, maps can often be preprocessed before games are released or when they are loaded into memory. The data produced by preprocessing should use a small amount of memory, and preprocessing should be fast if it is performed at runtime.
In this chapter, we present subgoal graphs, which are constructed by preprocessing maps that are represented as grids. Subgoal graphs use a small ...
Get Game AI Pro 2 now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.