Function hierarchical_pathfinding::generics::grid::dijkstra_search

pub fn dijkstra_search<Id: Copy + Eq + Hash, NeighborIter: Iterator<Item = Id>>(
    get_all_neighbors: impl FnMut(Id) -> NeighborIter, 
    get_cost: impl FnMut(Id) -> isize, 
    start: Id, 
    goals: &[Id]
) -> HashMap<Id, Path<Id>>

Searches a Graph using Dijkstra's Algorithm.

The Generic type Parameter Id is supposed to uniquely identify a Node in the Graph. This may be a Number, String, a Grid position, ... as long as it can be compared, hashed and copied. Note that it is advised to choose a short representation for the Id, since it will be copied several times.

This function can be used to search for several Goals and will try to calculate a Path for every provided Goal. It stops as soon as it has the shortest Path to every Goal, or when all reachable Nodes have been expanded.

Examples

Basic usage:

// create and initialize Grid
// 0 = empty, 1 = swamp, 2 = wall
let mut grid = [
    [0, 2, 0, 0, 0],
    [0, 2, 2, 2, 2],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 2, 0],
    [0, 0, 0, 2, 0],
];
let (width, height) = (grid.len(), grid[0].len());

let neighborhood = ManhattanNeighborhood::new(width, height);

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

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

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

let paths = dijkstra_search(
    |point| neighborhood.get_all_neighbors(point),
    cost_fn(&grid),
    start,
    &goals,
);

// (4, 4) is reachable
assert!(paths.contains_key(&goals[0]));

// (2, 0) is not reachable
assert!(!paths.contains_key(&goals[1]));

Solid Goals

It is possible to calculate the shortest Path to for example a Wall and other non-walkable Nodes using this function. To do that, simply supply a Function to the get_cost Parameter that returns a negative number for Nodes that should not be used as part of an actual Path. In the case that a Path to a non-walkable Goal is requested, the neighbor of that Goal with the shortest Path from the Start is returned, if any is reachable. "neighbor" in this context is a Node for which get_all_neighbors contains the Goal.

Arguments

• get_all_neighbors - a Function that takes a Node and returns all other Nodes reachable from that Node. The returned value is the Id of the neighbor.
• get_cost - a Function that takes a Node and returns the Cost required to walk across that Node. Negative values indicate Nodes that cannot be walked across.
• start - the starting Node
• goals - the Goals that this function is supposed to search for

Returns

a HashMap with all reachable Goal's Ids as the Key and the shortest Path to reach that Goal as Value. The first Node in the Path is always the start and the last is the corresponding Goal