Hierarchical Pathfinding Tech Demo

This is a tech demo I did with Evan Schipellite for my game AI course. We implemented hierarchical pathfinding and path smoothing. The purpose of hierarchical pathfinding is to make the movement path calculated much smaller and relative to the characters current area. For example if your in your room and you need to get to work, the only path that is immediately important is the one to get out of your room and into the next one. In order to know which room is the next one (going into the hallway instead of your bathroom) there needs to be a higher level plan. To create this plan the hierarchical pathfinder needs to group up sections and layers. The first layer being the node information that would be used for something like A*; In our tech demo we use a tile grid with connections to all adjacent tiles without collision. The next layer could be grouped as rooms like the bed room, upstairs hallway, bathroom, ect. The layer after that could be the buildings such as your house, your work building, ect. From here you can keep making as many layers as necessary to increase efficiency. I created a level editor using C# XNA with winforms to provide the data for our tech demo. Using this editor we were able to easily specify sections in as many layers as we wanted as shown in the pictures above.

The most challenging part of this project was understanding and implementing hierarchical pathfinding. We used Artificial Intelligence For Games by Ian Millington and John Funge for the explanation of how hierarchical pathfinding works and algorithm for implementing the pathfinding. It took us a few hours to completely understand how hierarchical pathfinding should work and how we should approach doing it. I was able to create an infrastructure that would read in the data from my level editor and create multiple layers that we could use in our pathfinding algorithm. We were then able to take that infrastructure and apply it to the algorithm in the book to get a working hierarchical pathfinder.

To show off the smaller subsections of hierarchical pathfinding working we added the ability to turn on and off continuous pathfinding. When continuous pathfinding is off the characters only move to the next room on the higher path. This demonstrates how small of a path is created at one time.

In order for hierarchical pathfinding to really be worth it the map would need to be much larger than it is in this tech demo. In this situation it would not be impossible to A* across the whole map but if the map was much larger it would take far too much time to A* to any position. In that case this technique would be very useful to allow for pathfinding over a smaller area.