A*寻路,二叉堆优化及AS3实现 - 多媒体制作 - 蓝色理想
您的位置：　 &
& A*寻路,二叉堆优化及AS3实现
　A*寻路,二叉堆优化及AS3实现
作者：　时间： 　文档类型：原创　来自：
第 2 页 牛刀小试 - A*寻路算法简介 第 3 页
eidiot挂帅出征，携令牌一枚，率人马若干，编制如下：
* 寻路元帅&&寻路总指挥，执“行动令牌”一枚和“开启士兵名录”、“关闭将军名录”各一册。凭“行动令牌”调兵遣将。* 预备士兵&&由元帅或预备将军派往未探索区域，完成探索任务后授“开启”军衔，晋为“开启士兵”。发令派其出者为其“父将”。* 开启士兵前线待命。接到“行动令牌”后晋为“预备将军”执行探索任务。* 预备将军凭“行动令牌”派出预备士兵至周围未探索区域，并考察周围“开启士兵”状态，以“父将”之名节制所派士兵。归还“行动令牌”后授“关闭”军衔，晋为“关闭将军”。* 关闭将军后方待命。到达终点后依次报告“父将”直至元帅，寻路任务完成。
为协调行动，特颁军令如下：
* “预备士兵”只能由起点或“父将”所在格横、竖或斜向移动一格，直向（横、竖）移动一格走10步，斜向一格14步（斜向是直向1.414倍，取整数），抵达后不得再移动。* 所有人员需记下派出自己的“父将”、从起点到所在位置所走步数（G）、预计到达终点共需步数（F）。其中 F = G + H ，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。G 的计算是“父将”的 G 值加上“父将”位置到该位置所走步数，H 的计算是该点到终点“只走直路”所需路程。
看看战图更容易理解，从红色方格出发越过黄色障碍到达蓝色方格：
screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {} else {window.open('http://eidiot.net/wp-content/uploads/.gif');}" alt="" src="/articleimg/5/0.gif" onload="if(this.width>screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" border=0>
screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {} else {window.open('http://eidiot.net/wp-content/uploads/.gif');}" alt="" src="/articleimg/5/00.gif" onload="if(this.width>screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" border=0>
由图可形象看出何谓“开启士兵”、“关闭将军”：外围的绿色方格为“开启士兵”，“前线待命”，随时可向外继续探索。内围的紫色方格是“关闭将军”，从终点开始沿箭头寻其“父将”直至起点即得最终路径。
战前会议结束，拔营出征。
* 首先派出编号为0的“预备士兵”侦查起点，然后升其为“开启士兵”，列入“开启士兵名录”。* 检查“开启士兵名录”，找出F值最低的“开启士兵”（只有一名人员，当然是0号），发出“行动令牌”派其执行探索任务。* 0号“开启士兵”接到“行动令牌”，晋为“预备将军”，探索周围格子。* 向周围8个格子分别派出编号为1到8的“预备士兵”，成为这八名“预备士兵”的“父将”。* 八名“预备士兵”到达方格后计算G值和F值，报告0号“父将”，晋为“开启士兵”。* 0号“预备将军”收到八名“开启士兵”的报告，归还“行动令牌”，晋为“关闭将军”。* 元帅收回“行动令牌”，将0号加入“关闭将军名录”，1到8号加入“开启士兵名录”。
此过程结果如下（方格右上角数字是人员编号，左下角是G，右下角是H，左上角是F）：
screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {} else {window.open('http://eidiot.net/wp-content/uploads/.gif');}" alt="" src="/articleimg/5/1.gif" onload="if(this.width>screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" border=0>
第一轮探索任务完成，元帅开始检查“开启士兵名录”。此时名录中有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号加入“关闭将军名录”。
此过程结果如下：
screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {} else {window.open('http://eidiot.net/wp-content/uploads/.gif');}" alt="" src="/articleimg/5/2.gif" onload="if(this.width>screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" border=0>
第二轮结束，元帅再次检查“开启士兵名录”。此时还有7名“开启士兵”，5号和8号的F值都为最低的54，选择不同寻路的结果也将不同。元帅选择了最后加入的8号“开启士兵”发出“行动令牌”，过程同上，不赘述，结果如下：
screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {} else {window.open('http://eidiot.net/wp-content/uploads/.gif');}" alt="" src="/articleimg/5/3.gif" onload="if(this.width>screen.width*0.7) {this.resized= this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL+Mouse wheel to zoom in/out';}" border=0>
重复这个过程直到某位“关闭将军”站到了终点上（或者“开启士兵”探测到了终点，这样更快捷，但某些情况找到的路径不够短），亦即找到了路径；或是“开启士兵名录”已空，无法到达终点。
下面整理一下全过程并翻译成“标准语言”，首先是各名词：* “开启士兵名录” - 开启列表 - 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代码和示例。
经典论坛讨论:
责任编辑：
◎进入论坛版块参加讨论
页次：2/4页
1个记录/页
1
2
3
4
页
蓝色理想版权申明：除部分特别声明不要转载，或者授权我站独家播发的文章外，大家可以自由转载我站点的原创文章，但原作者和来自我站的链接必须保留（非我站原创的，按照原来自一节，自行链接）。文章版权归我站和作者共有。
转载要求：转载之图片、文件，链接请不要盗链到本站，且不准打上各自站点的水印，亦不能抹去我站点水印。
特别注意：本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有，文章若有侵犯作者版权，请与我们，我们将立即删除修改。
说明：输入正确的用户名和密码才能参与评论。如果您不是本站会员，你可以 为本站会员。
注意：文章中的链接、内容等需要修改的错误，请用，以利文档及时修改。
注意：请不要在评论中含与内容无关的广告链接，违者封ID
请您注意：?不良评论请用，以利管理员及时删除。?尊重网上道德，遵守中华人民共和国的各项有关法律法规?承担一切因您的行为而直接或间接导致的民事或刑事法律责任?本站评论管理人员有权保留或删除其管辖评论中的任意内容
?您在本站发表的作品，本站有权在网站内转载或引用 ?参与本评论即表明您已经阅读并接受上述条款
专业书推荐
&1999-. 版权所有2586人阅读
在地图中，通过鼠标或者由程序自动运行，让一个人物自动从地图的一点走到另一点。需要计算两点之间的最优路线要实现这样的寻路算法。最常规和最简单的方法，使用算法。本篇总结不具体讲解算法的实现以及原理，主要告诉怎么用。后面的总结中我会陆续把算法进行详细分析，希望大家学习。
2.1.&地图加载
1)在寻路过程中，地图是被分为若干个小格子，当然，根据格子数量的不同，路线长度的不同，计算寻路的时间也就不同。
上面是有一个由20*20的地图拼起来的地图，每一个地图块是有20像素*20像素元件做成。
每一个地图块是2帧构成，地图帧是人物可以行走的路线，第二帧是障碍物（桌子）。上面的地图是路线和障碍物8比2的概率生成，参考代码：
Block&是地图块元件类。用Flash&cs3&已经做好。
this.mass_x_count&是指地图X轴上板块数量
this.mass_y_count&是指地图Y轴上板块数量
distancex&是指地图X轴离边界Left的距离
distancey&是指地图Y轴离边界Top的距离
aNodeMap&是一个2维数组，记录着每一个地图块当前的状态，是障碍物还是路线。
地图初始化中，根据两个For循环嵌套，生成一个表格状的地图。这里我不在详细介绍，详细会AS3的一定可以看的懂。
2.2.&地图上移动人物加载
1）路线寻路肯定要有一个元件在地图上移动，才可以正确的显示出寻路的过程。无论是一个人物移动或多个人物移动，基本做法相同，下面我们就来加载一个人物物件到地图上来。
Waiter&是一个移动的任务元件。在这里我们叫&服务员元件&
Timer&是为服务员增加一个事件，主要目的是为了服务员从一个地图块移动到另一个地图块，不是跳过去的，而是慢慢的移动过去的。
此方法主要在加载完地图后调用，指定人物加载的，坐标，进行加载。
2.3.&选择移动目的地
1）地图和服务员加载完成后，我们需要选择服务员移动的目的地，选择的方式有很多。举个例子，人人餐厅中客人进来就餐，首先进门后，程序会自动寻找有空位的坐标，然后计算路线，客人就会沿着路线走进去。同样服务员也会根据客人进来餐厅的循序，以及客人所做的座椅的坐标进行计算路线，然后走过去服务。
2）由于我们只是一个例子，所以就有我们鼠标确定目的地。
this.addEventListener(MouseEvent.CLICK,clickWay);
这个事件通过，用户鼠标点击地图上路线进行调用。
2.4.&路线寻找，人物移动
1）在地图增加完后我们增加一个算法实例
AStar是算法的一个封装类。我们需要把我们地图上路线和障碍物二维数组传递给算法。
这个是在地图加载后完成
2）确定移动目的地后计算路线
上面代码是在选择目的地后补充的代码
设置A*（）算法的其实点和目的地。起始点和目的地封装成对象给算法的。
ANode&是一个算法计算中节点的保存，记录着节点的位置，，节点，以及使用计算&&F、、值的保存。从而做为路线计算中开启列表进行存储。
最后会调用判断路线的获取是否成功。获取的路线调用方法进行获取。
启动进行服务员移动操作。
3）服务员移动
&&&&&在移动服务之前，我们确定，我们寻找到路线，此服务员的上一个路线已经完成。
代码如下：
这个方法是在寻找到路线后，timer启动执行的。表示是否移动服务员。
player&代表当前移动中的服务员对象，他是在创建服务员的时候保存在全局变量中。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：14138次
排名：千里之外
(4)(1)(1)(1)(2)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'相关文章：&&&&&&
最新添加资讯
24小时热门资讯
附近好友搜索当前位置：
> &天地培训-FlashAS3游戏开发培训进阶班
天地培训-FlashAS3游戏开发培训进阶班
课程价格：电询
上课班制：随到随学
课程类型：普通课程
授课时间：电话咨询
授课对象：游戏程序爱好者
返现信息：2%学费
关 键 词：Flashas3培训 Flash程序培训 AS3游戏培训
温馨提示:只有在此网站报名，才获得DOGAME返学网提供的返现学费
我从DOGAME返学网-学习省钱从这里开始！上看到该课程的电话，我想问...
加入时间：日
认证情况：
1、面向对象编程
这部分课程是编程从入门到精通的关键阶段。面向对象是近十几年来最流行，最被认可的，最适合人类思考模式的一种编程方式。它把程序的表达地更接近人类的思维，而不是一味的去执行枯燥的计算机原理。面向对象使得多人协同开发变得容易，也使得程序的可维护性和可扩展性大大提升。主要内容：类和对象封装、继承和多态面向对象案例实践&
2、AS3显示列表机制
AS3的显示列表机制可以说是Flash的发家之本。本阶段我们只要学习如何使用AS3来生成和控制各种文本、图片、动画、视频等可视元素。并且我们可以添加各种复杂效果（如滤镜、遮罩和修改颜色通道等）。主要内容：可视对象和可视对象容器矢量图和位图文本、影片剪辑和按钮
3、AS3事件流机制
AS3的事件流机制是Flash的一大特色。通过事件流的三个阶段：捕获阶段、目标阶段和冒泡阶段。我们可以很方便地接收事件，并且对事件做出相应的处理。本阶段我们主要学习事件流机制工作的原理以及如何自定义事件。主要内容：鼠标事件、键盘事件、时间事件事件流机制自定义事件&
4、AS3网络通信
稍复杂的AS3应用程序，一般都会涉及到加载外部数据或者与服务器脚本相互通信。AS3对网络通信的支持空前强大，目前主流的网络数据交互方式几乎全部支持。主要内容：URLLoader加载数据与检测加载进度认识XMLSocket通信与SharedObject本地存储。&
5、框架应用
6、游戏项目实战
还在自己写各种物理算法？还在自己纠结底层的渲染效果？这一切的努力都过时了。别再想怎么让自己的自行车安装电池电机，别再想怎么给自行车安装雨棚了，买辆高级摩托车就什么都解决了。假舆马者，非利足也，而致千里；假舟楫者，非能水也，而绝江河。有成熟的稳定的何不拿来尝试一下？学习一下呢？主要内容：TweenerStarlingBox2D其他框架
这部分课程主要讲解游戏关注遇到的核心问题。如何进行精确的碰撞检测、如何实现地图卷轴系统、如何把玩家数据存储至服务器、如何实现怪物AI、如果编写寻路算法、如何优化Flash程序等等。
主要内容：碰撞检测寻路算法地图卷轴系统对象池等优化技术
性别：男 女
温馨提示:只有在此网站报名，才获得DOGAME返学网提供的返现学费
手机号码： *
固定电话：
联系地址：
微信二维码
加返学网为好友
var ad_divs = $obj('ad_none').getElementsByTagName('div');
var ad_obj =
for(var i = 0; i < ad_divs. i++) {
if(ad_divs[i].id.substr(0, 3) == 'ad_' && (ad_obj = $obj(ad_divs[i].id.substr(0, ad_divs[i].id.length - 5))) && ad_divs[i].innerHTML) {
ad_obj.innerHTML = ad_divs[i].innerHTML;
ad_obj.className = ad_divs[i].classN