Clearance-based pathfinding and hierarchical annotated A* search

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, Westwoods 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 (Figure 1). 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?