Dynamic HPA*: Part 1

My current personal project uses A* for AI path-finding, but I recently discovered that under certain conditions, the algorithm would become a performance bottleneck. Here’s what what went wrong, and the solution I used to solve it.

The game project uses traditional A* path-finding to navigate AI characters through a 2D grid-based game world. Pretty standard stuff for games and for the most part it worked great! A* is reasonably fast, always finds the optimal path, is easy to understand, and can be time-sliced without much effort. There is a good reason it is the de-facto graph solving algorithm in the game industry.

For those unfamiliar with A*, here is a explanation of how it works:

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

Meaning, as it traverses from one Node to another, it is constantly tracking how much it “costs” to reach this Node from the start Node, and makes a guess at how much it will cost to get to the end Node (the Heuristic). By adding those 2 costs up, it can make an educated guess at what the total cost of that path will be for the entire path if it continues along this route. With that estimation, it can then compare multiple Nodes to determine which is the best choice as it traverses the Graph searching for the destination. By constantly choosing the expected “lowest cost” Node, it usually finds the destination very quickly.

“Usually” being the key word…

I ran into a scenario where A* starts to breaks down:

The starting position is the Blue + sign and the destination is the Pink x. The black squares are walls which the path cannot cross. Here is what the solved path would look like, shown here in Green.

The issue is that for the path to be solved, it needs to start going further and further away from the destination; it has to get worse before it can get better. This is exactly the opposite of how A* tries to function. It will always trying to move to Nodes that have a lower estimated total cost, leaving higher cost Nodes for later.

Let’s look at that solved path again, but this time color coded to show a rough idea of the cost of each node in the path. Green being cheap, and red being expensive.

Again, this is just a rough approximation. As you can see though, once the path begins moving left of the destination (the pink X), the cost starts rising, because the estimated cost to the destination is going up, as well as the cost from the starting position. According to A*, this indicates we are going in the wrong direction, and so it begins searching in other directions where there are unexplored Nodes that are cheaper.

By the time it solves the path it will have explored all the Nodes in the grey area like this (note the image is just cropped at the top and bottom; it should be pretty much a circle):

Here is that area again, but with a rough approximation of the Node cost, using Green for “cheap” and Red for “expensive”:

 

These are just mock-ups I did in Paint, but as you can imagine, the cost of a Node rises as you move away from the start and destination points.

The area needed to be searched, for A* to work in this scenario, took too long and was causing noticeable slowdown in the game, even with just a few AI active. It is made worse by the fact that in the my game, walls can be arbitrarily placed by the player, creating extremely long walls.

So now that I knew what was going wrong, the question became, how to fix it!

I’ll cover my solution to the problem in my next blog entry (now available).