当前位置:首页 >> IT/计算机 >>

Astar算法详解


A*算法详解 今天刚开通了百度博客,这也是我在这里的第一篇文章,以后会在此写下我学习 AS3 的一些心得和技巧,方便自己日后的复习也让一些新手门能快速的入门,那么, 开门见山,第一 篇就写 AS3 版的 A*算法吧。 那么,我个人习惯不喜欢把简单的东西往复杂了搞,虽然复杂代表着规范,和严谨, 但是处于学习的目的,我给出的 A*算法,相当的简单和实用,当然重点是算法思想,下面就 跟随我的指示太了解 A*算法吧。 那么什么是 A*,其实就是在很多障碍物的地图上,物体从 A 点移动到 B 点的路径, 当然,光要路径也不对,我们要找的就是其中最短的一条,这样问题就来了,如何才能找到 最短的一条呢?首先,我们得有一个标准来验证。我们需要一个探路器和节点,比如我们每 走一步都会用探路器在我们周围的 8 个点上放上节点,然后每个节点会返回出他们的代价,我 们根据探路器的指示,找到代价最少的节点,然后下一步就走到了那里,然后继续上面的操 作,那么,原理是很简单的,我们先需要一个节点类(node),节点类要做的事情就是返回出代 价,至于怎么返回请看下面: 假设我们在地图上每走一步都需要消耗代价,比如直线走一格是 10 代价,斜线走是 14 代价,那么我们可以根据以下的公式计算代价: F=H+G 总代价=目标到当前的直线代价+从开始节点到当前节点的移动代价 那么,其实看到这里我们就只要,需要 3 个函数,F 函数和 H 函数还有 G 函数,那么可以写 成: function F():int{ H()+G(); } 好了,到了这里,A*算法我们已经完成一半了,现在只要去实现 H 和 G 了,那么继续看: public function getH():int { return Math.abs(h - Goal_node.h) * 10 + Math.abs(l - Goal_node.l) * 10; //返回目标到当前的直线代价 } 哇,好少了啊,对,就一行,H 计算的是目标节点到当前节点所消耗的代价,注意了:只需要 计算行和列,斜线的不算,当然不能少了取绝对值,我们不需要负数,之前我们说了直线的代 价是 10,所以我们把他们的代价都*上 10,当然你可以根据自己需求来*上不同的代价,OK,H

搞定了,下面来看看 G: public function getG():int { if (Math.abs(h - Start_node.h) == 1&& Math.abs(l - Start_node.l) == 1) { return 14+Father_int; //返回父节点的带价值和当前节点到开始节点值等于一路走过来的带价值 } else { return Math.abs(h - Start_node.h) * 10 + Math.abs(l - Start_node.l) * 10 + Father_int; //同上 } } //返回从开始节点到当前节点的移动代价 //G 函数比 H 函数多了一点,就是计算斜角的代价,但是,记住,这个斜角只是当前节点的 左上,左下,右上,右下的那一格,那么如何来计算是否是斜角呢?其实只要计算当前行减 去父节点和列减去父节点的列是否都等于 1,这里也一样需要取绝对值,如果都为 1 则说明 不在同一行也不在同一列,Father_int 是什么呢?是父节点的代价,G 函数计算的是当前的代 价还要加上父节点的代价,才能算出开始节点到当前节点的总代价,到了这里 A*逻辑部分已 经完成一大半了,最后我们还需要将找到的路径保存进一个数组里,看下面代码: public function getPath():Array { if (Father_node== this) { var ccc:Array=new Array(); ccc=[[h, l]]; return ccc; } else { var aa:Array = Father_node.getPath(); var answer:Array=aa.slice(0,aa.length); answer[aa.length] =[h, l]; return answer; } } 太少了,对,就是这么简单啦,首先我们检测目标节点的父节点是否等于自己,等于自己说明达 到了起点,因为起点是没有父节点的, 所以我们就设为是自己,好,先就此打住, 看看下面的 else, 这里我们用了递归来寻找节点,首先我们新建立一个数组等于父节点返回的节点,然后在把它 拷贝一份进新的输入,因为 FLASH 的数组是动态的, 所以我们直接在尾部 answer[aa.length] 添 加进当前节点的行和列,最后返回,直到返回到父节点也把自己的坐标返回了,整个递归调用 结束,最后我们需要知道我们是否已经找到目标了,其实我们就可以直接判断当前的节点是否 是目标节点: public function equals(me:Object):Boolean { if (me is node) { if (me.h == h && me.l == l) {

return true; } else { return false; } } else { return false; } } 对啊,就是判断行和列就 OK 啦,这个方法如果返回真了就是找到了,如果返回假就说明没 找到, 自此整个节点核心算法完毕, 下面是整个节点类: package { public class node { public var h:int; public var l:int; public var Father_node:node; public var Goal_node:node; public var Start_node:node; public var Father_int:int; public function node(h:int,l:int,Father_node:node,Goal_node:node,Start_node:node) { this.h=h; //接受行 this.l=l; //接受列 this.Father_node=Father_node; //接受父类节点 this.Goal_node=Goal_node; //接受目标节点 this.Start_node=this.Father_node; //接受开启节点 if (Father_node==null) { this.Father_node=this; } if (Goal_node==null) { this.Goal_node=this; } if (Start_node==null) { this.Start_node=this; }

//如果没有,则等于自己(用于起点和重点) if (Start_node!=null) { Father_int=Start_node.getG(); } //获得父类节点的代价 } public function getH():int { return Math.abs(h - Goal_node.h) * 10 + Math.abs(l - Goal_node.l) * 10; //返回目标到当前的直线代价 } public function getG():int { if (Math.abs(h - Start_node.h) == 1&& Math.abs(l - Start_node.l) == 1) { return 14+Father_int; //返回父节点的带价值和当前节点到开始节点值等于一路走过来的带价值 } else { return Math.abs(h - Start_node.h) * 10 + Math.abs(l - Start_node.l) * 10 + Father_int; //同上 } } //返回从开始节点到当前节点的移动代价 public function getF():int { return getH() + getG(); } public function equals(me:Object):Boolean { if (me is node) { if (me.h == h && me.l == l) { return true; } else { return false; } } else { return false; } } public function getPath():Array { if (Father_node== this) { var ccc:Array=new Array(); ccc=[[h, l]]; return ccc; } else { var aa:Array = Father_node.getPath(); var answer:Array=aa.slice(0,aa.length); answer[aa.length] =[h, l]; return answer;

} } } } 好了,节点我们搞定了,剩下的就是探路器的问题了(Find),那么我们的探路器的工作主要是 负责,摆放节点到各个节点,那么这里我们需要知道什么位置需要放什么位置不需要,比如 放过节点的位置当然就不需要了,呵呵,然后探路器会分析哪个节点返回的代价最少,最后当 探路器找到目标之后会把整个路径返回出去,那么说到这里了,我们不得不说下列表问题,探 路器是通过列表来选择是否放置节点,一共有 2 个,开启列表和关闭列表,首先,我们得知道, 被 放置的节点是否在某个列表里,如下函数: public function detection_listing(h:int,l:int,vec:Array):node { for (var i:int=0; i < vec.length; i++) { var mc:node=vec[i]; if (h == mc.h && l == mc.l) { return mc; } } return null; } //检测是否在列表里(检测当前行当前列是否与开启列表里的元素一样) 现在我们只要把列表(数组)丢进去再丢行和列就好了,再下来, 我们需要知道斜角的地方是否 有障碍物,如下函数: public function bianyuan(h:int,l:int,hh:int,ll:int,map:Array):Boolean { if (hh-1==h&&ll-1==l) { if (map[h][l+1]==1||map[h+1][l]==1) { //trace("左上") return false; } } else if (hh-1==h&&ll+1==l) { if (map[h][l-1]==1||map[h+1][l]==1) { //trace("右上") return false; } } else if (hh+1==h&&ll-1==l) { if (map[h-1][l]==1||map[h][l+1]==1) { //trace("左下") return false; } } else if (hh+1==h&&ll+1==l) { if (map[h][l-1]==1||map[h-1][l]==1) {

