Struct PathCache

Source
pub struct PathCache<N: Neighborhood> { /* private fields */ }
Expand description

A struct to store the Hierarchical Pathfinding information.

Implementations§

Source§

impl<N: Neighborhood + Sync> PathCache<N>

Source

pub fn new<F: Sync + Fn((usize, usize)) -> isize>( (width, height): (usize, usize), get_cost: F, 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 means solid Tile)
  • neighborhood - the Neighborhood to use. (See Neighborhood)
  • config - optional config for creating the cache. (See PathCacheConfig)

get_cost((x, y)) should return the cost for walking over the Tile at (x, y). Costs below 0 are solid Tiles.

§Examples

Basic usage:

use hierarchical_pathfinding::prelude::*;

// 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());
type Grid = [[usize; 5]; 5];

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

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
    cost_fn(&grid), // get the cost for walking over a Tile
    ManhattanNeighborhood::new(width, height), // the Neighborhood
    PathCacheConfig::with_chunk_size(3), // config
);
Source

pub fn new_with_fn_mut<F: FnMut((usize, usize)) -> isize>( (width, height): (usize, usize), get_cost: F, neighborhood: N, config: PathCacheConfig, ) -> PathCache<N>

Same as new, but doesn’t use threads to allow FnMut.

Equivalent to new if parallel feature is disabled.

Note that this is way slower than new with parallel.

Source

pub fn new_parallel<F: Sync + Fn((usize, usize)) -> isize>( (width, height): (usize, usize), get_cost: F, neighborhood: N, config: PathCacheConfig, ) -> PathCache<N>

👎Deprecated since 0.5.0: new is automatically parallel

Same as new, but uses multiple threads.

Note that get_cost has to be Fn instead of FnMut.

Source

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

Calculates the Path from start to goal on the Grid.

If no Path could be found, None is returned.

get_cost((x, y)) should return the cost for walking over the Tile at (x, y). Costs below 0 are solid Tiles.

§Examples

Basic usage:

let pathfinding: PathCache<_> = // ...

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

pub fn find_paths( &self, start: (usize, usize), goals: &[(usize, usize)], get_cost: impl FnMut((usize, usize)) -> isize, ) -> HashMap<(usize, usize), 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.

get_cost((x, y)) should return the cost for walking over the Tile at (x, y). Costs below 0 are solid Tiles.

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

§Examples

Basic usage:

let pathfinding: PathCache<_> = // ...

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<_> = paths[&goal].clone().collect();

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

assert_eq!(dijkstra_path, a_star_path);
Source

pub fn find_closest_goal( &self, start: (usize, usize), goals: &[(usize, usize)], get_cost: impl FnMut((usize, usize)) -> isize, ) -> Option<((usize, usize), AbstractPath<N>)>

Finds the closest from a list of goals.

Returns a tuple of the goal and the Path to that goal, or None if none of the goals are reachable.

Similar to find_paths in performance and search strategy, but stops after the first goal is found.

§Examples

Basic usage:

let pathfinding: PathCache<_> = // ...

let start = (0, 0);
let goals = [(4, 4), (2, 0), (2, 2)];

// find_closest_goal returns Some((goal, Path)) on success
let (goal, path) = pathfinding.find_closest_goal(
    start,
    &goals,
    cost_fn(&grid),
).unwrap();

assert_eq!(goal, goals[2]);

let naive_closest = pathfinding
    .find_paths(start, &goals, cost_fn(&grid))
    .into_iter()
    .min_by_key(|(_, path)| path.cost())
    .unwrap();

assert_eq!(goal, naive_closest.0);

let path: Vec<_> = path.collect();
let naive_path: Vec<_> = naive_closest.1.collect();
assert_eq!(path, naive_path);

Comparison with find_paths:

let (goal, path) = pathfinding.find_closest_goal(
    start,
    &goals,
    cost_fn(&grid),
).unwrap();

let naive_closest = pathfinding
    .find_paths(start, &goals, cost_fn(&grid))
    .into_iter()
    .min_by_key(|(_, path)| path.cost())
    .unwrap();

assert_eq!(goal, naive_closest.0);

let path: Vec<_> = path.collect();
let naive_path: Vec<_> = naive_closest.1.collect();
assert_eq!(path, naive_path);
Source

pub fn tiles_changed<F: Sync + Fn((usize, usize)) -> isize>( &mut self, tiles: &[(usize, usize)], get_cost: F, )

Notifies the PathCache that the Grid changed.

This Method updates any internal Paths that might have changed when the Grid changed. This is an expensive operation and should only be performed if the change affected the walking cost of a tile and the PathCache is needed again. If possible, try to bundle as many changes as possible into a single call to tiles_changed to avoid unnecessary recalculations.

Side note: if anybody has a way to improve this method, open a GitHub Issue / Pull Request.

§Examples

Basic usage:

let mut pathfinding: PathCache<_> = // ...

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

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

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

assert_eq!(grid, [
    [0, 2, 0, 0, 0],
    [0, 2, 0, 2, 2],
    [0, 1, 0, 0, 0],
    [0, 1, 2, 2, 0],
    [0, 0, 0, 2, 0],
]);

pathfinding.tiles_changed(
    &[(2, 1), (2, 3)],
    cost_fn(&grid),
);

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

pub fn tiles_changed_with_fn_mut<F: FnMut((usize, usize)) -> isize>( &mut self, tiles: &[(usize, usize)], get_cost: F, )

Same as tiles_changed, but doesn’t use threads to allow FnMut.

Equivalent to tiles_changed if parallel feature is disabled.

Note that this is way slower than tiles_changed with parallel.

Source

pub fn inspect_nodes(&self) -> CacheInspector<'_, N>

Allows for debugging and visualizing the PathCache

The returned object gives read-only access to the current state of the PathCache, mainly the Nodes and how they are connected to each other

§Examples

Basic usage:

let pathfinding: PathCache<_> = // ...

// only draw the connections between Nodes once
let mut visited = HashSet::new();

for node in pathfinding.inspect_nodes() {
    let pos = node.pos();
    // draw Node at x: pos.0, y: pos.1

    visited.insert(node.id());
     
    for (neighbor, cost) in node.connected().filter(|(n, _)| !visited.contains(&n.id())) {
        let other_pos = neighbor.pos();
        // draw Line from pos to other_pos, colored by cost
    }
}
Source

pub fn config(&self) -> &PathCacheConfig

Returns the config used to create this PathCache

Trait Implementations§

Source§

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

Source§

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

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

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

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<N> Freeze for PathCache<N>
where N: Freeze,

§

impl<N> RefUnwindSafe for PathCache<N>
where N: RefUnwindSafe,

§

impl<N> Send for PathCache<N>
where N: Send,

§

impl<N> Sync for PathCache<N>
where N: Sync,

§

impl<N> Unpin for PathCache<N>
where N: Unpin,

§

impl<N> UnwindSafe for PathCache<N>
where N: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

impl<T> Pointable for T

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.