然后我们使用这些泛化来实现一些网格算法

• bf: 广度优先遍历和搜索。
• astar：目标位置 Pos 的 A* 搜索。
• ucs：均成本搜索。

所有基本类型都具有标准的 iter、iter_mut、extend、as_ref 以及转换操作，这些都是预期的。

基本类型

Pos：绝对坐标，位置

Pos 类型表示正方形网格中的绝对位置。该类型本身接受网格的高度和宽度作为 const 泛型参数。

我们通常应该为使用的网格大小创建一个类型别名

use sqrid;

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

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

我们只能生成在传入的维度内的 Pos 实例。

Dir：相对坐标，方向，移动

Dir 类型表示一个正方形的一个相对移动。它只能是 8 个主要和次要方向之一：Dir::N、Dir::NE、Dir::E、Dir::SE、Dir::S、Dir::SW、Dir::W、Dir::NW。

它是路径的构建块，遍历 Pos 邻居等。它有效地表示图中由 Pos 类型表示的边。

所有遍历 Dir 值的函数都接受一个布尔 const 参数，指定是否应考虑次要方向（NE、SE、SW、NW）。

我们可以通过使用Sqrid类型和grid_create宏来创建所需的类型。然后，我们可以使用Grid::line和Grid::line_mut来与特定行交互，或者使用as_ref（见std::convert::AsRef）和as_mut（见std::convert::AsMut）与整个底层数组交互。

使用示例

type Sqrid = sqrid::sqrid_create!(3, 3, 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, { Sqrid::WIDTH }, { Sqrid::HEIGHT },
                              { (Sqrid::WIDTH * Sqrid::HEIGHT) as usize }>;

// 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：一个基于位图的Pos索引布尔网格

Gridbool是对布尔网格的紧凑抽象。

该类型可以通过gridbool_create宏创建。它针对获取和设置特定坐标的值进行了优化，但也可以以次优性能获取所有true/false坐标 - 在这种情况下，时间是与网格大小成正比，而不是与true/false值的数量成正比。

使用示例

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

// 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：算法的入口点

Pos类型和一些Dir类型的方法需要通常在应用程序内部不改变的const泛型参数。同时，Grid和Gridbool也需要从网格宽度和高度推导出来的进一步参数，但由于某些Rust限制，必须显式指定。

为了简化这些类型的创建，我们提供了Sqrid类型，它累积所有const泛型参数，可以通过宏来创建其他类型。

示例用法

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);

算法

广度优先遍历

Sqrid::bf_iter函数实例化一个迭代器结构体（bf::BfIterator），它可以用于迭代从给定原点开始，使用提供的函数评估给定的Pos位置 + Dir方向到下一个Pos位置。

示例用法

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

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

广度优先搜索

Sqrid::bfs_path接受一个起点、一个移动函数和一个目标函数，通过广度优先迭代找出到达目标的最短路径。

该函数返回满足目标的 Pos 以及形式为 Vec<Dir> 的路径。

示例用法

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);
}

A* 搜索

Sqrid::astar_path 接收一个移动函数、起点和终点，并通过使用 A* 算法计算出最短路径。

该函数返回形式为 Vec<Dir> 的路径。

示例用法

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

一致代价搜索

Sqrid::ucs_path 接收一个移动代价函数、起点和终点，并通过使用一致代价搜索（本质上是一种 Dijkstra 算法的变体）找到代价最低的路径。

该函数返回形式为 Vec<Dir> 的路径。

示例用法

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);
}