//trace("右下") return false; } } return true //判断当前节点的斜角上周围是否有障碍物 } 我们需要丢一个行和列进去,然后再丢另一组行和列进去,然后是地图,判断第一组的行和列 在第二组的行和列的什么位置,最后再判断是否有障碍物. if (map[h][l-1]==1||map[h-1][l]==1) , 这里我设置障碍物是 1,再后来,我们需要知道是否找不到路: if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){ trace("没有路了") kaishi=false } 嗯,开启列表已经没有东西了,但是路径返回返回假,就说明寻路失败,我这里设置了一个 布尔值为假:好了,辅助函数都写好了,关键时刻到了,现在我们需要使用探路,探测身边周围 的 8 个点,方法如下: for (var j:int=-1; j<2; j++) { for (var k:int=-1; k<2; k++) { } } 对,2 个 for 循环,看看,当前节点的行加上 J,和当前节点的列加上 K,是否就是当前节点周 围的 8 个点,好了,下面是上面的函数的完整应用: public function aido(map:Array) { if (shanchu.length!=0) { for (var t:int=0; t<shanchu.length; t++) { shanchu[t]=null; trace("删除了") } } //如果删除列表不为空,则删除里面所有元素,等待系统回收 shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array;

//关闭列表 Start_listing.push(Start_node); //把当前节点放入开启列表 shanchu.push(Start_node); //把当前节点放入删除列表 do { Current_node=Start_listing[0]; //获取开启列表的第一个元素 for (var i:int=1; i<Start_listing.length; i++) { if (Start_listing[i].getF()<Current_node.getF()) { Current_node=Start_listing[i]; } } //比较数组里的元素,如果数组里的元素的 F 值比当前的小,则把当前的替换成数组 里的 if (Current_node.equals(Goal_node)) { //trace("找到路了"); fruit=Current_node.getPath(); kaishi=true break } //是否找到路径 Stop_listing.push(Current_node); //添加当前节点到关闭列表 Start_listing.splice(Start_listing.indexOf(Current_node),1); //删除开始列表把当前节点从 for (var j:int=-1; j<2; j++) { for (var k:int=-1; k<2; k++) { //遍历当前节点周围的位置 if (Current_node.h+j==0&&Current_node.l+k==0) { continue; } if (Current_node.h+j>=map.length||Current_node.h-j<0) { continue; } if (Current_node.l+k>=map[0].length||Current_node.l-k<0) { continue; } //判断是否遍历到了自己,是否超出了边界,如果是,则返回出去,重新遍历 if (bianyuan(Current_node.h+j,Current_node.l+k,Current_node.h,Current_node.l,map)&&detection _fraise(Current_node.h+j,Current_node.l+k,map)&&detection_border(Current_node.h+j,Current _node.l+k,map)&&detection_listing(Current_node.h+j,Current_node.l+k,Stop_listing)==null) { //如果周边的节点不在关闭列表里,是不是障碍物,斜角的周边是否有障碍物

