Struct hierarchical_pathfinding::PathCache [−][src]
pub struct PathCache<N: Neighborhood> { /* fields omitted */ }
Expand description
A struct to store the Hierarchical Pathfinding information.
Implementations
impl<N: Neighborhood> PathCache<N>
[src]
impl<N: Neighborhood> PathCache<N>
[src]pub fn new(
(width, height): (usize, usize),
get_cost: impl FnMut((usize, usize)) -> isize,
neighborhood: N,
config: PathCacheConfig
) -> PathCache<N>
[src]
pub fn new(
(width, height): (usize, usize),
get_cost: impl FnMut((usize, usize)) -> isize,
neighborhood: N,
config: PathCacheConfig
) -> PathCache<N>
[src]Creates a new PathCache
Arguments
(width, height)
- the size of the Gridget_cost
- get the cost for walking over a Tile. (Cost < 0 means solid Tile)neighborhood
- the Neighborhood to use. (SeeNeighborhood
)config
- optional config for creating the cache. (SeePathCacheConfig
)
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 '_ + FnMut((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 { chunk_size: 3, ..Default::default() }, // config );
pub fn find_path(
&self,
start: (usize, usize),
goal: (usize, usize),
get_cost: impl FnMut((usize, usize)) -> isize
) -> Option<AbstractPath<N>>
[src]
pub fn find_path(
&self,
start: (usize, usize),
goal: (usize, usize),
get_cost: impl FnMut((usize, usize)) -> isize
) -> Option<AbstractPath<N>>
[src]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)], );
pub fn find_paths(
&self,
start: (usize, usize),
goals: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
) -> HashMap<(usize, usize), AbstractPath<N>, FnvBuildHasher>
[src]
pub fn find_paths(
&self,
start: (usize, usize),
goals: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
) -> HashMap<(usize, usize), AbstractPath<N>, FnvBuildHasher>
[src]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);
pub fn find_closest_goal(
&self,
start: (usize, usize),
goals: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
) -> Option<((usize, usize), AbstractPath<N>)>
[src]
pub fn find_closest_goal(
&self,
start: (usize, usize),
goals: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
) -> Option<((usize, usize), AbstractPath<N>)>
[src]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);
pub fn tiles_changed(
&mut self,
tiles: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
)
[src]
pub fn tiles_changed(
&mut self,
tiles: &[(usize, usize)],
get_cost: impl FnMut((usize, usize)) -> isize
)
[src]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());
pub fn inspect_nodes(&self) -> CacheInspector<'_, N>ⓘNotable traits for CacheInspector<'a, N>
impl<'a, N: Neighborhood> Iterator for CacheInspector<'a, N> type Item = NodeInspector<'a, N>;
[src]
pub fn inspect_nodes(&self) -> CacheInspector<'_, N>ⓘNotable traits for CacheInspector<'a, N>
impl<'a, N: Neighborhood> Iterator for CacheInspector<'a, N> type Item = NodeInspector<'a, N>;
[src]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 } }
pub fn config(&self) -> &PathCacheConfig
[src]
pub fn config(&self) -> &PathCacheConfig
[src]Returns the config used to create this PathCache
Trait Implementations
impl<N: Clone + Neighborhood> Clone for PathCache<N>
[src]
impl<N: Clone + Neighborhood> Clone for PathCache<N>
[src]Auto Trait Implementations
impl<N> RefUnwindSafe for PathCache<N> where
N: RefUnwindSafe,
N: RefUnwindSafe,
impl<N> Send for PathCache<N> where
N: Send,
N: Send,
impl<N> Sync for PathCache<N> where
N: Sync,
N: Sync,
impl<N> Unpin for PathCache<N> where
N: Unpin,
N: Unpin,
impl<N> UnwindSafe for PathCache<N> where
N: UnwindSafe,
N: UnwindSafe,
Blanket Implementations
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]pub fn borrow_mut(&mut self) -> &mut T
[src]
pub fn borrow_mut(&mut self) -> &mut T
[src]Mutably borrows from an owned value. Read more
impl<T> ToOwned for T where
T: Clone,
[src]
impl<T> ToOwned for T where
T: Clone,
[src]type Owned = T
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn to_owned(&self) -> T
[src]Creates owned data from borrowed data, usually by cloning. Read more
pub fn clone_into(&self, target: &mut T)
[src]
pub fn clone_into(&self, target: &mut T)
[src]🔬 This is a nightly-only experimental API. (toowned_clone_into
)
recently added
Uses borrowed data to replace owned data, usually by cloning. Read more