Expand description
Breadth-first traversal and search module
Breadth-first traversal
Breadth-first traversal on a grid is useful for several algorithms: searches, flood-fill, etc. This module provides a breadth-first iterator that yields the whole vector of coordinates at the current distance of the origin at each iteration.
While we can use BfIterator::new
to instantiate the iterator, doing that
requires us to specify several generic parameters. There’s also a more
convenient set of functions plugged into Sqrid
that has no such
requirement:
Sqrid::bf_iter_grid
Sqrid::bf_iter_hash
Sqrid::bf_iter_btree
Sqrid::bf_iter
: alias forbf_iter_grid
.
Example of recommended usage:
type Sqrid = sqrid::sqrid_create!(3, 3, false);
type Pos = sqrid::pos_create!(Sqrid);
for (distance, vecPosDir) in
Sqrid::bf_iter(sqrid::mov_eval, &Pos::CENTER).enumerate() {
println!("breadth-first at distance {}: {:?}",
distance, vecPosDir);
for (pos, dir) in vecPosDir {
println!("pos {} from dir {}", pos, dir);
}
}
// We can also iterate on the coordinates directly using `flatten`:
for (pos, dir) in Sqrid::bf_iter(sqrid::mov_eval, &Pos::CENTER)
.flatten() {
println!("breadth-first pos {} from dir {}", pos, dir);
}
Breadth-first search
Breadth-first search takes a movement function, an origin and a destination
function. It traverses the grid in breadth-first order, using
BfIterator
, until the destination function returns true. It returns the
shortest path from origin to the selected destination, along with the Pos
coordinates of the destination itself.
As usual, there is both a search_path
function that takes all
generic parameters explicitly, and a more convenient set of
functions plugged into the Sqrid
type:
Sqrid::bfs_path_grid
Sqrid::bfs_path_hash
Sqrid::bfs_path_btree
Sqrid::bfs_path
: alias forbf_path_grid
.
Example of recommended usage:
type Sqrid = sqrid::sqrid_create!(3, 3, false);
type Pos = sqrid::pos_create!(Sqrid);
// Generate the grid of "came from" directions from bottom-right to
// top-left:
if let Ok((goal, path)) = Sqrid::bfs_path(
sqrid::mov_eval, &Pos::TOP_LEFT,
|pos| pos == Pos::BOTTOM_RIGHT) {
println!("goal: {}, path: {:?}", goal, path);
}
Structs
- Breadth-first iterator
Functions
- Create new breadth-first iterator
- Create new breadth-first iterator using the
BTreeSet
type internally - Create new breadth-first iterator using
Grid
internally - Create new breadth-first iterator using the
HashSet
] type internally - Make a breadth-first search, return the “came from” direction
MapPos
- Makes a breadth-first search, returns the path as a
Vec<Dir>
- Makes an BF search using
Grid
, returns the path as aVec<Dir>