A*寻路,二叉堆优化及AS3实现

eidiot挂帅出征，携令牌一枚，率人马若干，编制如下： vd;k;l www.it55.com rdfg

* 寻路元帅  
寻路总指挥，执“行动令牌”一枚和“开启士兵名录”、“关闭将军名录”各一册。凭“行动令牌”调兵遣将。
* 预备士兵  
由元帅或预备将军派往未探索区域，完成探索任务后授“开启”军衔，晋为“开启士兵”。发令派其出者为其“父将”。
* 开启士兵
前线待命。接到“行动令牌”后晋为“预备将军”执行探索任务。
* 预备将军
凭“行动令牌”派出预备士兵至周围未探索区域，并考察周围“开启士兵”状态，以“父将”之名节制所派士兵。归还“行动令牌”后授“关闭”军衔，晋为“关闭将军”。
* 关闭将军
后方待命。到达终点后依次报告“父将”直至元帅，寻路任务完成。

为协调行动，特颁军令如下： vd;k;l www.it55.com rdfg

* “预备士兵”只能由起点或“父将”所在格横、竖或斜向移动一格，直向（横、竖）移动一格走10步，斜向一格14步（斜向是直向1.414倍，取整数），抵达后不得再移动。
* 所有人员需记下派出自己的“父将”、从起点到所在位置所走步数（G）、预计到达终点共需步数（F）。其中 F = G + H ，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。G 的计算是“父将”的 G 值加上“父将”位置到该位置所走步数，H 的计算是该点到终点“只走直路”所需路程。

www.it55.com

看看战图更容易理解，从红色方格出发越过黄色障碍到达蓝色方格： 45398 www.it55.com it55学习IT知识，享受IT生活 4dfkjn

http://www.it55.com/

图例：

vd;k;l www.it55.com rdfg

sflj www.it55.com kg^&fgd

由图可形象看出何谓“开启士兵”、“关闭将军”：外围的绿色方格为“开启士兵”，“前线待命”，随时可向外继续探索。内围的紫色方格是“关闭将军”，从终点开始沿箭头寻其“父将”直至起点即得最终路径。

战前会议结束，拔营出征。 vd;k;l www.it55.com rdfg

* 首先派出编号为0的“预备士兵”侦查起点，然后升其为“开启士兵”，列入“开启士兵名录”。
* 检查“开启士兵名录”，找出F值最低的“开启士兵”（只有一名人员，当然是0号），发出“行动令牌”派其执行探索任务。
* 0号“开启士兵”接到“行动令牌”，晋为“预备将军”，探索周围格子。
* 向周围8个格子分别派出编号为1到8的“预备士兵”，成为这八名“预备士兵”的“父将”。
* 八名“预备士兵”到达方格后计算G值和F值，报告0号“父将”，晋为“开启士兵”。
* 0号“预备将军”收到八名“开启士兵”的报告，归还“行动令牌”，晋为“关闭将军”。
* 元帅收回“行动令牌”，将0号加入“关闭将军名录”，1到8号加入“开启士兵名录”。 vd;k;l www.it55.com rdfg

此过程结果如下（方格右上角数字是人员编号，左下角是G，右下角是H，左上角是F）：

第一轮探索任务完成，元帅开始检查“开启士兵名录”。此时名录中有8名人员，其中1号F值最低为40（起点右移一格，G值为10，到终点平移3格，H值为30，F = G + H = 40），向其发出“行动令牌”。

* 1号“开启士兵”接到“行动令牌”，晋为“预备将军”，探索周围格子。
* 周围8个格子中有3格障碍，跳过。一格是“关闭将军”，跳过。其余四格是“开启士兵”，检查如果从该位置过去G值是否更低。以2号为例，如果从1 号过去G值为 10 + 14 = 24 （1号的G值加上1号到2号的步数）,而2号原来的G值是10，不做处理（如果此时发现新的G值更低，则更新2号的G值，并改2号的“父将”为1号）。其他类推。
* 1号检测完周围的方格，不需做任何处理，归还“行动令牌”，晋为“关闭将军”。
* 元帅收回“行动令牌”，将1号加入“关闭将军名录”。

此过程结果如下：

sflj www.it55.com kg^&fgd

免费资源www.it55.com

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

免费资源www.it55.com

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

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

it55.com

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

（阅读次数：）