A*寻路,二叉堆优化及AS3.0实现_as3.0 8方位寻路-程序员宅基地

A*寻路,二叉堆优化及AS3.0实现
本文作者:dmh2002 发布于:2008-2-12 分类:AS3 经验/技巧/游戏 点击:133

A*寻路,二叉堆优化及AS3实现
 游戏时代群雄并起,寻路乃中原逐鹿第一步,重要性不言而喻。今习得寻路战术之首A*算法,为大家操演一番,不足之处还望不吝赐教。可以选择阅读下面的内容,或者先看看 寻路示例 、AS3类代码 及其 API文档。
牛刀小试 - A*寻路算法简介
如虎添翼 - 使用二叉堆优化
锋芒毕露 - AS3代码和示例

牛刀小试 - 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个节点:
如果不可通过或已在关闭列表,跳过,否则:
如果已在开放列表中,检查新路径是否更好。如果新G值更低则更新其G值并改当前节点为其父节点,否则跳过
如果是可通过区域则放入开启列表,计算这一点的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; //开放列表,存放节点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值
private var m_fatherList : Array; //节点的父节点(ID)
  这些数据列表都以节点ID为索引顺序存储。看看代码如何工作:
//每次取出开放列表最前面的ID
currId = this.m_openList[0];
//读取当前节点坐标
currNoteX = this.m_xList[currId];
currNoteY = this.m_yList[currId];
  还有一个很关键的变量:
private var m_noteMap : Array; //节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID
  使用 m_noteMap 可以方便的存取任何位置节点的开启关闭状态,并可取其ID进而存取其它数据。m_noteMap 是个三维数组,第一维y坐标(第几行),第二维x坐标(第几列),第三维节点状态和ID。判断点(p_x, p_y)是否在开启列表中:
return this.m_noteMap[p_y][p_x][NOTE_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坐标为note[0],y坐标为note[1]。
  下面开始寻路,第一步将起点添加到开启列表:
this.openNote(p_startX, p_startY, 0, 0, 0);
  openNote() 方法将节点加入开放列表的同时分配一个唯一的ID、按此ID存储数据、对开启列表排序。接下来是寻路过程:
while (this.m_openCount > 0)
{
    //每次取出开放列表最前面的ID
    currId = this.m_openList[0];
    //将编码为此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_movementCostList[currId] + ((note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL);
    score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
    if (this.isOpen(note[0], note[1])) //如果节点已在开启列表中
    {
        //测试节点的ID
    checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
    //如果新的G值比节点原来的G值小,修改F,G值,换父节点
    if(cost < this.m_movementCostList[checkingId])
    {
        this.m_movementCostList[checkingId] = cost;
        this.m_pathScoreList[checkingId] = score;
        this.m_fatherList[checkingId] = currId;
        //对开启列表重新排序
        this.aheadNote(this.getIndex(checkingId));
    }
    } else //如果节点不在开放列表中
    {
    //将节点放入开放列表
    this.openNote(note[0], note[1], score, cost, currId);
    }
}
  从终点开始依次沿父节点回到到起点,返回找到的路径:
/**
* 获取路径
* @param p_startX    起始点X坐标
* @param p_startY    起始点Y坐标
* @param p_id        终点的ID
* @return             路径坐标数组
*/       
private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
{
    var arr : Array = [];
    var noteX : int = this.m_xList[p_id];
    var noteY : int = this.m_yList[p_id];
    while (noteX != p_startX || noteY != p_startY)
    {
    arr.unshift([noteX, noteY]);
    p_id = this.m_fatherList[p_id];
    noteX = this.m_xList[p_id];
    noteY = this.m_yList[p_id];
    }
    arr.unshift([p_startX, p_startY]);
    this.destroyLists();
    return arr;
}
列表排序
  这部分看代码和注释就可以了,不多说:
/** 将(新加入开放别表或修改了路径评分的)节点向前移动 */
private function aheadNote(p_index : int) : void
{
    var father : int;
    var change : int;
    //如果节点不在列表最前
    while(p_index > 1)
    {
    //父节点的位置
    father = Math.floor(p_index / 2);
    //如果该节点的F值小于父节点的F值则和父节点交换
    if (this.getScore(p_index) < this.getScore(father))
    {
        change = this.m_openList[p_index - 1];
        this.m_openList[p_index - 1] = this.m_openList[father - 1];
        this.m_openList[father - 1] = change;
        p_index = father;
    } else
    {
        break;
    }
    }
}
/** 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动 */
private function backNote() : void
{
    //尾部的节点被移到最前面
    var checkIndex : int = 1;
    var tmp : int;
    var change : int;
    while(true)
    {
    tmp = checkIndex;
    //如果有子节点
    if (2 * tmp <= this.m_openCount)
    {
        //如果子节点的F值更小
        if(this.getScore(checkIndex) > this.getScore(2 * tmp))
        {
        //记节点的新位置为子节点位置
        checkIndex = 2 * tmp;
        }
        //如果有两个子节点
        if (2 * tmp + 1 <= this.m_openCount)
        {
        //如果第二个子节点F值更小
        if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
        {
            //更新节点新位置为第二个子节点位置
            checkIndex = 2 * tmp + 1;
        }
        }
    }
    //如果节点位置没有更新结束排序
    if (tmp == checkIndex)
    {
        break;
    }
    //反之和新位置交换,继续和新位置的子节点比较F值
    else
    {
        change = this.m_openList[tmp - 1];
        this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
        this.m_openList[checkIndex - 1] = change;
    }
    }
}
  其中 getScore() 方法:
/**
* 获取某节点的路径评分F值
* @param p_index    节点在开启列表中的索引(从1开始)
*/       
private function getScore(p_index : int) : int
{
    //开启列表索引从1开始,ID从0开始,数组索引从0开始
    return this.m_pathScoreList[this.m_openList[p_index - 1]];
}
查看寻路示例
下载示例源文件 (zip 6.44)
参考文章:
A* Pathfinding for Beginners (中文)
Using Binary Heaps in A* Pathfinding (中文)

文章来自: 闪客居(www.flashas.net) 详文参考:http://www.flashas.net/html/flashas/aschuji/AS_3_0/20070607/1900.html
本文出自: dmh2002's Blog, 原文地址: http://dmh2002.com/post/5.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/chqj_163/article/details/82880613

智能推荐

VS2008 无法启动程序 系统找不到指定的文件_vs2008 无法启动程序 没有更多文件-程序员宅基地

文章浏览阅读1.4k次。一直用VS2008挺好的 但今天不知道怎么 启动调试的时候突然弹出在上查到了一些资料原因:是因为我前两天为了测试新做的网站 安装了绿色版的IE6 由于系统是Vista 装了这个IE6也跑不起来 只好把它卸载了!就是因为它所以造成这个错误的发生,在卸载的时候它将注册表中的IE项也给删除了(oh,my god!)解决方案:1、打开注册表 (开始 -》 运行 -》 reged_vs2008 无法启动程序 没有更多文件

移动设备分辨率以及适配问题_480x854的dpi-程序员宅基地

文章浏览阅读1.3k次。手机常见分辨率:4:3VGA 640*480 (Video Graphics Array)QVGA 320*240 (Quarter VGA)HVGA 480*320 (Half-size VGA)SVGA 800*600 (Super VGA)5:3WVGA 800*480 (Wide VGA)16:9FWVGA 854*480 (_480x854的dpi

html一发入魂-程序员宅基地

文章浏览阅读95次。初识HTML什么是HTML:超文本标记语言:超文本包括:文字图片音频视频动画等html5+css3自带浏览器跨平台:微软google苹果MozillaW3C :万维网联盟结构化标准语言(html(超文本语言),xml(配置文件))表现标准语言(css)行为标准(DOM ,ECMAScript)常见IDE:记事本DWIDEAWebStorm网页基本标签基本标签:<!-- 标题标签 --> <h1>一级标签</h

springboot中简单创建webservice服务_spring-boot-starter-web-services-程序员宅基地

文章浏览阅读2.1k次。添加依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web-services</artifactId> </dependency>添加配置类不添加配置类也可以在springboot的启动类了里面发布服务,但是那样_spring-boot-starter-web-services

java列表上移下移实现_where advert_sort <![cdata[ > ]]> #{oldsort}-程序员宅基地

文章浏览阅读283次。java列表上移下移实现列表插入时排序字段的最大值+5UPDATE `tb_test` t, <if test="type == 'up'"> (SELECT IFNULL(MAX(sort), #{sort}) AS msort FROM `tb_test` WHERE <![CDATA[ sort < #{sort} ]]>) t1 </if> <if test="type == 'down'"> _where advert_sort ]]> #{oldsort}

AX2012 常用表关系(客户地址,联系信息)_ax2012 地址的er图-程序员宅基地

文章浏览阅读1.8k次。//客户地址信息static void CustAddressInformation(Args _args){ CustTable custTable; DirPartyTable dirPartyTable; DirPartyLocation dirPartyLocation; LogisticsL_ax2012 地址的er图

随便推点

经典面试题之 : malloc/free和new/delete 的区别_面试题 malloc/free 和 new/delete区别-程序员宅基地

文章浏览阅读629次。1 malloc/free和new/delete 共同点malloc/free和new/delete的共同点是:都是从堆上申请空间,并且需要用户手动释放2 malloc/free 和 new/delete的不同1 malloc/free 是函数 new/delete 是操作符2 malloc 申请的空间不可以初始化,而new出来的空间可以初始化3 malloc 申请空间时需..._面试题 malloc/free 和 new/delete区别

JAIN SIP instantmessaging学习_jain-sip notify消息-程序员宅基地

文章浏览阅读818次。学习目的:通过阅读源程序,了解如何使用JAVA的JAIN包来制作SIP客户端程序(IM).学习笔记: Class 说明 InstantMessagingGUI 启动类,负责显示主画面,读如初始化文件,初始化个变_jain-sip notify消息

关于解决多显示器Fliqlo无法正常显示的方法_fliqlo显示感叹号-程序员宅基地

文章浏览阅读5.3k次。关于解决多显示器Fliqlo无法正常显示的方法新版fliqlo在电脑开双屏或笔记本外接显示器时,会出现副屏显示不完整或者外接显示器不显示时钟的情况。我们只需要下载GitHub上大佬的插件就可以解决上述问题。https://github.com/AlynxZhou/flipclock/releases百度网盘地址:https://pan.baidu.com/s/1ioiMVQ-AZPHv6tDFQy0I0Q 提取码:6k7t根据读我的文本文档进行操作即可正常使用fliqlo最后可用屏_fliqlo显示感叹号

(RegionProposal Network)RPN网络结构及详解_rpn结构-程序员宅基地

文章浏览阅读10w+次,点赞113次,收藏720次。RPN(RegionProposal Network)区域生成网络Faster-RCNN的核心。在这里整理。1.anchors。特征可以看做一个尺度51*39的256通道图像,对于该图像的每一个位置,考虑9个可能的候选窗口:三种面积{128,256,512}×{128,256,512}×三种比例{1:1,1:2,2:1}{1:1,1:2,2:1}。这些候选窗口称为anchors..._rpn结构

Nginx1.21.1 安装部署_nginx/1.21.1-程序员宅基地

文章浏览阅读4.6k次。一、前提条件:openssl、pcre已经安装1、查看openssl是否安装openssl version -a2、查看是否安装pcre,安装会显示版本, 没安装什么都不显示rpm -qa pcre二、Nginx安装1、下载nginx安装包[root@localhost nginx]# wget http://nginx.org/download/nginx-1.21.1.tar.gz2、安装部署1)解压[root@localhost nginx]# tar zxvf nginx_nginx/1.21.1

手把手解决visdom可视化出现ConnectionRefusedError: [WinError 10061] 由于目标计算机积极拒绝,无法连接。-程序员宅基地

文章浏览阅读5.1k次,点赞11次,收藏37次。背景:笔者在进行pytorch学习visdom可视化时,第一次运行可视化代码出现如下错误:[WinError 10061] 由于目标计算机积极拒绝,无法连接。在查阅了相关资料后发现可能是vidom激活服务器的问题,解决办法如下。错误详细描述及详细解决过程此处是初始测试代码(引入鸢尾画数据集,对特征点集进行可视化)from visdom import Visdomfrom sklearn.datasets import load_irisiris_x,iris_y=load_iris(ret_connectionrefusederror: [winerror 10061] 由于目标计算机积极拒绝,无法连接。