About_node=detection_listing(Current_node.h+j,Current_node.l+k,Start_listing); //判断周边的节点,传递行,列,开启列表 //如果当前对象在开启列表里,则函数会返回空,如果不在,则会创建新的节点 if (About_node==null) { //如果为空则不用多说了,像病毒一样扩散开来 About_node=new node(Current_node.h+j,Current_node.l+k,Current_node,Goal_node,Current_node); //初始化节点,传递行,列,父节点(当前的节点),目标节点(上面当鼠标点击时 6 了 一个),开始节点(游戏运行时 6 了一个) Start_listing.push(About_node); shanchu.push(About_node); //如果周边的节点为空,则在周边扩散节点,将扩散的节点放入开启列表, 以备下次 检测需要,也放入删除列表,待找到路径后删除删除列表里所有的节点,等待系统回收 } else { var oldG:int=About_node.getG(); //保存零时变量为开启列表里的 G 值 var Father:node=About_node.Father_node; //保存开启列表里的父节点 About_node.Father_node=Current_node; //替换开启列表里的父节点为当前节点 if (About_node.getG() >= oldG) { //trace("被替换了") //比较被替换父节点的开启列表里的节点的值是否大于最开始的 G 值 About_node.Father_node=Father; //如果大于则,被替换的开启列表里的节点的父节点又被送了回来给与了开启列 表里的节点 } //如果周边节点移动的代价比当前节点移动的代价要少的话,就替换当前节点的父 节点,递归路径时遍会递归到最短路径的父类 } } } } } while (Start_listing.length!=0); //如果开启列表为空,停止寻路 if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){ trace("没有路了") kaishi=false } } 首先,我们定义了一个寻路函数,只接收地图,然后我们初始化了开启列表和关闭列表,最后将 当前节点放入开启列表和关闭列表,其实我们就是把起点放进去,仔细看,这个动作是在 for 循环外面,既然是寻路,所以我们要有个开头,对吧,最后我们用 do...while()

