[原创] as3 做的 A*寻路

原创首发www.eb163.com，转载请保留出处　作者：iiacm （着火骷髅）
　　Ａ*算法的思想很丰富，游戏中用来解决人物角色、敌人的寻路问题是相当不错的方法。以前玩帝国时代的时候，看到里面的士兵跑路的路径都是择优而行，感到很奇妙，后来才知道，那是A*算法的功劳。随着逐渐的学习，对这个算法更是无比的倾慕，一度听到这个名词，心中一股钦佩之情油然而生…… 于是一直都在寻找学习的方法，不断的看帖、搜索，终于，在jr高手发布的帖子（http://www.eb163.com/club/viewthread.php?tid=2458&highlight=%D1%B0%C2%B7）和超哥的启发下，写出了自己的A*例子，感谢他们给予的帮助，拿出来和大家一起分享一下。
　　演示地址：http://www.eb163.com/club/thread-11209-1-1.html

一、demo的结构
　　demo分为三个部分：MainClass文档类——构建一个二维地图，并调用A*寻路类寻路；AStar A*寻路算法类——提供了所有寻路时用到的方法函数；AStarGrid 节点数据类——为寻路过程提供中间的数据结构，引入这个类的对象可以剥离地图单元，寻路时操作节点数据对象替代直接操作地图单元，方便管理。具体代码：

package{
        /*
        iiacm(着火骷髅)，网页游戏开发网 www.eb163.com 
        网页游戏互动社区
        
        A*寻路算法启发性搜索 demo 文档类
        */
        import flash.display.Sprite;
        import flash.events.MouseEvent;
        import flash.geom.Point;
        public class MainClass extends Sprite{
                //设定地图单元行数
                protected var rowNum:uint=22;
                //设定地图单元列数
                protected var columnNum:uint=20;
                //设定地图单元宽度
                protected var mcWidth:uint=25;
                //设定地图单元高度
                protected var mcHeight:uint=20;
                //存储地图单元数据的数组
                protected var mcArr:Array=new Array();
                //声明一个A*寻路类的实例对象，把地图单元数据作为参数传入类的构造函数
                protected var aStar:AStar=new AStar(mcArr);
                //当前起点
                protected var nowPoint:Point=new Point(5,5);
                //当前终点
                protected var endPoint:Point;
                public function MainClass(){
                        init();
                }
                //初始化，创建地图
                protected function init(){
                        createMcs();
                }
                //根据行数列数创建地图，同时填充地图数据
                protected function createMcs(){
                        for(var i:int=0; i<columnNum; i++){
                                mcArr[i]=new Array();
                                for(var j:int=0; j<rowNum; j++){
                                        var sprite:Sprite=drawRect();
                                        sprite.x=j*mcWidth;
                                        sprite.y=i*mcHeight;
                                        sprite.name="mc_"+i+"_"+j;
                                        mcArr[i].push(sprite);
                                        addChild(sprite);
                                        sprite.addEventListener(MouseEvent.CLICK, onClickSpriteHandler);
                                }
                        }
                }
                //为地图单元添加的鼠标点击事件处理函数，由起点到被点击地图单元的位置进行寻路，改变alpha属性对找到的路径标记
                protected function onClickSpriteHandler(e:MouseEvent){
                        for(var i=0;i<mcArr.length;i++){
                                for(var j=0;j<mcArr[i].length;j++){
                                        mcArr[i][j].alpha=1;
                                }
                        }
                        endPoint=checkMapPos(e.currentTarget as Sprite);
                        aStar.findPath(nowPoint, endPoint);
                        nowPoint=endPoint;
                }
                //查找当前点击的地图单元，返回单元所在坐标
                protected function checkMapPos(mapGrid:Sprite):Point{
                        var point:Point;
                        for(var i=0;i<mcArr.length;i++){
                                for(var j=0;j<mcArr[i].length;j++){
                                        if(mapGrid.name==mcArr[i][j].name){
                                                point=new Point(i,j);
                                                break;
                                        }
                                }
                        }
                        return point;
                }
                //绘制地图单元
                protected function drawRect():Sprite{
                        var sprite:Sprite=new Sprite();
                        sprite.graphics.lineStyle(.25, 0x232323, 1);
                        sprite.graphics.beginFill(0xffffff, 0.5);
                        sprite.graphics.drawRect(0, 0, mcWidth, mcHeight);
                        sprite.graphics.endFill();
                        return sprite;
                }
        }
}

