hierarchical_pathfinding 0.3.5

A crate to quickly approximate Paths on a Grid.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


# Hierarchical Pathfinding

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

[![Build Status](https://travis-ci.org/mich101mich/hierarchical_pathfinding.svg?branch=master)](https://travis-ci.org/mich101mich/hierarchical_pathfinding)
Tests: [![CircleCI](https://circleci.com/gh/mich101mich/hierarchical_pathfinding.svg?style=svg)](https://circleci.com/gh/mich101mich/hierarchical_pathfinding)

## 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

![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)