Hierarchical pathfinding implies dividing searches into a high level one, based on the region centers contained in the identified sectors, and a low level one, based on every tile in the map. Once the map has been sectorized and the regions identified, the artificial intelligence needed to change so it would recognize the difference between both pathfinding requests and their states, apart from the interactions between both.

I based the agents’ intelligence on behavior trees. To build the definitive tree, one that would recognize all the possible states, I had to write about ten unit tests. The final graph is the following:

However, the last time I programmed a behavior tree in my engine I failed to implement a NOT node, which inverts the result of its child. Writing it in it has doubled the amount of usable conditions and actions, making it trivial to implement, for example, the first “sentence” of the logic shown on the image: “if the agent has a destination but he hasn’t reached it, attempt to figure out if it has a low level route”. A few of the texts I’ve read about behavior trees warned about complicating their composition inventing nodes, because any behavior can be represented using sequences (nodes that return success if all of their children succeed), selectors/fallbacks (nodes that return success if any of their children succeed), decorators and actions. Condition nodes are a type of action node that makes a check.

The following video shows hierarchical pathfinding requests in a 64x64x8 map with agents that have different movement capabilities; some walk, others fly, others swim in shallow waters and others in deep waters. Every tile has information about whether an agent with specific movement capabilities can move straight through, upwards, downwards, straight up or straight down.

Although the agents reach their destination, in other maps I’ve found out that some tiles are unreachable for no apparent reason, or the agents choose erroneous region centers. Now that I have implemented saving and loading maps, I imagine I will be able to isolate those issues and solve them through unit testing.

(UPDATE): indeed, isolating failing maps in unit tests allowed me to solve the bugs I’ve found until now in the pathfinding system. A future article will show pathfinding through complicated maps that feature buildings.