package{
        /*
        iiacm(着火骷髅)，网页游戏开发网 www.eb163.com 
        网页游戏互动社区
        
        A*寻路类
                使用A*算法实现自动寻找最佳路径功能
        */
        import flash.geom.Point;
        import flash.display.DisplayObject;
        public class AStar{
                //封闭列表
                protected var _closeList:Array=new Array();
                //开放列表
                protected var _openList:Array=new Array();
                //地图节点数据
                protected var _mapData:Array;
                //存储寻路结果的数组
                protected var way:Array=new Array();
                //起点节点
                protected var _startNode:AStarGrid;
                //目标节点
                protected var _targetNode:AStarGrid;
                //当前操作节点
                protected var _nowNode:AStarGrid;
                //是否找到路径，起始值false，完成寻路后为true
                protected var _isFind:Boolean=false;
                //从起点起点沿着已生成的路径到给定节点的移动开销，直线方向为g=10，斜线方向为obliqueG=14
                public var g:Number=10;
                public var obliqueG:Number=14;
                //从给定节点到目标节点的估计移动开销
                public var h:Number=10;
                //允许寻找的方向，值为8时表示可以从8个方向寻找路线，即允许斜线行走
                //public var direct:int=8;
                //构造函数，需要一个存储有地图节点数据的数组做参数
                public function AStar(mapData:Array){
                        _mapData=mapData;
                }
                //启动寻路
                public function findPath(startPos:Point, targetPos:Point):Array{
                        //设置起点、终点
                        _startNode=new AStarGrid(startPos.x, startPos.y, _mapData[startPos.x][startPos.y]);
                        _targetNode=new AStarGrid(targetPos.x, targetPos.y, _mapData[targetPos.x][targetPos.y]);
                        //在地图上标记出起点和终点
                        _startNode.mc.alpha=0;
                        _targetNode.mc.alpha=0;
                        //标记，设置起点为当前操作节点
                        _nowNode=_startNode;
                        //设置起始节点的父节点为null
                        setFather(_startNode, null);
                        //重置寻路结果
                        way=new Array();
                        //计算起始节点的g, h, f值
                        countHG(_startNode);
                        //将起始节点加入开放列表及封闭列表
                        addToOpen(_startNode);
                        addToClose(_startNode);
                        //获取起始节点周围节点
                        way=getAround(_startNode);
                        //-----------------------
                        return way;
                }
                //获取当前操作节点周围的节点，通过递归调用执行寻路过程
                protected function getAround(centreNode:AStarGrid):Array{
                        //声明两个数组，分别存放当前操作节点周围的节点数据及对应的地图单元
                        var aroundArr:Array=new Array();
                        var aroundNodeArr:Array=new Array();
                        //将当前操作节点周围的非空节点、地图单元分别加入aroundNodeArr和aroundArr数组，
                        if(centreNode.dC+1<_mapData[0].length){
                                aroundArr.push(_mapData[centreNode.dR][centreNode.dC+1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR, centreNode.dC+1, aroundArr[0]));
                        }
                        if(centreNode.dC-1>=0){
                                aroundArr.push(_mapData[centreNode.dR][centreNode.dC-1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR, centreNode.dC-1, aroundArr[1]));
                        }
                        if(centreNode.dR+1<_mapData.length){
                                aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC, aroundArr[2]));
                        }
                        if(centreNode.dR-1>=0){
                                aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC, aroundArr[3]));
                        }
                        if(centreNode.dR-1>=0 && centreNode.dC-1>=0){
                                aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC-1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC-1, aroundArr[4]));
                        }
                        if(centreNode.dR+1<_mapData.length && centreNode.dC+1<_mapData[0].length){
                                aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC+1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC+1, aroundArr[5]));
                        }
                        if(centreNode.dR-1>=0 && centreNode.dC+1<_mapData[0].length){
                                aroundArr.push(_mapData[centreNode.dR-1][centreNode.dC+1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR-1, centreNode.dC+1, aroundArr[6]));
                        }
                        if(centreNode.dR+1<_mapData.length && centreNode.dC-1>=0){
                                aroundArr.push(_mapData[centreNode.dR+1][centreNode.dC-1]);
                                aroundNodeArr.push(dataToGrid(centreNode.dR+1, centreNode.dC-1, aroundArr[7]));
                        }
                        //声明一个AStarGrid对象，存储在 aroundNodeArr 数组中具有f值最大的节点 
                        var fMaxGrid:AStarGrid;
                        //遍历 aroundNodeArr 数组，把数组中所有节点的父节点设为当前操作节点，计算他们的g, h, f值，并全部执行加入开放列表操作
                        for(var n:int=0; n<aroundArr.length; n++){
                                setFather(aroundNodeArr[n], centreNode);
                                countHG(aroundNodeArr[n]);
                                addToOpen(aroundNodeArr[n]);
                        }
                        //找出 aroundNodeArr 数组中具有f值最大的节点，存入 fMaxGrid 变量
                        for(var i:int=1; i<aroundNodeArr.length; i++){
                                for(var m:int=aroundNodeArr.length-1; m>=i; m--){
                                        if(aroundNodeArr[m].f<aroundNodeArr[m-1].f){
                                                var sNode:AStarGrid=aroundNodeArr[m-1];
                                                aroundNodeArr[m-1]=aroundNodeArr[m];
                                                aroundNodeArr[m]=sNode;
                                        }
                                }
                        }
                        //设置当前操作节点为 f 值最大的节点，并将其加入封闭列表
                        _nowNode=aroundNodeArr[0];
                        addToClose(aroundNodeArr[0]);
                        //判断 _isFind 的值确认是否完成寻路
                        var finishArr:Array=new Array();
                        if(!_isFind){
                                //否，则继续搜索当前节点的周围节点；
                                getAround(_nowNode);
                        }else{
                                //是，则输出路径
                                finishArr=getPath();
                        }
                        return finishArr;
                }
                //由目标节点开始，回溯父节点，知道父节点为null，即完成路径的查找
                protected function getPath():Array{
                        var pathArr:Array=new Array();
                        //判断如果起点与终点一致，则立刻返回路径，不一致就正常寻路
                        if(_targetNode.dR==_startNode.dR && _targetNode.dC==_startNode.dC){
                                pathArr.push(_targetNode);
                        }else{
                                //完成寻路后，清空开放、封闭列表，为下次寻路做准备
                                var node:AStarGrid=_targetNode;
                                pathArr.push(node);
                                while(node.father!=null){
                                        var f:AStarGrid=node.father;
                                        pathArr.push(f);
                                        _mapData[node.dR][node.dC].alpha=.4;
                                        node=node.father;
                                }
                        }
                        pathArr[0].mc.alpha=0;
                        _isFind=false;
                        _closeList=new Array();
                        _openList=new Array();
                        _startNode=null;
                        _targetNode=null;
                        return pathArr;
                }
                //设置父节点
                protected function setFather(sonNode:AStarGrid, fatherNode:AStarGrid){
                        sonNode.father=fatherNode;
                }
                //计算节点的 g, h, f值
                protected function countHG(node:AStarGrid){
                        countH(node);
                        countG(node);
                        node.f=node.h+node.g;
                }
                //计算节点的 h 值
                protected function countH(node:AStarGrid):uint{
                        var xH:uint=Math.abs(_targetNode.dR-node.dR)*h;
                        var yH:uint=Math.abs(_targetNode.dC-node.dC)*h;
                        var hValue:uint=xH+yH;
                        node.h=hValue;
                        return hValue;
                }
                //计算节点的 g 值
                protected function countG(node:AStarGrid):uint{
                        var n:AStarGrid=node;
                        var gValue:uint=0;
                        if(n.father!=null){
                                while(n.father!=null){
                                        var f:AStarGrid=n.father;
                                        if(f.dR==n.dR || f.dC==n.dC){
                                                gValue+=g;
                                        }else{
                                                gValue+=obliqueG;
                                        }
                                        n=n.father;
                                }
                        }else{
                                gValue=0;
                        }
                        node.g=gValue;
                        return gValue;
                }
                //将节点加入开放列表
                protected function addToOpen(addedNode:AStarGrid){
                        /*for(var i:int=0; i<_openList.length;i++){
                                if(_openList[i].dR==_targetNode.dR && _openList[i].dC==_targetNode.dC){
                                        _isFind=true;
                                        setFather(_targetNode, addedNode);
                                        break;
                                }
                        }
                        */
                        //判断加入开放列表的节点是否重复，重复则重新计算节点经由当前操作节点的 g 值，如果小于原来的 g 值，则将节点的父节点置为当前操作节点，否则取消加入开放列表
                        if(!_isFind){
                                for(var n:int=0; n<_openList.length; n++){
                                        if(_openList[n].dR==addedNode.dR && _openList[n].dC==addedNode.dC){
                                                var oldG:uint=addedNode.g;
                                                var newG:uint;
                                                if(_nowNode.dR==addedNode.dR || _nowNode.dC==addedNode.dC){
                                                        newG=_nowNode.g+g;
                                                }else{
                                                        newG=_nowNode.g+obliqueG;
                                                }
                                                if(newG<oldG){
                                                        setFather(addedNode, _nowNode);
                                                        countHG(addedNode);
                                                }else{
                                                }
                                        }else{
                                                _openList.push(addedNode);
                                        }
                                }
                        }else{
                        }
                }
                //将节点加入封闭列表
                protected function addToClose(addedNode:AStarGrid){
                        _closeList.push(addedNode);
                        //判断目标节点是否在封闭列表中，在则将目标节点的父节点设为当前操作节点，寻路结束
                        for(var i:int=0; i<_closeList.length;i++){
                                if(_closeList[i].dR==_targetNode.dR && _closeList[i].dC==_targetNode.dC){
                                        _isFind=true;
                                        setFather(_targetNode, addedNode);
                                        break;
                                }
                        }
                }
                //把节点转化为相应的地图单元
                protected function gridToData(starGrid:AStarGrid):*{
                        return _mapData[starGrid.dR][starGrid.dC];
                }
                //把地图单元转化为相应的节点
                protected function dataToGrid(r:uint, c:uint, mc:DisplayObject):*{
                        return new AStarGrid(r, c, mc, null);
                }
        }
}

