Hierarchical Pathfinding

A Rust crate to find Paths on a Grid using HPA* (Hierarchical Pathfinding A*) and Hierarchical Dijkstra.

Tests:

Description

Provides a faster method of finding Paths on a Grid-like structure than regular Pathfinding algorithms. This is achieved by caching segments of Paths that form a higher order Node Graph. Finding a Path in that Graph is considerably faster than traversing all the tiles of the Grid individually, at the cost of producing Paths that are slightly worse than the optimal Path.

Advantages

• Finding a Path is a lot faster compared to regular algorithms
• It is always correct: A Path is found if and only if it exists
  • This means that Hierarchical Pathfinding can be used as Heuristic to check if a Path exists and how long it will roughly be (upper bound)

Disadvantages

• Paths are slightly worse (negligible in most cases)
• Creating the cache takes time (only happens once at the start)
• Changes to the Grid require updating the cache
  • Whenever a Tile within a Chunk changes, that entire Chunk needs to recalculate its Paths. Performance depends on Chunk size (configurable) and the number of Nodes in a Chunk

Example

In order to calculate a Path from Start to End using regular A*, it is necessary to check a lot of Tiles:

(This is simply a small example, longer Paths require a quadratic increase in Tile checks, and unreachable Goals require the check of every single Tile)

The Solution that Hierarchical Pathfinding provides is to divide the Grid into Chunks and cache the Paths between Chunk entrances as a Graph of Nodes:

This allows Paths to be generated by connecting the Start and End to the Nodes within the Chunk and using the Graph for the rest: