# Hierarchical Pathfinding

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

[![Tests](https://github.com/mich101mich/hierarchical_pathfinding/actions/workflows/test.yml/badge.svg)](https://github.com/mich101mich/hierarchical_pathfinding/actions/workflows/test.yml)

## Description
Provides a fast algorithm for finding Paths on a Grid-like structure by caching segments of Paths to form a Node Graph. Finding a Path in that Graph is a lot faster than on the Grid itself, but results in Paths that are _slightly_ worse than the optimal Path.

Implementation based on the Paper ["Near Optimal Hierarchical Path-Finding"](https://www.researchgate.net/profile/Adi-Botea/publication/228785110_Near_optimal_hierarchical_path-finding_HPA/links/09e41508fc2fed9a72000000/Near-optimal-hierarchical-path-finding-HPA.pdf).

### Advantages
- Finding a Path is a lot faster compared to regular algorithms (A*, Dijkstra)
- 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

## Use Case

Finding Paths on a Grid is an expensive Operation. Consider the following Setup:

![The Setup](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/problem.png?raw=true)

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

![A*](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/a_star.png?raw=true)

(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:

![The Graph](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/hpa.png?raw=true)

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:

![The Solution](https://github.com/mich101mich/hierarchical_pathfinding/blob/master/img/hpa_solution.png?raw=true)

## Example

```rust
use hierarchical_pathfinding::prelude::*;

let mut pathfinding = PathCache::new(
    (width, height),   // the size of the Grid
    |(x, y)| walking_cost(x, y),   // get the cost for walking over a Tile
    ManhattanNeighborhood::new(width, height),   // the Neighborhood
    PathCacheConfig::with_chunk_size(3),   // config
);

let start = (0, 0);
let goal = (4, 4);

// find_path returns Some(Path) on success
let path = pathfinding.find_path(
    start,
    goal,
    |(x, y)| walking_cost(x, y),
);

if let Some(path) = path {
    println!("Number of steps: {}", path.length());
    println!("Total Cost: {}", path.cost());
    for (x, y) in path {
        println!("Go to {}, {}", x, y);
    }
}
```