Crate sqrid

Source

Expand description

sqrid provides square grid coordinates and related operations, in a crate with zero dependencies.

It’s easier to explain the features of this crate in terms of the types it provides:

Pos: position, as absolute coordinates in a grid of fixed size. The dimensions of the grid are const generics type parameters; invalid coordinates can’t be created.
Dir: “movement”, relative coordinates. These are the cardinal (and intercardinal) directions. Addition is implemented in the form of Pos + Dir = Option<Pos>, which can be None if the result is outside the grid.
Grid: a Pos-indexed array.
Gridbool: a bitmap-backed Pos-indexed grid of booleans.
Sqrid: “factory” type that acts as an entry point to the fundamental types below and to algorithms.

We also have traits that generalize Grid and Gridbool:

MapPos: trait that maps Pos to parameterized items; it’s implemented by Grid, and some HashMap/BTreeMap based types.
SetPos: trait that maps each Pos to a bool; it’s implemented by Gridbool, HashSet<Pos> and BTreeSet<Pos>.

We then use these generalization to implement some grid algorithms:

bf: breadth-first iteration and search.
astar: A* search that takes a destination Pos.
ucs: uniform-cost search.

All basic types have the standard iter, iter_mut, extend, as_ref, and conversion operations that should be expected.

§Fundamental types

§`Pos`: absolute coordinates, position

The Pos type represents an absolute position in a square grid. The type itself receives the height and width of the grid as const generic parameter.

We should usually create a type alias for the grid size we are using:

use sqrid;

type Pos = sqrid::Pos<6, 7>;

let pos = Pos::new(3, 3)?;

We can only generate Pos instances that are inside the passed dimensions.

§`Dir`: relative coordinates, direction, movement

The Dir type represents a relative movement of one square. It can only be one of the 8 cardinal and intercardinal directions: Dir::N, Dir::NE, Dir::E, Dir::SE, Dir::S, Dir::SW, Dir::W, Dir::NW.

It’s a building block for paths, iterating on a Pos neighbors, etc. It effectively represents the edges in a graph where the Pos type represents nodes.

All functions that iterate on Dir values accept a boolean const argument that specifies whether the intercardinal directions (NE, SE, SW, NW) should be considered.

§`Grid`: a `Pos`-indexed array

A Grid is a generic array that can be indexed by a Pos.

We can create the type from a suitable Sqrid type by using the grid_create macro. We can then interact with specific lines with Grid::line and Grid::line_mut, or with the whole underlying array with as_ref (see std::convert::AsRef) and as_mut (see std::convert::AsMut).

Usage example:

type Sqrid = sqrid::sqrid_create!(2, 2, false);
type Pos = sqrid::pos_create!(Sqrid);
type Grid = sqrid::grid_create!(Sqrid, i32);

// The grid create macro above is currently equivalent to:
type Grid2 = sqrid::Grid<i32, Pos,
                         { ((Sqrid::XMAX as usize + 1) * (Sqrid::YMAX as usize + 1)) }>;

// We can create grids from iterators via `collect`:
let mut gridnums = (0..9).collect::<Grid>();

// Iterate on their members:
for i in &gridnums {
    println!("i {}", i);
}

// Change the members in a loop:
for i in &mut gridnums {
    *i *= 10;
}

// Iterate on (coordinate, member) tuples:
for (pos, &i) in gridnums.iter_pos() {
    println!("[{}] = {}", pos, i);
}

// And we can always use `as_ref` or `as_mut` to interact with the
// inner array directly. To reverse it, for example, with the
// [`std::slice::reverse`] function:
gridnums.as_mut().reverse();

§`Gridbool`: a bitmap-backed `Pos`-indexed grid of booleans

The Gridbool is a compact abstraction of a grid of booleans.

The type itself can be created with gridbool_create macro. It’s optimized for getting and setting values at specific coordinates, but we can also get all true/false coordinates with suboptimal performance - in this case, the time is proportional to the size of the grid and not to the quantity of true/false values.

Usage example:

type Sqrid = sqrid::sqrid_create!(3, 3, false);
type Pos = sqrid::pos_create!(Sqrid);
type Gridbool = sqrid::gridbool_create!(Sqrid);
use sqrid::postrait::PosT;

// We can create a gridbool from a Pos iterator via `collect`:
let mut gb = Pos::iter().filter(|pos| pos.is_corner()).collect::<Gridbool>();

// We can also set values from an iterator:
gb.set_iter_t(Pos::iter().filter(|pos| pos.is_side()));

// Iterate on the true/false values:
for b in gb.iter() {
    println!("{}", b);
}

// Iterate on the true coordinates:
for pos in gb.iter_t() {
    assert!(pos.is_side());
}

// Iterate on (coordinate, bool):
for (pos, b) in gb.iter_pos() {
    println!("[{}] = {}", pos, b);
}

§`Sqrid`: entry point for algorithms

The Pos type and some methods on the Dir type require const generic arguments that usually don’t change inside an application. Both Grid and Gridbool also require further arguments that can actually be derived from the width and height of the grid, but that have to be explicitly specified due to some Rust limitations.

To make the creation of these types easier, we provide the Sqrid type, which acumulates all const generic parameters and can be used to create the other types via macros.

Example usage:

type Sqrid = sqrid::sqrid_create!(4, 4, false);
type Pos = sqrid::pos_create!(Sqrid);
type Grid = sqrid::grid_create!(Sqrid, i32);
type Gridbool = sqrid::gridbool_create!(Sqrid);

