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代码和示例。
经典论坛讨论: http://bbs.blueidea.com/thread-2738527-1-1.html
出处:蓝色理想
责任编辑:elesa
上一页 A*寻路,二叉堆优化及AS3实现 下一页 如虎添翼 - 使用二叉堆优化
◎进入论坛Flash专栏版块参加讨论
|