使用 字典(或者说优先级队列) 或者 堆 来替代 列表 也可以加速 A* 算法.在这些数据结构中遍历元素非常之快,这会非常有助于你在其中搜索某一节点,同样的,在有序字典或者最小堆中,我们也能很方便的找到具有最低...优化实现
现在,我们来看一个简单的寻路优化的实现方式,基本思想就是避免开放列表和关闭列表的遍历.我们首先需要创建一个节点数组.
?...通过这个节点数组,我们就可以通过网格的位置(索引)直接访问节点数据,这对于节点遍历非常有用.一旦我们有了节点数据,我们就可以执行 A* 算法了,我们要做的第一步就是在该数组中填充原始节点,我们使用的填充函数是...下一步就是创建 firstNode 节点指针,并将其加入开放列表中.我使用了 DistanceTo 函数来计算节点的启发式距离(到目标点的评估距离,即节点的 H 值).
?...循环中我们创建了一个指向当前评估节点的指针 temp,然后我们检查他的 on_close 和 on_open 变量以获知其是否在关闭列表中或是在开放列表中.使用这种方法我们就避免了在传统 A* 算法中最大的一个性能问题