§Algorithms

§Breadth-first traversal

The Sqrid::bf_iter function instantiates an iterator struct (bf::BfIterator) that can be used to iterate coordinates in breadth-first order, from a given origin, using a provided function to evaluate a given Pos position + Dir direction into the next Pos position.

Example usage:

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

for (pos, dir) in Sqrid::bf_iter(sqrid::pos_dir_add_ok, &Pos::CENTER)
                .flatten() {
    println!("breadth-first pos {} from {}", pos, dir);
}

§Breadth-first search

Sqrid::bfs_path takes an origin, a movement function and a goal function, and figures out the shortest path to a goal by using a breadth-first iteration.

The function returns the Pos that fulfills the goal and a path in the form of a Vec<Dir>.

Example 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::pos_dir_add_ok, &Pos::TOP_LEFT,
                              |pos| pos == Pos::BOTTOM_RIGHT) {
    println!("goal: {}, path: {:?}", goal, path);
}

§A* search

Sqrid::astar_path takes a movement function, an origin and a destination, and figures out the shortest path by using A*.

The function returns path in the form of a Vec<Dir>.

Example 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(path) = Sqrid::astar_path(sqrid::pos_dir_add_ok, &Pos::TOP_LEFT,
                                    &Pos::BOTTOM_RIGHT) {
    println!("path: {:?}", path);
}

§Uniform-cost search

Sqrid::ucs_path takes a movement-cost function, an origin and a destination, and figures out the path with the lowest cost by using uniform-cost search, which is essentially a variation of Dijkstra.

The function returns path in the form of a Vec<Dir>.

Example usage:

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

fn traverse(position: Pos, direction: sqrid::Dir) -> Option<(Pos, usize)> {
    let next_position = (position + direction).ok()?;
    let cost = 1;
    Some((next_position, cost))
}

// Generate the grid of "came from" directions from bottom-right to
// top-left:
if let Ok(path) = Sqrid::ucs_path(traverse, &Pos::TOP_LEFT,
                                  &Pos::BOTTOM_RIGHT) {
    println!("path: {:?}", path);
}

Modules§

astar: A* search algorithm module
base: Zero-dependency module that holds Sqrid
bf: Breadth-first traversal and search module
boundedint: Bounded integers modules.
dir: Direction data structure Dir that represents movement, and related functionality.
error: sqrid errors
grid: A grid is a generic array that can be indexed by a Pos
gridbool: Space-optimized grid of booleans using bitmaps
mappos: Module that abstracts maps with super::pos::Pos indexes
pos: Square grid absolute coordinates (position) and associated functionality
posdir: Interaction between Pos and Dir
postrait: Position as a trait
setpos: Module that abstracts sets of super::pos::Pos values
ucs: Uniform-cost search algorithm module

Macros§

grid_create: Helper macro for grid type creation.
gridbool_create: Helper macro for Gridbool type creation.
pos_create: Helper macro to a Pos type from an super::base::Sqrid.
sqrid_create: Creates the a Sqrid type from the provided parameters: width, height and diagonals

Structs§

BoundedI8: A bounded i8
BoundedI16: A bounded i16
BoundedI32: A bounded i32
BoundedI64: A bounded i64
BoundedI128: A bounded i128
BoundedIntIterator: Iterator for implementors of BoundedInt.
BoundedIsize: A bounded isize
BoundedU8: A bounded u8
BoundedU16: A bounded u16
BoundedU32: A bounded u32
BoundedU64: A bounded u64
BoundedU128: A bounded u128
DirIter: Iterator for Dir cardinal and itercardinal directions
Grid: A grid is a generic array that can be indexed by a Pos
Gridbool: Space-optimized grid of booleans using bitmaps
Pos: Square grid absolute coordinate
PosTIter: Iterator for positions
PosTIterInX: Iterator for a specific column
PosTIterInY: Iterator for a specific line
PosTIterRange: Iterator for positions inside a square range
Sqrid: Sqrid base “factory” type

Enums§

Dir: Direction type.
Error: sqrid errors enum

Traits§

BoundedInt: Trait for bounded integer types.
MapPos: Trait that abstracts maps with super::pos::Pos indexes
PosT: Position trait
SetPos: Trait that abstracts sets of super::pos::Pos values

Functions§

camefrom_into_path: Generate a Dir vector (i.e. a vector of directions) from a “came from” Dir MapPos by following the grid, starting at orig, until reaching dest.
direction_to: From a given src, returns the direction of the provided dst
display_fmt_helper: Grid Display helper function
pos_dir_add: Function that adds a pos and a dir, for usage where a function is more ergonomic.
pos_dir_add_ok: Function that adds a pos and a dir, for usage where a function that returns an Option<Pos> is more ergonomic.

Crate sqridCopy item path

§Fundamental types

§Pos: absolute coordinates, position

§Dir: relative coordinates, direction, movement

§Grid: a Pos-indexed array

§Gridbool: a bitmap-backed Pos-indexed grid of booleans

§Sqrid: entry point for algorithms

§Algorithms

§Breadth-first traversal

§Breadth-first search

§A* search

§Uniform-cost search

Modules§

Macros§

Structs§

Enums§

Traits§

Functions§

Crate sqrid

§`Pos`: absolute coordinates, position

§`Dir`: relative coordinates, direction, movement

§`Grid`: a `Pos`-indexed array

§`Gridbool`: a bitmap-backed `Pos`-indexed grid of booleans

§`Sqrid`: entry point for algorithms