Hierarchical A Star

Hierarchical A Star

http://webdocs.cs.ualberta.ca/~kulchits/Jonathan_Testing/publications/ai_publications/jogd.pdf

Although A-Star is widely used, it can be really slow for real-time applications such as games where even computation times of 50-100 milliseconds could adversely affect the performance. The main issue arises from the tremendous amount of nodes that need to be processed. The number of nodes increases as the square of the distance (O(n^2)). Hence it becomes very important to cut down the number of nodes to even make pathfinding feasible. That is where Hierarchical pathfinding can help us.

The idea is that instead of worrying about the minute details at all levels, we only worry about the minute details where necessary. Imagine you wanted to go to New York from Boston. You won't really concern yourself with the street level information at all the roads. You only need to know how to reach the Highway from New York. From there, you stay on the Highway until you reach Boston. From the Highway, you then need to know how to reach Boston. Hierarchical Pathfinding works in almost the exact way. We use abstractions of lower-level details and use them whenever we feel like we need not concern ourselves with all the minute details.

The problem of pathfinding essentially reduces to this:

• Start node: Within the block containing the start node, find the optimal path to the borders of the block.
• Search at the block level (100 × 100 blocks) for the optimal path from the block containing the start node to the block containing the goal node.
• Goal node: Within the block containing the goal node, find the optimal path from the border of the block to the goal.

We could further build upon this idea and use abstractions at different levels, where we move up the abstraction levels when we're moving from the start node and finally back down as we get closer to the goal node. We won't get the shortest path all the time, but the near-optimal paths are more than enough.

The implementation of Hierarchical Pathfinding can be really tricky. To represent the nodes, we have a NavGraphSystem, with WalkableBlocks marked on it. The different levels of abstraction that we use include Sweeps, Floors, and Regions. These will be explained in detail in the following pages.