# 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

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`