第二轮结束，元帅再次检查“开启士兵名录”。此时还有7名“开启士兵”，5号和8号的F值都为最低的54，选择不同寻路的结果也将不同。元帅选择了最后加入的8号“开启士兵”发出“行动令牌”，过程同上，不赘述，结果如下：

重复这个过程直到某位“关闭将军”站到了终点上（或者“开启士兵”探测到了终点，这样更快捷，但某些情况找到的路径不够短），亦即找到了路径；或是“开启士兵名录”已空，无法到达终点。

下面整理一下全过程并翻译成“标准语言”，首先是各名词：
* “开启士兵名录” - 开启列表 - open list
* “关闭将军名录” - 关闭列表 - closed list
* “父将” - 父节点 - parent square
* F - 路径评分
* G - 起点到该点移动损耗
* H - 该点到终点（启发式）预计移动损耗

寻路过程：
* 1, 将起点放入开启列表
* 2, 寻找开放列表中F值最低的节点作为当前节点
* 3, 将当前节节点切换到关闭列表
* 4, 如果当前节点是终点则路径被找到，寻路结束
* 5, 对于其周围8个节点:
　o 如果不可通过或已在关闭列表，跳过，否则：
　o 如果已在开放列表中，检查新路径是否更好。如果新G值更低则更新其G值并改当前节点为其父节点，否则跳过
　 o 如果是可通过区域则放入开启列表，计算这一点的F、G、H值，并记当前节点为其父节点
* 6, 如果开启列表空了，则无法到达目标，路径不存在。否则回到2

再翻译成“编程语言”？请看第三部分，锋芒毕露 - AS3代码和示例。

进入织梦论坛讨论：
http://www.17zm.net/forum/

如何让A*寻路更快？元帅三顾茅庐，请来南阳二叉堆先生帮忙优化寻找“开启士兵名录”中最低F值的过程，将寻路速度提高了2到3倍，而且越大的地图效果越明显。下面隆重介绍二叉堆先生：

下图是一个二叉堆的例子，形式上看，它从顶点开始，每个节点有两个子节点，每个子节点又各自有自己的两个子节点；数值上看，每个节点的两个子节点都比它大或和它相等。

在二叉堆里我们要求：
* 最小的元素在顶端
* 每个元素都比它的父节点大，或者和父节点相等。

只要满足这两个条件，其他的元素怎么排都行。如上面的例子，最小的元素10在最顶端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三层，更大的30反而在第二层。

这样一“堆”东西我们在程序中怎么用呢？幸运的是，二叉堆可以用一个简单的一维数组来存储，如下图所示。

假设一个元素的位置是n（第一个元素的位置为1，而不是通常数组的第一个索引0），那么它两个子节点分别是 n × 2 和 n × 2 + 1 ，父节点是n除以2取整。比如第3个元素（例中是20）的两个子节点位置是6和11，父节点位置是1。

对于二叉堆我们通常有三种操作：添加、删除和修改元素：

 * 添加元素
首先把要添加的元素加到数组的末尾，然后和它的父节点（位置为当前位置除以2取整，比如第4个元素的父节点位置是2，第7个元素的父节点位置是3）比较，如果新元素比父节点元素小则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它大，或者已经到达顶端，及第1的位置。
* 删除元素
删除元素的过程类似，只不过添加元素是“向上冒”，而删除元素是“向下沉”：删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果较小的子节点比它小就将它们交换，直到两个子节点都比它大。
* 修改元素
和添加元素完全一样的“向上冒”过程，只是要注意被修改的元素在二叉堆中的位置。

可以看出，使用二叉堆只需很少的几步就可以完成排序，很大程度上提高了寻路速度。

关于二叉堆先生需要了解的就是这么多了，下面来看看他怎么帮助元帅工作：   

* 每次派出的“预备士兵”都会获得一个唯一的编号（ID），一直到寻路结束，它所有的数据包括位置、F值、G值、“父将”编号都将按这个ID存储。
* 每次有新的“开启士兵”加入，二叉堆先生将它的编号加入“开启士兵名录”并重新排序，使F值最低的ID始终排在最前面
* 当有“开启士兵”晋为“关闭将军”，删除“开启士兵名录”的第一个元素并重新排序
* 当某个“开启士兵”的F值被修改，更新其数据并重新排序

注意，“开启士兵名录”里存的只是人员的编号，数据全都另外存储。不太明白？没关系，元帅将在 第三部分 来次真刀实枪的大演兵。

进入织梦论坛讨论：
http://www.17zm.net/forum/

地形数据不属于A*寻路的范围，这里定义一个 IMapTileModel 接口，由其它（模型）类来实现地图通路的判断。其它比如寻路超时的判断这里也不介绍，具体参考 AStar类及其测试代码。这里只介绍三部分主要内容：

* 数据存储
    * 寻路过程
    * 列表排序

数据存储
首先看看三个关键变量：

private var m_openList : Array; //开放列表，存放节点ID
private var m_openCount : int; //当前开放列表中节点数量
private var m_openId : int; //节点加入开放列表时分配的唯一ID(从0开始)

开放列表 m_openList 是个二叉堆（一维数组），F值最小的节点始终排在最前。为加快排序，开放列表中只存放节点ID ，其它数据放在各自的一维数组中：

private var m_xList : Array; //节点x坐标
private var m_yList : Array; //节点y坐标
private var m_pathScoreList : Array; //节点路径评分F值
private var m_movementCostList : Array; //(从起点移动到)节点的移动耗费G值
privat

上一页  [1] [2] [3] [4] 下一页