Crate hierarchical_pathfinding[−][src]
Expand description
A crate to quickly approximate Paths on a Grid.
Use Case
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:
Since the Graph is not an exact representation of the Grid, the resulting Paths will
be slightly worse than the actual best Path (unless config.perfect_paths
is set to true
). This is usually not a problem, since the purpose of Hierarchical Pathfinding
is to quickly find the next direction to go in or a Heuristic for the Cost and existence
of a Path.
The only time where the actual best Path would noticeably differ is in the case of short Paths. That is why this crate calls the regular A* search after HPA* confirmed the length and existence. (This behavior can be turned of using the Config).
This crate provides an implementation of a Hierarchical Pathfinding Algorithm for any generic Grid. Paths can be searched using either A* for a Path to a single Tile, or Dijkstra for searching multiple Targets. It handles solid walls in the Grid and actually finding a Path to a wall.
Examples
Creating the Cache
First is the Grid itself. How it is stored doesn’t matter, but lookup has to be fast.
For this example, we shall use a 2D-Array:
// 0 = empty, 1 = swamp, 2 = wall let mut grid = [ [0, 2, 0, 0, 0], [0, 2, 2, 2, 0], [0, 1, 0, 0, 0], [0, 1, 0, 2, 0], [0, 0, 0, 2, 0], ]; let (width, height) = (grid.len(), grid[0].len()); let cost_map = [ 1, // empty 10, // swamp -1, // wall = solid ];
Now for creating the PathCache
:
use hierarchical_pathfinding::prelude::*; let mut pathfinding = PathCache::new( (width, height), // the size of the Grid |(x, y)| cost_map[grid[y][x]], // get the cost for walking over a Tile ManhattanNeighborhood::new(width, height), // the Neighborhood PathCacheConfig::with_chunk_size(3), // config );
The PathCache
never takes the actual Grid, to allow for any storage format to be used
(Array
, Vec
, HashMap
, kd-tree
, …). Instead, it takes a callback function that
indicates, how “expensive” walking across a Tile is (negative numbers for solid obstacles).
Unfortunately, it is necessary to provide this function to every method of PathCache, since storing it would make the Grid immutable. See also Updating the PathCache.
Currying can be used to reduce duplication:
const COST_MAP: [isize; 3] = [1, 10, -1]; // now const for ownership reasons // only borrows the Grid when called fn cost_fn(grid: &Grid) -> impl '_ + Sync + Fn((usize, usize)) -> isize { move |(x, y)| COST_MAP[grid[y][x]] } let mut pathfinding = PathCache::new( (width, height), // the size of the Grid // simply call the creator function to take a reference of the Grid cost_fn(&grid), // ...
Pathfinding
Finding the Path to a single Goal:
let start = (0, 0); let goal = (4, 4); // find_path returns Some(Path) on success let path = pathfinding.find_path( start, goal, cost_fn(&grid), ); assert!(path.is_some()); let path = path.unwrap(); assert_eq!(path.cost(), 12);
For more information, see find_path
.
Finding multiple Goals:
let start = (0, 0); let goals = [(4, 4), (2, 0)]; // find_paths returns a HashMap<goal, Path> for all successes let paths = pathfinding.find_paths( start, &goals, cost_fn(&grid), ); // (4, 4) is reachable assert!(paths.contains_key(&goals[0])); // (2, 0) is not reachable assert!(!paths.contains_key(&goals[1]));
For more information, see find_paths
.
Using a Path
- Path exists:
path.is_some()
|paths.contains_key()
- Useful as a Heuristic for other Algorithms
- 100% correct (
true
if and only if path can be found)
- Total Cost of the Path:
path.cost()
- Correct for this Path, may be slightly larger than for optimal Path
- The cost is simply returned;
cost()
does no calculations
- Total Length of the Path:
path.length()
- Correct for this Path, may be slightly longer than the optimal Path
- The length is simply returned;
length()
does no calculations
- Next Position:
path.next()
|path.safe_next(cost_fn)
safe_next
is needed ifconfig.cache_paths
is set tofalse
- can be called several times to iterate Path
- path implements
Iterator<Item = (usize, usize)>
- Entire Path:
path.collect::<Vec<_>>()
|path.resolve(cost_fn)
resolve
is needed ifconfig.cache_paths
is set tofalse
- Returns a
Vec<(usize, usize)>
Note that resolve
calculates any missing segments (if config.cache_paths
== false
)
and allocates a Vec
with the resulting Points. Not recommended if only the
beginning of the Path is needed.
let mut player = Player { pos: (0, 0), //... }; let goal = (4, 4); let mut path = pathfinding.find_path( player.pos, goal, cost_fn(&grid), ).unwrap(); player.move_to(path.next().unwrap()); assert_eq!(player.pos, (0, 1)); // wait for next turn or whatever player.move_to(path.next().unwrap()); assert_eq!(player.pos, (0, 2)); // iterating is possible for new_pos in path { player.move_to(new_pos); } assert_eq!(player.pos, goal);
Updating the PathCache
The PathCache does not contain a copy or reference of the Grid for mutability and Ownership reasons. This means however, that the user is responsible for storing and maintaining both the Grid and the PathCache. It is also necessary to update the PathCache when the Grid has changed to keep it consistent:
let (start, goal) = ((0, 0), (2, 0)); let path = pathfinding.find_path(start, goal, cost_fn(&grid)); assert!(path.is_none()); // from previous example // Clear a way to the goal grid[1][2] = 0; // at (2, 1): the wall below the goal let path = pathfinding.find_path(start, goal, cost_fn(&grid)); assert!(path.is_some()); // there should be a Path now!
tiles_changed
must be called with all changed Tiles:
let (start, goal) = ((0, 0), (2, 0)); let path = pathfinding.find_path(start, goal, cost_fn(&grid)); assert!(path.is_none()); // Clear a way to the goal grid[1][2] = 0; // at (2, 1): the wall below the goal pathfinding.tiles_changed( &[(2, 1)], cost_fn(&grid), ); let path = pathfinding.find_path(start, goal, cost_fn(&grid)); assert!(path.is_some());
tiles_changed
takes a slice of Points, and it is recommended to bundle changes together for
performance reasons.
Configuration
The last parameter for PathCache::new is a PathCacheConfig
object with different options to have more control over the generated PathCache.
These options are mostly used to adjust the balance between Performance and Memory Usage, with the default values aiming more at Performance.
let mut pathfinding = PathCache::new( (width, height), // the size of the Grid cost_fn(&grid), // get the cost for walking over a Tile ManhattanNeighborhood::new(width, height), // the Neighborhood PathCacheConfig { chunk_size: 3, ..PathCacheConfig::LOW_MEM } ); assert_eq!(pathfinding.config().chunk_size, 3);
Cargo Features
parallel
Enabled by default.
The parallel feature causes PathCache
creation and updates to be multithreaded using Rayon, making them significantly faster.
This feature has no effect on the speed of finding paths (yet).
log
Disabled by default.
The log feature is used to enable internal timings on some functions.
You probably shouldn’t enable this feature unless you are working on improvments to hierarchical_pathfinding. In order to comsume the logs, you need a logger setup to show trace! level logs. See the log crate for more details.
Modules
Internal stuff that is returned by other function
A crate with the most common Neighborhoods
The prelude for this crate.
Structs
A struct to store the Hierarchical Pathfinding information.
Options for configuring the PathCache