A Comparison of High-Level Approaches for Speeding up Pathfinding

Most games being shipped today use some form of high-level abstraction such as a navmesh or waypoint graph for path planning. These structures can generally be represented in a form which is compact enough to meet the tight memory con-straints in a game. But, when such a graph grows too large, finding paths can still be a complex task. This challenge was faced in Dragon Age: Origins and solved by adding an ad-ditional level of abstraction. In the last few years a variety of novel approaches have been developed for finding opti-mal paths through graphs with specific design applications for road networks. Currently these techniques cannot be fea-sibly applied to the lowest detail of movement possible in a game map, but can be applied to the high-level abstractions which are commonly found in games. In this paper we de