Module sqrid::astar

source ·
Expand description

A* search algorithm module

This algorithm takes a movement function, an origin and a destination, and figures out the shortest path by using A*. A* should be used when we have a defined origin and destination points, and the cost of each step is the same.

Check out bf if the destination depends on more sophisticated conditions (or there are multple destinations), and check out ucs if the steps can have different costs.

The base of this module is the AstarIterator, which yields Pos coordinates in “A*-order”. That iterator is used by search_mapmov to build an unsorted Pos-indexed map of Dir directions, which can then transformed into a vector of directions by crate::camefrom_into_path. The complete search process is wrapped by search_path.

All these functions can be called directly, but that’s a bit inconvenient, as they require several generic parameters. An easier alternative is provided by the wrappers plugged into the Sqrid type:

Example of recommended usage:

type Sqrid = sqrid::sqrid_create!(3, 3, false);
type Pos = sqrid::pos_create!(Sqrid);

// Generate the vector with the path from bottom-right to top-left:
if let Ok(path) = Sqrid::astar_path(sqrid::mov_eval, &Pos::TOP_LEFT,
                                    &Pos::BOTTOM_RIGHT) {
    println!("path: {:?}", path);
}

Structs

Functions