一个简单的 A star 寻路算法实现
我需要一个接口简单的寻路模块，所以今天写了一个 。其实之前也写过很多版本，在我上传代码时就发现我自己的 github 账号下早有同名仓库。不过，之前的版本的接口设计不太满意，直接删掉了，用这次的新版本复用老的仓库名字。
我希望达到的目标是，C 接口简单易用，且和地图本身的数据结构无关，只提供寻路功能。这样容易拓展到不同应用场景。
数据结构简单，内存开销固定，在算法执行过程中不额外分配内存。这可以方便的在多线程环境运行。
我不需要处理特别复杂和规模巨大的地图，那种场景应该额外做一些预处理。但在起点和终点的路线结果不长时（即使在大规模地图上），应该有较好的性能。
原始的 A star 算法实现最为简单，在大多数情况下有不错的表现，所以我选择了它。我知道算法可以有很多改进方法，但我觉得代码简单最为重要。
通常 A star 算法依赖一个优先队列，但我没有选择使用诸如平衡二叉树等复杂结构来实现它，而使用了最简单的单向链表。因为这样可以轻松的把全部数据全部塞在一块平坦内存中。
基础数据结构是一个用数组实现的闭散列 hash 表，使用者来决定使用多大的数组，通常使用预期路径长度的平方大小会比较合适。为了减少每次寻路的初始化成本，使用了一个 version 值表示每个 slot 的初始状态，每次调用寻路，都会把 version 递增（ O(1) 操作），这样就可以让整个 hash 表的所有 slot 复位。
寻路过程中每个尝试的节点都会加入 hash 表中，在 hash 表使用率超过一半就会中止算法，防止性能恶化。但接口在这种情况下依然会返回已经找到的离目标最近的中途点。
在不复杂的大规模地图上，通常可以通过多次调用找到完整路径。但依然建议针对大地图做更高层次的预处理。在 Youtube 上有一个 Rimworld 作者讲解 Rimworld 中区域分割系统的视频值得一看，搜索 "RimWorld Technology - Region System" 可以找到。
A star 工作中的待展开节点集是用单向链表的形式串起了 hash 表中的 slot ，而没有使用额外的优先队列结构。虽然单向链表的插入操作是 O(n) 的，但我猜想在大部分场景中，这个 n 并不算大。尤其是估价函数理想工作状态下（朝着目标直线移动），新插入的节点都是在链表一端附近的。这个猜想需要足够多的测试数据验证。
为了调试算法工作中的内部状态，模块提供了一个函数可以输出整个 hash 表的当前状态图（仅限于每个 slot 的 gscore ，即离起点的路程）。合理使用这张图，可以把算法的内部状态可视化表现。test 中使用 ascii 字符展示，但用灰度图输出图像效果会更好。
代码刚写好，尚未充分测试。但我觉得接口设计还算通用，应该会有人愿意使用。期待有更多人使用而让代码的质量提升。
Comments
Posted by: Xavier | (7) June 7, 2025 09:04 PM
Posted by: joshua | (6) May 24, 2025 05:11 PM
Posted by: 大白腿腿真好看 | (5) May 22, 2025 02:26 PM
Posted by: wstc | (4) May 20, 2025 06:21 PM
Posted by: ligil | (3) May 20, 2025 05:04 PM
Posted by: ccc | (2) May 18, 2025 10:45 PM
Posted by: tangzhaoning | (1) May 16, 2025 09:17 AM