Research Publications

Real-time strategy (RTS) games often feature a wide number unit types for the player to control. One of my favourite titles from the past, Westwood's seminal Red Alert, had many classes of differently sized units: small infantry soldiers, medium-sized Jeeps and large tanks. In Red Alert 3, the most recent incarnation of the series, the diversity is increased even further by the introduction of units with terrain-specific movement capabilities. From a pathfinding perspective this introduces an interesting question: how can we efficiently search for valid routes for variable-sized agents in rich environments with many types of terrain? Hierarchical Annotated A* (HAA*) is a path planner which is able to efficiently address this problem by first analysing the terrain of a game map and then building a much smaller approximate representation that captures the essential topographical features of the original. In this article I want to outline the two major aspects of HAA*. First, I’ll discuss how one can analyse a grid map to automatically extract clearance-related topographical information. Second, I’ll explain how HAA* is able to use this information to build space-efficient abstractions that allow a range of agents with different sizes and terrain traversal capabilities to very quickly find a high quality path through a static multi-terrain environment.