循环来执行核心部分,在开始部分,我们先来了一次冒泡排序,就是找出开启列表里代价最小 的节点,然后让零时节点等于这个节点,然后再比较,这个节点是否是目标节点,如果是,则 找到路径,返回路径,如果不是,继续,只要是检测过的节点,都不需要再检测,所以我们把 当前节点放入关闭列表,同时也在开启列表里删除当前节点,最后,我们通过 for 循环,检测当 前节点周围的 8 个点,判断如果超出了边界则放弃掉,进行下一次循环,然后再判断当前节点 是否不在关闭列表里,旁边是否有障碍物,自己本上是否是障碍物,如果都没有, 则检测是否在 开启列表里,如果也不在开启列表里,则放置节点到当前的点上,把当前的点放入开启列表, 等待下一次的循环检测,如果在开启列表里, 则检测开启列表里的 G 指是否小于当前的 G 值, 如果小于,则替换父节点,因为递归寻路是通过父节点的坐标,我们需要保证我们找到的路径 是最短的,如果开启列表不为空,则继续循环,好,至此整个探路器核心介绍完毕,下面是完 整代码: package { public class Find { private var h:int; private var l:int; private var fruit:Array; //路径数组 private var Start_listing:Array; //开启列表 private var Stop_listing:Array; //关闭列表 public var Goal_node:node; //目标节点 public var Start_node:node; //开始节点 public var Current_node:node; //当前节点 public var Fairly_node:node; //比较节点 public var About_node:node; //零时节点 private var shanchu:Array; static public var kaishi:Boolean public function AIdo(h:int,l:int,hh:int,ll:int,map:Array):Array { shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array; //关闭列表 Goal_node=new node(hh,ll,null,null,null); //目标节点

Start_node=new node(h,l,null,Goal_node,null); //开始节点 aido(map); //开始寻路 return fruit; //返回寻路后的结果数组 } public function aido(map:Array) { if (shanchu.length!=0) { for (var t:int=0; t<shanchu.length; t++) { shanchu[t]=null; trace("删除了") } } //如果删除列表不为空,则删除里面所有元素,等待系统回收 shanchu=new Array(); //初始化删除列表 Start_listing=new Array; //开启列表 Stop_listing=new Array; //关闭列表 Start_listing.push(Start_node); //把当前节点放入开启列表 shanchu.push(Start_node); //把当前节点放入删除列表 do { Current_node=Start_listing[0]; //获取开启列表的第一个元素 for (var i:int=1; i<Start_listing.length; i++) { if (Start_listing[i].getF()<Current_node.getF()) { Current_node=Start_listing[i]; } } //比较数组里的元素,如果数组里的元素的 F 值比当前的小,则把当前的替换成数组 里的 if (Current_node.equals(Goal_node)) { //trace("找到路了"); fruit=Current_node.getPath(); kaishi=true break } //是否找到路径 Stop_listing.push(Current_node); //添加当前节点到关闭列表

Start_listing.splice(Start_listing.indexOf(Current_node),1); //删除开始列表把当前节点从 for (var j:int=-1; j<2; j++) { for (var k:int=-1; k<2; k++) { //遍历当前节点周围的位置 if (Current_node.h+j==0&&Current_node.l+k==0) { continue; } if (Current_node.h+j>=map.length||Current_node.h-j<0) { continue; } if (Current_node.l+k>=map[0].length||Current_node.l-k<0) { continue; } //判断是否遍历到了自己,是否超出了边界,如果是,则返回出去,重新遍历 if (bianyuan(Current_node.h+j,Current_node.l+k,Current_node.h,Current_node.l,map)&&detection _fraise(Current_node.h+j,Current_node.l+k,map)&&detection_border(Current_node.h+j,Current _node.l+k,map)&&detection_listing(Current_node.h+j,Current_node.l+k,Stop_listing)==null) { //如果周边的节点不在关闭列表里,是不是障碍物,斜角的周边是否有障碍物 About_node=detection_listing(Current_node.h+j,Current_node.l+k,Start_listing); //判断周边的节点,传递行,列,开启列表 //如果当前对象在开启列表里,则函数会返回空,如果不在,则会创建新的节点 if (About_node==null) { //如果为空则不用多说了,像病毒一样扩散开来 About_node=new node(Current_node.h+j,Current_node.l+k,Current_node,Goal_node,Current_node); //初始化节点,传递行,列,父节点(当前的节点),目标节点(上面当鼠标点击时 6 了 一个),开始节点(游戏运行时 6 了一个) Start_listing.push(About_node); shanchu.push(About_node); //如果周边的节点为空,则在周边扩散节点,将扩散的节点放入开启列表, 以备下次 检测需要,也放入删除列表,待找到路径后删除删除列表里所有的节点,等待系统回收 } else { var oldG:int=About_node.getG(); //保存零时变量为开启列表里的 G 值 var Father:node=About_node.Father_node; //保存开启列表里的父节点 About_node.Father_node=Current_node; //替换开启列表里的父节点为当前节点 if (About_node.getG() >= oldG) { //trace("被替换了") //比较被替换父节点的开启列表里的节点的值是否大于最开始的 G 值 About_node.Father_node=Father;

//如果大于则,被替换的开启列表里的节点的父节点又被送了回来给与了开启列 表里的节点 } //如果周边节点移动的代价比当前节点移动的代价要少的话,就替换当前节点的父 节点,递归路径时遍会递归到最短路径的父类 } } } } } while (Start_listing.length!=0); //如果开启列表为空,停止寻路 if(Start_listing.length==0&&Current_node.equals(Goal_node)==false){ trace("没有路了") kaishi=false } } public function bianyuan(h:int,l:int,hh:int,ll:int,map:Array):Boolean { if (hh-1==h&&ll-1==l) { if (map[h][l+1]==1||map[h+1][l]==1) { //trace("左上") return false; } } else if (hh-1==h&&ll+1==l) { if (map[h][l-1]==1||map[h+1][l]==1) { //trace("右上") return false; } } else if (hh+1==h&&ll-1==l) { if (map[h-1][l]==1||map[h][l+1]==1) { //trace("左下") return false; } } else if (hh+1==h&&ll+1==l) { if (map[h][l-1]==1||map[h-1][l]==1) { //trace("右下") return false; } } return true //判断当前节点的斜角上周围是否有障碍物 } public function detection_fraise(h:int,l:int,map:Array):Boolean { if (map[h][l]==1) { return false;

} else { return true; } } //检测是否有障碍物 public function detection_border(h:int,l:int,map:Array):Boolean { return h < map.length && l < map[0].length && h >= 0 && l >= 0; } //检测是否超出边界 public function detection_listing(h:int,l:int,vec:Array):node { for (var i:int=0; i < vec.length; i++) { var mc:node=vec[i]; if (h == mc.h && l == mc.l) { return mc; } } return null; } //检测是否在列表里(检测当前行当前列是否与开启列表里的元素一样) } } 用法很简单,这是一个静态的方法,Find.AIdo(起点行,起点列,终点行,终点列,地图)以后只要用 A*,找到这个 2 个类文件,调用这个方法就会返回一个 2 维数组,其中第 2 维的 0 代表行, 1 代表列。


赞助商链接
相关文章:
Astar(A星)算法实现详解及代码下载
Astar(A星)算法实现详解及代码下载_计算机软件及应用_IT/计算机_专业资料。文章中介绍了详细的A*算法的实现,贴出了博客地址, 在博客中有完整的代码下载,及演示软...
Astar算法
Astar算法_IT/计算机_专业资料。A*算法Harbin Institute of Technology 研究生课程...A算法详解 17页 免费 A路径寻找算法入门 11页 免费 Astar经典算法 14页 免费...
astar(a星)算法
A*算法原理简介 A*(A-Star)算法是一种静态路网中求解最短路最有 A star ...Astar算法详解 13页 1下载券 Astar经典算法 14页 免费 Astar算法简介 10页 3...
Astar算法与深度优先算法解决走迷宫问题
Astar算法与深度优先算法解决走迷宫问题_计算机软件及应用_IT/计算机_专业资料。#...可走方块 { //将其它两处的 di++改为这里的一处 di++将导致算法错误,...
A星算法matlab源码及详细注释
A星算法matlab源码及详细注释_信息与通信_工程科技_专业资料。A星算法matlab源码及详细注释 A 星算法 matlab 源码及详细注释 function astardemo %ASTARDEMO ...
算法分析与设计
科学出版社 六、附录代码头文件: Astar.h //*** //代码目的:用 A*算法解决旅行商问题 // //估价函数: f=g+h 其中 g 为该节点走过的路程,h 为未走过...
A星算法
喜欢此文档的还喜欢 astar(a星)算法 17页 免费 A星算法 21页 免费 A星算法 13页 1下载券 A算法详解 17页 免费 A路径寻找算法入门 11页 免费...
A星详解
A 算法详解 第一部分:A*算法简介 写这篇文章的初衷是应一个网友的要求,当然...^_* 注意下面所说的都是以 ClassAstar 这个程序为蓝本,你可以在这 里下载...
Astart算法
Astart算法_理学_高等教育_教育专区。A*算法初识A*算法 写这篇文章的初衷是应...astar(a星)算法 17页 免费 A算法详解 17页 免费 Astar经典算法 14页 免费 ...
A算法
aStarTutorial.htm 以下是翻译的正文 会者不难,A*(念作 A 星)算法对初学者...A算法 44页 1下载券 A算法详解 17页 免费 A算法 15页 1下载券©...
更多相关标签: