Screeps Pathfinding

为可编程的多人在线游戏 Screeps：世界提供的本地 Rust 路径查找算法。

目的

此库的目的是在本地 Rust 中实现多个路径查找算法，以避免需要跨越 WASM 边界，并在 JS 中使用 Pathfinder 进行路径查找。尽可能避免调用 JS，并在无法避免时进行明确标注。

提供多个路径查找算法的目的是允许使用比 Pathfinder 实现的跳点搜索更先进的算法，这对于具有移动目标和起始位置（如战斗期间）的路径查找将是有益的。

当前算法

• Dijkstra 的最短路径算法
• A* 算法

简单时间比较

测试在 MMO 的 Shard3 上进行。迭代分布在多个时钟周期。起始和目标位置是静态的。

1 次迭代

5 次迭代

20 次迭代

300 次迭代

值得注意的是，路径查找器在第 1 次迭代后平均开始显著下降，这很可能意味着在 JS-Land 中有一些 JIT 优化正在进行，因为我们每次都进行相同的起始-目标路径查找调用。