Skip to content

Implementation of Near-Optimal Hierarchical Pathfinding (HPA*) algorithm in Unity, tested with maps from Dragon Age: Origins

License

Notifications You must be signed in to change notification settings

hugoscurti/hierarchical-pathfinding

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

49 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Hierarchical Pathfinding

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).

How to test

  1. Clone the repo

  2. 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

  3. Launch the project in unity, load the scene "main" and run it


Credits

About

Implementation of Near-Optimal Hierarchical Pathfinding (HPA*) algorithm in Unity, tested with maps from Dragon Age: Origins

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages