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

游戏时代群雄并起，寻路乃中原逐鹿第一步，重要性不言而喻。今习得寻路战术之首A*算法，为大家操演一番，不足之处还望不吝赐教。可以选择阅读下面的内容，或者先看看 寻路示例 、AS3类代码 及其 API文档。牛刀小试 - A*寻路算法简介eidiot挂帅出征，携令牌一枚，率人马若干，编制如下： 寻路元帅寻路总指挥，执“行动令牌”一枚和“开启士兵名录”、“关闭将军名录”各一册。凭“行动令牌”调兵遣将。 预备士兵由元帅或预备将军派往未探索区域，完成探索任务后授“开启”军衔，晋为“开启士兵”。发令派其出者为其“父将”。 开启士兵前线待命。接到“行动令牌”后晋为“预备将军”执行探索任务。 预备将军凭“行动令牌”派出预备士兵至周围未探索区域，并考察周围“开启士兵”状态，以“父将”之名节制所派士兵。归还“行动令牌”后授“关闭”军衔，晋为“关闭将军”。 关闭将军后方待命。到达终点后依次报告“父将”直至元帅，寻路任务完成。 为协调行动，特颁军令如下： “预备士兵”只能由起点或“父将”所在格横、竖或斜向移动一格，直向（横、竖）移动一格走10步，斜向一格14步（斜向是直向1.414倍，取整数），抵达后不得再移动。 所有人员需记下派出自己的“父将”、从起点到所在位置所走步数（G）、预计到达终点共需步数（F）。其中 F = G + H ，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。G 的计算是“父将”的 G 值加上“父将”位置到该位置所走步数，H 的计算是该点到终点“只走直路”所需路程。 看看战图更容易理解，从红色方格出发越过黄色障碍到达蓝色方格：图例：由图可形象看出何谓“开启士兵”、“关闭将军”：外围的绿色方格为“开启士兵”，“前线待命”，随时可向外继续探索。内围的紫色方格是“关闭将军”，从终点开始沿箭头寻其“父将”直至起点即得最终路径。战前会议结束，拔营出征。 首先派出编号为0的“预备士兵”侦查起点，然后升其为“开启士兵”，列入“开启士兵名录”。 检查“开启士兵名录”，找出F值最低的“开启士兵”（只有一名人员，当然是0号），发出“行动令牌”派其执行探索任务。 0号“开启士兵”接到“行动令牌”，晋为“预备将军”，探索周围格子。 向周围8个格子分别派出编号为1到8的“预备士兵”，成为这八名“预备士兵”的“父将”。 八名“预备士兵”到达方格后计算G值和F值，报告0号“父将”，晋为“开启士兵”。 0号“预备将军”收到八名“开启士兵”的报告，归还“行动令牌”，晋为“关闭将军”。 元帅收回“行动令牌”，将0号加入“关闭将军名录”，1到8号加入“开启士兵名录”。 此过程结果如下（方格右上角数字是人员编号，左下角是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号加入“关闭将军名录”。 此过程结果如下：第二轮结束，元帅再次检查“开启士兵名录”。此时还有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代码和示例。如虎添翼 - 使用二叉堆优化如何让A*寻路更快？元帅三顾茅庐，请来南阳二叉堆先生帮忙优化寻找“开启士兵名录”中最低F值的过程，将寻路速度提高了2到3倍，而且越大的地图效果越明显。下面隆重介绍二叉堆先生：下图是一个二叉堆的例子，形式上看，它从顶点开始，每个节点有两个子节点，每个子节点又各自有自己的两个子节点；数值上看，每个节点的两个子节点都比它大或和它相等。在二叉堆里我们要求： 最小的元素在顶端 每个元素都比它的父节点大，或者和父节点相等。 只要满足这两个条件，其他的元素怎么排都行。如上面的例子，最小的元素10在最顶端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三层，更大的30反而在第二层。这样一“堆”东西我们在程序中怎么用呢？幸运的是，二叉堆可以用一个简单的一维数组来存储，如下图所示。假设一个元素的位置是n（第一个元素的位置为1，而不是通常数组的第一个索引0），那么它两个子节点分别是 n 2 和 n 2 + 1 ，父节点是n除以2取整。比如第3个元素（例中是20）的两个子节点位置是6和7，父节点位置是1。对于二叉堆我们通常有三种操作：添加、删除和修改元素： 添加元素首先把要添加的元素加到数组的末尾，然后和它的父节点（位置为当前位置除以2取整，比如第4个元素的父节点位置是2，第7个元素的父节点位置是3）比较，如果新元素比父节点元素小则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它大，或者已经到达顶端，及第1的位置。 删除元素删除元素的过程类似，只不过添加元素是“向上冒”，而删除元素是“向下沉”：删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果较小的子节点比它小就将它们交换，直到两个子节点都比它大。 修改元素和添加元素完全一样的“向上冒”过程，只是要注意被修改的元素在二叉堆中的位置。 可以看出，使用二叉堆只需很少的几步就可以完成排序，很大程度上提高了寻路速度。关于二叉堆先生需要了解的就是这么多了，下面来看看他怎么帮助元帅工作： 每次派出的“预备士兵”都会获得一个唯一的编号（ID），一直到寻路结束，它所有的数据包括位置、F值、G值、“父将”编号都将按这个ID存储。 每次有新的“开启士兵”加入，二叉堆先生将它的编号加入“开启士兵名录”并重新排序，使F值最低的ID始终排在最前面 当有“开启士兵”晋为“关闭将军”，删除“开启士兵名录”的第一个元素并重新排序 当某个“开启士兵”的F值被修改，更新其数据并重新排序 注意，“开启士兵名录”里存的只是人员的编号，数据全都另外存储。不太明白？没关系，元帅将在 第三部分 来次真刀实枪的大演兵。锋芒毕露 - AS3代码和示例地形数据不属于A*寻路的范围，这里定义一个 IMapTileModel 接口，由其它（模型）类来实现地图通路的判断。其它比如寻路超时的判断这里也不介绍，具体参考 AStar类及其测试代码。这里只介绍三部分主要内容： 数据存储 寻路过程 列表排序 数据存储首先看看三个关键变量：private var m_openList : Array; /开放列表，存放节点IDprivate 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值private var m_fatherList : Array; /节点的父节点(ID)这些数据列表都以节点ID为索引顺序存储。看看代码如何工作：/每次取出开放列表最前面的IDcurrId = this.m_openList0;/读取当前节点坐标currNoteX = this.m_xListcurrId;currNoteY = this.m_yListcurrId;还有一个很关键的变量：private var m_noteMap : Array; /节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID使用 m_noteMap 可以方便的存取任何位置节点的开启关闭状态，并可取其ID进而存取其它数据。m_noteMap 是个三维数组，第一维y坐标（第几行），第二维x坐标（第几列），第三维节点状态和ID。判断点(p_x, p_y)是否在开启列表中：return this.m_noteMapp_yp_xNOTE_OPEN;寻路过程AStar类 寻路的方法是 find() :/* 开始寻路* param p_startX 起点X坐标* param p_startY 起点Y坐标* param p_endX 终点X坐标* param p_endY 终点Y坐标* return 找到的路径(二维数组 : p_startX, p_startY, . , p_endX, p_endY)*/ public function find(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : Array/* 寻路 */注意这里返回数据的形式：从起点到终点的节点数组，其中每个节点为一维数组x, y的形式。为了加快速度，类里没有使用Object或是Point，节点坐标全部以数组形式存储。如节点note的x坐标为note0,y坐标为note1。下面开始寻路，第一步将起点添加到开启列表：this.openNote(p_startX, p_startY, 0, 0, 0);openNote() 方法将节点加入开放列表的同时分配一个唯一的ID、按此ID存储数据、对开启列表排序。接下来是寻路过程：while (this.m_openCount 0) /每次取出开放列表最前面的ID currId = this.m_openList0; /将编码为此ID的元素列入关闭列表 this.closeNote(currId); /如果终点被放入关闭列表寻路结束，返回路径 if (currNoteX = p_endX & currNoteY = p_endY) return this.getPath(p_startX, p_startY, currId); /.每轮寻路过程/开放列表已空，找不到路径return null;每轮的寻路：/获取周围节点，排除不可通过和已在关闭列表中的aroundNotes = this.getArounds(currNoteX, currNoteY);/对于周围每个节点for each (var note : Array in aroundNotes) /计算F和G值 cost = this.m_movementCostListcurrId + (note0 = currNoteX | note1 = currNoteY) ? COST_STRAIGHT : COST_DIAGONAL); score = cost + (Math.abs(p_endX - note0) + Math.abs(p_endY - note1) * COST_STRAIGHT; if (this.isOpen(note0, note1) /如果节点已在开启列表中 /测试节点的ID checkingId = this.m_noteMapnote1note0NOTE_ID; /如果新的G值比节点原来的G值小,修改F,G值，换父节点 if(cost 1) /父节点的位置 father = Math.floor(p_index 2); /如果该节点的F值小于父节点的F值则和父节点交换 if (this.getScore(p_index) this.getScore(father) change = this.m_openListp_index - 1; this.m_openListp_index - 1 = this.m_openListfather - 1; this.m_openListfather - 1 = change; p_index = father; else break; /* 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动 */private function backNote() : void /尾部的节点被移到最前面 var checkIndex :