In this project, we explore a variation of A* which utilizes the concept of abstracting a map into clusters and precomputing information to do pathfinding. This method is called Near-Optimal Hierarchical Pathfinding (HPA*).
The idea is to separate a map into multiple levels of clusters and to precompute information on how to navigate between clusters so that we can use this information later to do pathfinding on a higher level. This method mainly addresses the issue of pathfinding in real-time. Searching for a path should be efficient and should be done often. Moreover, given that the state of a game is constantly changing, we often disregard many of the pathfinding done. By using HPA*, we divide a map into clusters and precompute information on how to travel from a cluster to another. Therefore, we can efficiently do pathfinding on a higher level at a much lower cost, reusing precomputed low level paths between clusters. Consequently, pathfinding is generally faster than a traditional A* algorithm, and disregarding unnecessary paths is less heartbreaking. However, given that we travel from cluster to cluster by predetermined boundary nodes, the resulting paths from this method can be a bit less optimal than a straightforward A*, hence the name “Near-Optimal”.
Near-Optimal Hierarchical Pathfinding was implemented on grid-based maps using arbitrarily-sized automatically generated clusters. We tested the results of our algorithm on real maps from BioWare’s commercial game Dragon Age: Origins, provided by the Moving AI lab (See credits).
-
Clone the repo
-
Download maps from Moving AI's 2d Pathfinding benchmark sets
-
The expected map folder structure from the repo's root is the following:
Maps/ |- map/ | |- my_map1.map | |- my_map2.map | |- ... |- scen/ | |- my_map1.scen | |- my_map2.scen | |- ... -
If you download all the maps from a specific data set, extract all the .map files into Maps/map/
-
If you want to run the tests set as well, download the benchmark data and extract all the .scen files into Maps/scen/, and create an empty Maps/results/ folder
-
-
Launch the project in unity, load the scene "main" and run it
-
HPA* was introduced in this paper written by Botea, Müller, and Schaeffer.
-
All .map and .scen files used for testing come from Moving AI's 2d Pathfinding benchmark sets
-
The Priority Queue used in this project comes from BlueRaja's High Speed Priority Queue for C#. All files in folder Priority Queue comes from the repo's Priority Queue folder.