grid_pathfinding

基于网格的路径搜索系统。实现了跳跃点搜索，并使用改进的剪枝规则进行快速路径搜索。预先计算了连通分量，以避免无路径时进行洪水填充。支持4邻域和8邻域网格，并为4邻域实现了JPS的定制变体。

示例

以下提供了一个简单的8网格示例，说明如何设置基本问题和寻找路径。

use grid_pathfinding::PathingGrid;
use grid_util::grid::Grid;
use grid_util::point::Point;

// In this example a path is found on a 3x3 grid with shape
//  ___
// |S  |
// | # |
// |  E|
//  ___
// where
// - # marks an obstacle
// - S marks the start
// - E marks the end

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(2, 2);
    let path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    println!("Path:");
    for p in path {
        println!("{:?}", p);
 }
}

这假设了一个8邻域，这是默认的网格类型。可以通过添加以下行来解决4邻域的问题，不允许对角移动，如示例simple_4中所示：

pathing_grid.allow_diagonal_move = false;

在生成组件之前，这已经在示例中完成。

有关使用多个目标和生成航点的路径搜索示例，请参阅示例。

基准测试

系统可以使用来自Moving AI 2D路径搜索基准测试的场景进行基准测试。提供了一般支持加载这些文件的grid_pathfinding_benchmark工具包。使用cargo bench默认执行的基准测试运行了来自Dragon Age: Origins的三个场景集：dao/arena、dao/den312和dao/arena2（或使用正交算法时为dao/den009d）。运行这些场景需要相应的地图和场景文件保存在名为maps/dao和scenarios/dao的文件夹中。

可以使用以下方式设置基准：

cargo bench -- --save-baseline main

可以使用以下方式将新运行的结果与基准进行比较：

cargo bench -- --baseline main

性能

使用3.3 GHz的i5-6600四核处理器，使用JPS算法允许对角线搜索且禁用改进的剪枝，运行dao/arena2场景集需要134毫秒。使用默认的邻域生成方式，如正常的A*算法（通过设置GRAPH_PRUNING = false启用）将此时间增加到1.37秒，相差10倍。一般来说，随着地图的增大，相对差异也会增加，对于较小的地图dao/arena集（846微秒和1.34毫秒，分别有和没有剪枝）。

现有的C++ JPS实现运行相同场景大约需要60毫秒。已知最快的求解器是l1-path-finder（用JavaScript实现）使用带有地标（4邻域）的A*算法只需38毫秒即可完成。这表明在搜索速度方面还有很大的改进空间。

工具包的目标

该工具包的长期目标是提供一个快速现成的网格路径搜索实现。