DYNAMIC HPA*: PART 2

If you haven’t already, you should read part 1 of this blog first.

To quickly recap the previous blog:

My game uses standard A* for path finding, but would run into performance issues when trying to find paths around concave shapes. The problem is that once you go passed the destination, A* thinks you are going down a bad path and so it exhausts all other alternate paths first.

The solution I found to this problem is an extension to A*, known as “Near Optimal Hierarchical Path-Finding”; often referred to as HPA*. All my work has been based on this white paper: http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf.

This analogy summarizes the abstract theory of HPA* quite well:

Consider the problem of traveling by car from Los Angeles, California, to Toronto, Ontario. Specically, what is the minimum distance to travel by car from 1234 Santa Monica Blvd in Los Angles to 4321 Yonge Street in Toronto? Given a detailed roadmap of North America, showing all roads annotated with driving distances, an A* implementation can compute the optimal (minimum distance) travel route. This might be an expensive computation, given the sheer size of the roadmap.

 

Of course, a human travel planner would never work at such a low level of detail. They would solve three problems:

 

1. Travel from 1234 Santa Monica Boulevard to a major highway leading out of Los Angeles.

2. Plan a route from Los Angeles to Toronto.

3. Travel from the incoming highway in Toronto to 4321 Yonge Street.

At a high level, this algorithm is an optimization which aims to change the A* search graph into a collection of smaller searches, that can be somewhat pre-computed.

This algorithm starts by breaking the search graph down into “clusters”. Each cluster contains a small section of the larger graph (like a Quad tree).

To make this truly useful though, each cluster needs to determine where its entrances and exits are (cluster nodes). This is precomputed with a few rules, but essentially it says “if two clusters have neighboring nodes that are not walls, those are potential entrances and exits. Along empty sections of the border of a cluster, put 1 or 2 cluster nodes depending on the length of the border section.

You end up with something like this:

Note that it finds the valid connections between the clusters, but also the connections within the cluster. To determine the connections inside a cluster, we actually use standard A* between each cluster node within a cluster. If a node can be reached, then they are connected, and the A* cost to reach to node is cached for later use. If 2 nodes cannot be connection without leaving the cluster (eg. there is a wall down the center between them), the nodes are left unconnected.

Connections between clusters also have their cost cached, but they always have the same cost since it is always a 1 unit distance.

After this is done for the whole graph you end up with something like this:

And since we cached all the A* costs between nodes, we can now quickly find the optimal path from any cluster to another using A* on this Graph. We no longer need to search tile by tile, but can instead search cluster by cluster.

However, this is only step 2 of the travelling from LA to Toronto analogy; we still need to “get to the highway” and “get from the highway exit to the street address”.

To do this, we dynamically insert our Start and Goal into the cluster graph, and do an A* search from Start to Goal.

In practice this was the most complex part of the work, since we often have numerous entities doing path searches at the same time, and we need to make sure they don’t hold references to the temporary graph nodes, since they will be removed once the owner finds their path.

Another complexity is that we don’t actually want the game entities to follow this HPA* path verbatim since it will trying to walk through some small walls. To fix this, I use the HPA* path for high level planning but when actually walking from one graph node to another, I use a low level tile based A* path finder to get a path between them. This is the same search done when connecting graph nodes during precomputation, so the results should match up.

Since my game allows the user to place down walls at will, the cluster graph needs to be able to update dynamically. This isn’t too complex, since I really just need to update the cluster in which the wall was placed, and update any connections to adjacent cluster nodes.

So how’s it look in the end? Lets take another looks at that convex shape search again:

Using some debug draw, I’ve overlaid the cluster information:

It’s a little tough to see but here is what is there (apologies to the color blind out there):

• Yellow squares show the borders of clusters.
• Red circles show graph nodes.
• Lines between graph nodes blend from bright red to white representing the cost to travel between those nodes (red  = high cost, white = low cost).

Notice that the cost between clusters is always very low (white), and the cost inside clusters varies based on the distance between nodes, and any walls that might get in the way.

Now lets spawn an AI in there (the green guy on the right) and watch how he path finds to the player (the white guy in the center).

Woah, that’s a lot to take in, so let me break down the additional data that has been added:

• Red and Purple squares are nodes visited during path finding. They have cost us some computation time.
• Red are closed nodes (this is an A* term)
• Purple are open nodes (this is also an A* term).
• The light blue line (tough to see) is the path it chose to reach the destination. Note: the path find is in progress so it doesn’t show the final path.

Note that this includes both the high level HPA* search and the low level tile based A* search, so this is every single node needed to reach the destination. It may seem like a lot still, but lets have a look at what this looked like prior to the implementation of HPA*:

It was so bad I had to change the camera zoom level just to show all the nodes visited (note: at this point open nodes were Green boxes instead of purple ones)!

Going back to the new solution, I’ve highlighted both the cluster search path chosen, and the final A* path chosen.

So to recap again, first I quickly find the list of cluster nodes that get me from Start to Goal in the shortest distance (based on cached costs between cluster nodes). I then do a low level tile-based path find from cluster node to cluster node along that high level path to get the final path the AI will walk on.

The extra cool part is that once I have the high level HPA* path, I can start the AI walking along that while the low level search works in the background.

In the end, the huge reduction in the number of nodes visited gains me about a 30x performance increase in a worst case like the one above. For most cases it is slightly better, and for really simple cases it can actually be a little bit worse, but nothing significant. The important thing is that prior to this, the game was not really shippable, as it could easily be brought to a crawl just through basic gameplay. The work took about 2 weeks of spare-time-crunch, but definitely worth it!