Struct hierarchical_pathfinding::PathCache

pub struct PathCache<N: Neighborhood> { /* fields omitted */ }

A struct to store the Hierarchical Pathfinding information.

Methods

impl<N: Neighborhood> PathCache<N>

pub fn new(
    (width, height): (usize, usize),
    get_cost: impl Fn(Point) -> isize,
    neighborhood: N,
    config: PathCacheConfig
) -> PathCache<N>

Creates a new PathCache

Arguments

• (width, height) - the size of the Grid
• get_cost - get the cost for walking over a Tile. (Cost < 0 => solid Tile)
• neighborhood - the Neighborhood to use. (See Neighborhood)
• config - optional config for creating the cache. (See PathCacheConfig)

Examples

Basic usage:

use hierarchical_pathfinding::{prelude::*, Point};

// create and initialize Grid
// 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());

const COST_MAP: [isize; 3] = [1, 10, -1];

fn cost_fn<'a>(grid: &'a [[usize; 5]; 5]) -> impl 'a + Fn(Point) -> isize {
    move |(x, y)| COST_MAP[grid[y][x]]
}

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, ..Default::default() }, // config
);

pub fn find_path(
    &mut self,
    start: Point,
    goal: Point,
    get_cost: impl Fn(Point) -> isize
) -> Option<AbstractPath<N>>

Calculates the Path from start to goal on the Grid.

If no Path could be found, None is returned.

This function takes a mutable reference of self, because start and goal need to be inserted into the Abstract Graph in order for the algorithm to work. They are removed at the end unless config.keep_insertions was set to true (default) when creating the PathCache.

Arguments

• start the Point where the search starts
• goal the Point to search for. This may be a solid Tile.
• get_cost get the cost for walking over a Tile. (Cost < 0 => solid Tile)

Examples

Basic usage:

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);

The return Value gives the total Cost of the Path using cost() and allows to iterate over the Points in the Path.

Note: Setting config.cache_paths to false means that the Paths need to be recalculated as needed. This means that for any sections of the Path that are not present, safe_next needs to be called to supply the Cost function. Calling next in that scenario would lead to a Panic.

Using the Path:

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));

If the Grid changes, any Path objects still in use may become invalid. You can still use them if you are certain that nothing in relation to that Path changed, but it is discouraged and can lead to undefined behavior or panics.

Obtaining the entire Path:

// ...
let path = path.unwrap();

let points: Vec<(usize, usize)> = path.collect();
assert_eq!(
    points,
    vec![(0, 1),  (0, 2),  (0, 3),  (0, 4),  (1, 4),  (2, 4),
         (2, 3),  (2, 2),  (3, 2),  (4, 2),  (4, 3),  (4, 4)],
);

pub fn find_paths(
    &mut self,
    start: Point,
    goals: &[Point],
    get_cost: impl Fn(Point) -> isize
) -> HashMap<Point, AbstractPath<N>>

Calculates the Paths from one start to several goals on the Grid.

This is equivalent to find_path, except that it is optimized to handle multiple Goals at once. However, it is slower for very few goals, since it does not use a heuristic like find_path does.

Instead of returning a single Option, it returns a Hashmap, where the position of the Goal is the key, and the Value is a Tuple of the Path and the Cost of that Path.

See find_path for more details on how to use the returned Path.

Arguments

• start the Point where the search starts
• goals the Points to search for. They may be a solid Tiles.
• get_cost get the cost for walking over a Tile. (Cost < 0 => solid Tile)

Examples

Basic usage:

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]));

The returned Path is always equivalent to the one returned by find_path:

let start = (0, 0);
let goal = (4, 4);

let paths = pathfinding.find_paths(
    start,
    &[goal],
    cost_fn(&grid),
);
let dijkstra_path: Vec<Point> = paths[&goal].clone().collect();

let a_star_path: Vec<Point> = pathfinding.find_path(
    start,
    goal,
    cost_fn(&grid),
).unwrap().collect();

assert_eq!(dijkstra_path, a_star_path);

pub fn tiles_changed(
    &mut self,
    tiles: &[Point],
    get_cost: impl Fn(Point) -> isize
)

let (start, goal) = ((0, 0), (2, 0));

let path = pathfinding.find_path(start, goal, cost_fn(&grid));
assert!(path.is_none());

grid[0][1] = 0;
grid[4][4] = 2;

pathfinding.tiles_changed(
    &[(1, 0), (4, 4)],
    cost_fn(&grid),
);

let path = pathfinding.find_path(start, goal, cost_fn(&grid));
assert!(path.is_some());

pub fn config(&self) -> PathCacheConfig

Returns the config used to create this PathCache

Trait Implementations

impl<N: Clone + Neighborhood> Clone for PathCache<N>

fn clone(&self) -> PathCache<N>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Debug + Neighborhood> Debug for PathCache<N>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.