Crates.io | hierarchical_pathfinding |
lib.rs | hierarchical_pathfinding |
version | 0.5.0 |
source | src |
created_at | 2019-03-30 11:12:43.427023 |
updated_at | 2021-08-08 17:23:22.077209 |
description | Quickly approximate Paths on a Grid |
homepage | |
repository | https://github.com/mich101mich/hierarchical_pathfinding |
max_upload_size | |
id | 124755 |
size | 159,225 |
A Rust crate to find Paths on a Grid using HPA* (Hierarchical Pathfinding A*) and Hierarchical Dijkstra.
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".
Finding Paths on a Grid is an expensive Operation. Consider the following Setup:
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:
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);
}
}