[−][src]Function hierarchical_pathfinding::generics::graph::a_star_search

pub fn a_star_search<Id: Copy + Eq + Hash, NeighborIter: Iterator<Item = (Id, Cost)>>(
    get_all_neighbors: impl FnMut(Id) -> NeighborIter, 
    is_walkable: impl FnMut(Id) -> bool, 
    start: Id, 
    goal: Id, 
    heuristic: impl FnMut(Id) -> Cost
) -> Option<Path<Id>>

Searches a Graph using the A* 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.

Examples

Basic usage:

// A     B--2--E
// |\     
// | \    
// 1  9   
// |   \  
// |    \
// C--6--D
let (A, B, C, D, E) = (0, 1, 2, 3, 4);
let cost_matrix: [[i32; 5]; 5] = [
//    A,  B,  C,  D,  E
	[-1, -1,  1,  9, -1], // A
	[-1, -1, -1, -1,  2], // B
	[ 1, -1, -1,  6, -1], // C
	[ 9, -1,  6, -1, -1], // D
	[-1,  2, -1, -1, -1], // E
];

let result = a_star_search(
	|point| { // get_all_neighbors
		cost_matrix[point]
			.iter()
			.enumerate()
			.filter(|&(_, cost)| *cost != -1)
			.map(|(id, cost)| (id, *cost as usize))
	},
	|_| true, // is_walkable
	A, // start
	D, // goal
	|point| euclid_distance(point, D), // heuristic
);

assert!(result.is_some());
let path = result.unwrap();

assert_eq!(path, vec![A, C, D]);
assert_eq!(path.cost(), 7);

If the Goal cannot be reached, None is returned:

// ...
    A, // start
    E, // goal
	|point| euclid_distance(point, E), // heuristic
);

assert_eq!(result, None);

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 is_walkable Parameter that returns false for Nodes that should not be used as part of an actual Path. If there are no such Nodes in the Graph, is_walkable may simply be set to |_| true.
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 a Tuple of the Id of the neighbor and the Cost to get there.
  • is_walkable - a Function that determines if a Node can be walked over. see Solid Goals for more info
  • start - the starting Node
  • goal - the Goal that this function is supposed to search for
  • heuristic - the Heuristic Function of the A* Algorithm

Returns

the Path, if one was found, or None if the goal is unreachable. The first Node in the Path is always the start and the last is the goal