在A*寻路中使用二叉堆

　2006-07-23 11:33:11　来源：WEB开发网　　　

核心提示： 对开启列表的元素重排序就如在主文章中描述的，有时候你会发现现有的开启列表中的元素会改变，在A*寻路中使用二叉堆(9)，这种情况发生的时候，我们不必要取出这个元素重新来过，注释详尽，有C++和Blitz两个版本，只要从当前位置开始，用它新的（更低的）F值和它的父节点比较

对开启列表的元素重排序

就如在主文章中描述的，有时候你会发现现有的开启列表中的元素会改变。这种情况发生的时候，我们不必要取出这个元素重新来过。只要从当前位置开始，用它新的（更低的）F值和它的父节点比较。如果它的F值低到足以替换它的父节点，你就把它替换掉（不然你就会得到一个错误的堆，一切都完了）。一般，你使用和“在堆中添加新元素”的小节中相同的代码，并做额外处理如下：

不幸的是，因为你的数据是在一个庞大，无序的堆里，你需要遍历整个堆查找先有开启列表中的元素。你主要要查找由openX(openList()) 和openY(openList())获取的确切坐标的格子，找到之后，你就可以从那一点开始，像往常那样做必要的比较和交换。

最后的注解

好了，我希望你仍然能读懂，没有被搞昏头。如果你不着急，并且希望在自己的寻路算法中使用二叉堆，那么这就是我的建议。

首先，把二叉堆放一放。把注意力放在你的A*寻路算法上，使用简单点的排序算法，保证算法正常工作没有bug。一开始你并不需要它很快速，你只需要它能工作。

其次，在你把二叉堆添加到代码中之前，试着把二叉堆写成独立的功能，用适当的方法添加和删除元素。确保你写的程序中，可以看到整个过程中每一步的操作，也许可以把结果打印在屏幕上，如果你愿意。你还得包含一些中途退出的代码，以便在必要的时候结束整个流程。如果二叉堆写的不对，你很容易就会陷入到无限循环中。

一旦你确信两个程序都运行无误，备份他们，然后开始把他们结合起来。除非你比我还聪明，否则一开始你难免遇到麻烦。输出都是些错误信息并且/或者看到寻路者因为bug走出各种怪异的方向。不过最终你会搞定一切。

进一步阅读

和以往一样，网上有很多其他的关于这个话题的好文章。这里有些入门的。第一篇用图示。第二篇说明了怎么用一个简单的数组（如果我的说明很麻烦的话）实现二叉堆。第三篇探讨了寻路算法中堆的一般用途。