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:
Sqrid::astar_path_grid
Sqrid::astar_path_hash
Sqrid::astar_path_btree
Sqrid::astar_path
: alias forastar_path_grid
.
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
- Internal A* iterator
Functions
- Make an A* search, return the “came from” direction
MapPos
- Makes an A* search, returns the path as a
Vec<Dir>
- Makes an A* search using the
BTreeMap
type, returns the path as aVec<Dir>
- Makes an A* search using
Grid
, returns the path as aVec<Dir>
- Makes an A* search using the
HashMap
] type, returns the path as aVec<Dir>