package{
        /*
        iiacm(着火骷髅)，网页游戏开发网 www.eb163.com 
        网页游戏互动社区
        
        A*寻路运算节点类
                为寻路提供数据节点对象
        */
        import flash.display.DisplayObject;
        public class AStarGrid{
                //节点的父节点
                public var father:AStarGrid;
                //节点所在的行号
                public var dR:uint;
                //节点所在的列号
                public var dC:uint;
                //节点对应的地图单元
                public var mc:DisplayObject;
                //从此节点到目标节点的估计移动开销
                public var h:uint=0;
                //从起点起点沿着已生成的路径到此节点的移动开销
                public var g:uint=0;
                //节点的移动开销，用来衡量此节点的路径优先度
                public var f:uint=0;
                //构造函数，初始化节点的值
                public function AStarGrid(dataR:uint=0, dataC:uint=0, displayObj:DisplayObject=null, father=null){
                        father=father;
                        dR=dataR;
                        dC=dataC;
                        mc=displayObj;
                }
        }
}

二、A*寻路的步骤
　　起初看些关于A*寻路的文章的时候，都很混乱，因为对它的原理并不了解，甚至于越看越乱…… 不过，当搞清楚了它的原理及他的寻路步骤后，就会很好理解了。正如jr在帖子中提到的那样，寻路的流程分别为：

1、寻路的过程就是检验地图单元（或称为节点）的过程，算法是通过对周围地形的评价得到路径的。寻路前要准备一些东西，为寻路存放数据作准备，他们分别是：
1）一个开放列表：存放以检验过和待检验的节点
2）一个封闭列表：存放操作过的节点，只有被检验过并且具是最优评估值（后面会介绍）的节点才是操作过的节点，路径将通过遍历他们的父节点产生
3）当前操作节点：经检验，计算出的评估值最优的节点
4）评估值：也就是jr高手帖子中提到的 f=h+g，评估值 f 的函数等于—— h（水平和垂直方向距离的和）加上g（直线方向或45度方向的移动消耗）。h、g的值可以自己约定，只要都是一个数量级的就可以了，而且 g 值在直线方向上的消耗值一定要大于 45 度方向上的移动消耗，demo中沿用 h=10，g=10（直线），g=14（45度方向）

2、从起点开始，把起点首先放入封闭列表，将它的父节点设置为null，获取起点周围的节点，将这些周围节点也加开放列表，把他们的父节点设为起点，对开放列表中的节点进行检验，同时计算他们的 f、h、g 值，选择其中 f 值最小的为下一个操作节点，这样我们就有了下一个要操作的对象，把这个节点加入到封闭列表中去

3、获取当前操作节点周围的节点，将这些节点放到开放列表，这里以为开放列表中已经有元素了，得给这些要加入开放列表的“周围节点”作个判断：如果该“周围节点”已存在列表中的话就取消添加入列表的操作，然后看这个节点在经过当前操作节点的情况下的 g 值是否小于它原来的 g 值，如果小于，就把这个更小的 g 值更新到这个“周围节点”中，且把这个“周围节点”的父节点设置为当前操作节点；如果大于，则不作改动，继续检验下一个“周围节点”，检验完后再从这些“周围节点”中挑出 f 值最小的作下一个操作节点……如此反复作递归调用

4、重复步骤 3 中的内容，直到发现封闭列表中出现有终点，说明我们已经到达了终点，终止递归调用，开始路径回溯，即由终点开始，追寻他们的父节点，这些父节点都是在寻路的过程中以评估值最优为条件设置的，当找到父节点为null的节点，就说明已回到了起点，完成了整个寻路的过程

三、小结
　　好了，demo做完了，学习过程是痛苦的，但是得到成果的时候是喜悦的……在做的过程中，只要理解了寻路的步骤，把每步要用的功能封装好，各个环节就会清晰的暴露在视野中。 这个demo只展现了A*寻路中的一些原理，还没有加入障碍策略和绕路策略等机制，这在今后会不断的做出完善。顺带提提我的体会，寻路过程中允许穿越地图单元行走，所以会看到斜线的路径，这和检验的周围节点有关，如果不希望斜线行走，则在检验周围节点的时候不添加斜线方向的节点就成；若要做类似蜂窝型的不规则地图寻路，同样在检验周围节点上作修改就可以了。由于有了中间操作对象 AStarGrid 类，寻路类只关心传入的地图数据是什么样的，而不用关心实际地图的形状，这提高了寻路类的适应性。