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:
- [Qa]: 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.
- [Qr]: "movement", relative coordinates. These are the
cardinal (and intercardinal) directions.
Addition is implemented in the form of Qa + Qr = Option<Qa>,
which can be None if the result is outside the grid.
- [Grid]: a Qa-indexed array.
- [Gridbool]: a bitmap-backed Qa-indexed grid of booleans.
- [Sqrid]: "factory" type that acts as an entry point to the
fundamental types below and to algorithms.
Besides these fundamental types, as also have algorithm modules:
- [bf]: breadth-first iteration and search.
- [astar]: A* search that takes a destination Qa.
- [ucs]: uniform-cost search.
All basic types have the standard iter, iter_mut, extend,
as_ref, and conversion operations that should be expected.
Qa: absolute coordinates, positionThe [Qa] 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:
```rust use sqrid;
type Qa = sqrid::Qa<6, 7>; ```
We can only generate [Qa] instances that are valid - i.e. inside
the grid. Some of the ways to create instances:
- Using one of the const associated items: [Qa::FIRST] and
[Qa::LAST]; [Qa::TOP_LEFT], etc.; [Qa::CENTER].
- Using try_from with a (i16, i16) tuple or a tuple reference.
- Calling [Qa::new], which checks the bounds in const contexts:
rust
type Qa = sqrid::Qa<6, 7>;
const MY_FIRST : Qa = Qa::new::<3, 4>();
The following, for instance, doesn't compile:
rust
type Qa = sqrid::Qa<6, 7>;
const MY_FIRST : Qa = Qa::new::<12, 4>();
Qr: relative coordinates, direction, movementThe [Qr] type represents a relative movement of one square. It
can only be one of the 8 cardinal and intercardinal directions:
[Qr::N], [Qr::NE], [Qr::E], [Qr::SE], [Qr::S],
[Qr::SW], [Qr::W], [Qr::NW].
It's a building block for paths, iterating on a [Qa] neighbors,
etc. It effectively represents the edges in a graph where the
[Qa] type represents nodes.
All functions that iterate on Qr values accept a boolean const
argument that specifies whether the intercardinal directions
(NE, SE, SW, NW) should be considered.
Grid: a Qa-indexed arrayA [Grid] is a generic array that can be indexed by a [Qa].
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:
```rust type Sqrid = sqrid::sqridcreate!(3, 3, false); type Qa = sqrid::qacreate!(Sqrid); type Grid = sqrid::grid_create!(Sqrid, i32);
// The grid create macro above is currently equivalent to:
type Grid2 = sqrid::Grid // We can create grids from iterators via // 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 (qa, &i) in gridnums.iter_qa() {
println!("[{}] = {}", qa, i);
} // And we can always use The [ The type itself can be created with [ Usage example: ```rust
type Sqrid = sqrid::sqridcreate!(3, 3, false);
type Qa = sqrid::qacreate!(Sqrid);
type Gridbool = sqrid::gridbool_create!(Sqrid); // We can create a gridbool from a Qa iterator via // We can also set values from an iterator:
gb.setitert(Qa::iter().filter(|qa| qa.is_side())); // Iterate on the true/false values:
for b in gb.iter() {
println!("{}", b);
} // Iterate on the true coordinates:
for qa in gb.itert() {
assert!(qa.isside());
} // Iterate on (coordinate, bool):
for (qa, b) in gb.iter_qa() {
println!("[{}] = {}", qa, b);
}
``` The [ To make the creation of these types easier, we provide the
[ Example usage: The [ Example usage: ```rust
type Sqrid = sqrid::sqridcreate!(3, 3, false);
type Qa = sqrid::qacreate!(Sqrid); for (qa, qr) in Sqrid::bfiter(sqrid::qaqreval, &Qa::CENTER)
.flatten() {
println!("breadth-first qa {} from {}", qa, qr);
}
``` [ The function returns the [ Example usage: ```rust
type Sqrid = sqrid::sqridcreate!(3, 3, false);
type Qa = sqrid::qacreate!(Sqrid); // Generate the grid of "came from" directions from bottom-right to
// top-left:
if let Ok((goal, path)) = Sqrid::bfspath(
sqrid::qaqreval, &Qa::TOPLEFT,
|qa| qa == Qa::BOTTOMRIGHT) {
println!("goal: {}, path: {:?}", goal, path);
}
``` [ The function returns path in the form of a Example usage: ```rust
type Sqrid = sqrid::sqridcreate!(3, 3, false);
type Qa = sqrid::qacreate!(Sqrid); // Generate the grid of "came from" directions from bottom-right to
// top-left:
if let Ok(path) = Sqrid::astarpath(sqrid::qaqreval, &Qa::TOPLEFT,
&Qa::BOTTOMRIGHT) {
println!("path: {:?}", path);
}
``` [ The function returns path in the form of a Example usage: ```rust
type Sqrid = sqrid::sqridcreate!(3, 3, false);
type Qa = sqrid::qacreate!(Sqrid); fn traverse(position: Qa, direction: sqrid::Qr) -> Option<(Qa, usize)> {
let nextposition = (position + direction)?;
let cost = 1;
Some((nextposition, cost))
} // Generate the grid of "came from" directions from bottom-right to
// top-left:
if let Ok(path) = Sqrid::ucspath(traverse, &Qa::TOPLEFT,
&Qa::BOTTOM_RIGHT) {
println!("path: {:?}", path);
}
```collect:
let mut gridnums = (0..9).collect::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 Qa-indexed grid of booleansGridbool] is a compact abstraction of a grid of booleans.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.collect:
let mut gb = Qa::iter().filter(|qa| qa.is_corner()).collect::Sqrid: entry point for algorithmsQa] type and some methods on the [Qr] 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.Sqrid] type, which acumulates all const generic parameters and
can be used to create the other types via macros.rust
type Sqrid = sqrid::sqrid_create!(4, 4, false);
type Qa = sqrid::qa_create!(Sqrid);
type Grid = sqrid::grid_create!(Sqrid, i32);
type Gridbool = sqrid::gridbool_create!(Sqrid);
Algorithms
Breadth-first traversal
Sqrid::bf_iter] function instantiates an iterator struct
([BfIterator]) that can be used to iterate coordinates in
breadth-first order, from a given origin, using a provided
function to evaluate a given [Qa] position + [Qr] direction
into the next Qa position.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.Qa] that fulfills the goal and a
path in the form of a Vec<Qr>.A* search
Sqrid::astar_path] takes a movement function, an origin and a
destination, and figures out the shortest path by using A*.Vec<Qr>.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.Vec<Qr>.