一个简单的 A star 寻路算法实现
💡
原文中文，约1300字，阅读约需3分钟。
📝
内容提要
作者开发了一个基于 A* 算法的寻路模块，使用单向链表和闭散列哈希表优化性能，适用于多线程环境和大规模地图，接口设计通用，便于扩展。期待用户反馈以提升代码质量。
🎯
关键要点
- 作者开发了一个基于 A* 算法的寻路模块，适用于多线程环境和大规模地图。
- 数据结构简单，内存开销固定，算法执行过程中不额外分配内存。
- 接口设计简单易用，与地图数据结构无关，便于扩展。
- 选择了原始的 A* 算法实现，认为代码简单最为重要。
- 使用单向链表代替复杂的优先队列结构，方便数据存储。
- 基础数据结构为闭散列哈希表，使用 version 值来复位 hash 表的状态。
- 在寻路过程中，若 hash 表使用率超过一半则中止算法，但仍返回最近的中途点。
- 建议针对大地图进行更高层次的预处理，参考 Rimworld 的区域分割系统。
- 待展开节点集使用单向链表串起 hash 表中的 slot，插入操作为 O(n)。
- 模块提供函数输出 hash 表的当前状态图，便于可视化算法内部状态。
- 代码尚未充分测试，但接口设计通用，期待用户反馈以提升代码质量。
❓
延伸问答
A* 算法的寻路模块适用于什么环境？
该模块适用于多线程环境和大规模地图。
这个寻路模块的内存管理是怎样的？
数据结构简单，内存开销固定，算法执行过程中不额外分配内存。
为什么选择单向链表而不是优先队列？
选择单向链表是因为它可以方便地将所有数据存储在一块平坦内存中，简化结构。
如何处理寻路过程中 hash 表的状态？
使用 version 值来复位 hash 表的状态，确保每次调用寻路时都能快速初始化。
在寻路过程中，如果 hash 表使用率超过一半会发生什么？
算法会中止，但仍会返回离目标最近的中途点。
这个寻路模块的接口设计有什么特点？
接口设计简单易用，与地图数据结构无关，便于扩展到不同应用场景。
➡️
