Module sqrid::bf

source ·
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:

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 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:

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

Functions