It’s been a while and I apologize for not updating the blog lately. Lair of the Kobolds is still progressing however and I have been busy on the game even while the blog’s been quiet.
Out of curiosity one day I sent 200 kobolds walking around a large map. They were using A* pathfinding like most games of this type do, and some are notorious for slowing down with a lot of creatures walking around. Lair of the kobolds was no exception. Most of the kobolds stood around waiting for their turn in the pathing queue while only a select lucky few could get where they were going.
The problem with normal A* is it will flood the map searching, especially if there is no route to the target location or it’s a got a very roundabout path. I researched a bit and stumbled upon HPA* which is a variation of A* that uses hierarchical clusters in order to narrow down the path before doing the normal square by square A*. HPA* Gets around the flooding problem by only flooding the clusters that are transitioned through, and there are far fewer of them. This paper is a good reference for how it works.
The Basic Algorithm
The way the algorithm works is you break the world into clusters of cubes, and then find all transitions between the clusters. Once you have the transitions you run A* on each pair of transitions within a cluster to get connectivity and distance between the two transitions. Then you can do another A* search on just the transition nodes to get an abstract path which is just the links between transitions. To get the real path from the abstract path you then run A* between the transitions in each cluster that the abstract path uses.
Once the transitions through the clusters are found, normal A* is run to walk between the clusters. Below is the visualization of a single kobold’s path. Red is the path through transitions, yellow is the actual path he follows. It’s not an optimal path but it can be made prettier by implementing path smoothing.
Selecting Transitions in 3D
Getting it to work in 3D was a little more involved than the 2D example in the paper. I started out by designating clusters as 3d cubes rather than 2d squares, which then gave the problem of the “edges” now turning into 2d squares themselves. The X and Z directions could be simplified by scanning them in slices that are only 1 cube high, but I found that pathfinding was faster if the clusters had a height of 1 anyway because kobolds walk on the ground and there was a lot of failed transition searching through the floors and ceilings of dungeons. Below is a view of the clusters on a small map. Each 1 block high cluster is surrounded by a square, and all the transitions between clusters are small cubes.
Finding transitions between Y levels was a bit harder, since there’s no easy scanline way that results in good transitions. What I ended up doing was floodfilling both the current level and the level above to find individual “islands”, then grouping together the ramps that had the same two islands on either side and picking from those.
Below is an example of how this works. We are trying to find the transitions between the upper and lower levels which are separated by the dark pit in the center. The ramps are signified as arrows leading from the upper level to the lower. Something simple like finding all the ramps and choosing one won’t work, because the two parts of the upper level and two parts of the lower level aren’t connected.
Next, we floodfill each section of the top layer, then each section of the bottom, with any ramps getting tagged with both end’s fills. This separates our ramps into distinct groups: red/blue, red/green, yellow/blue, yellow/green.
We know that all ramps in each group can get us from the same lower section to the same upper section, so we can feel free to choose one. I simply picked the one most central to each set.
Dealing with Geometry Changes
Kobolds mine (and will soon build) so the pathing information for a cluster occasionally needs to be reprocessed. If the changed block is in the middle of a cluster, all that needs to be done is recalculate the distances and connectivity of the transitions within that cluster. But if the changed block is on the edge of the cluster, the transitions between the changed cluster and the neighbor it shares an edge with need to be re-found. The neighbor only needs to calculate transition distances for any new transitions it gets from the changed cluster, because no internals changed. Since my clusters are only one block high, transitions with the upper and lower neighbors need to be re-found every time
Now how well did it do to speed things up? I ran a test with kobolds pathing to random surface points on some large maps, all paths going through both HPA* and A* to compare.
On a hilly map the average time for A* was 14.7 milliseconds. With HPA* it went down to 2.5 milliseconds.
On a flattish map the average time for A* was 9.5 milliseconds. With HPA* it went down to 0.9 milliseconds.
Not too shabby. Now about 6-10 times more kobolds can path around than before this was implemented.
And now… 200 kobolds walking around a large map: