分层路径查找

一个 Rust 包，用于使用 HPA*（分层路径查找 A*）和分层 Dijkstra 在网格上查找路径。

描述

通过缓存路径段以形成节点图来提供在类似于网格的结构上快速查找路径的算法。在该图中查找路径比在网格本身上快得多，但结果路径略差于最佳路径。

基于论文"近似最优分层路径查找"的实现。

优点

• 与常规算法（A*，Dijkstra）相比，查找路径要快得多
• 总是正确的：如果路径存在，则找到路径；如果不存在，则找不到路径
  • 这意味着分层路径查找可以作为启发式方法来检查路径是否存在以及其大致长度（上界）

缺点

• 路径略差（在大多数情况下可以忽略不计）
• 创建缓存需要时间（仅在开始时发生一次）
• 网格的更改需要更新缓存
  • 每当一个块中的瓦片发生变化时，整个块都需要重新计算其路径。性能取决于块的大小（可配置）和块中的节点数

用例

在网格上查找路径是一项昂贵的操作。考虑以下设置

为了使用常规 A* 计算从起点到终点的路径，有必要检查很多瓦片

（这只是一个简单的例子，更长的路径需要二次增加瓦片检查，不可达的目标需要检查每个瓦片）

分层路径查找提供的解决方案是将网格分成块，并将块入口之间的路径缓存为节点图

这使得可以通过将起点和终点连接到块内的节点，并使用图来生成路径

示例

use hierarchical_pathfinding::prelude::*;

let mut pathfinding = PathCache::new(
    (width, height),   // the size of the Grid
    |(x, y)| walking_cost(x, y),   // get the cost for walking over a Tile
    ManhattanNeighborhood::new(width, height),   // the Neighborhood
    PathCacheConfig::with_chunk_size(3),   // config
);

let start = (0, 0);
let goal = (4, 4);

// find_path returns Some(Path) on success
let path = pathfinding.find_path(
    start,
    goal,
    |(x, y)| walking_cost(x, y),
);

if let Some(path) = path {
    println!("Number of steps: {}", path.length());
    println!("Total Cost: {}", path.cost());
    for (x, y) in path {
        println!("Go to {}, {}", x, y);
    }
}