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:

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

The Graph

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

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 if config.cache_paths is set to false
- 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 if config.cache_paths is set to false
- 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

internals

Internal stuff that is returned by other function

neighbors

A crate with the most common Neighborhoods

prelude

The prelude for this crate.

Structs

PathCache

A struct to store the Hierarchical Pathfinding information.

PathCacheConfig

Options for configuring the PathCache