ActionScript 3.0 实现的A*寻路算法源代码

ch_kexin

浏览: 899053 次
性别:
来自: 青岛

最近访客更多访客>>

ponce

hacker507

kingbird001

xutao2811

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

A*寻路算法，DEMO展示
 A*（A星）寻路算法讲解
在DEMO展示中，有三个版本，由于代码写了很久了，我也不记得下面贴出的代码是哪个版本的了，见谅。。
　
首先是文档类Index.as：

package code{

    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.text.TextFormat;

    public class Index extends Sprite{

        private var road:Road;

        public function Index(){
            stage.align = "TL";
            stage.scaleMode = "noScale";
            stage.showDefaultContextMenu = false;
            init();
        }

        //初始化
        private function init():void{
            road = new Road;
            addChild(road);
            road.x = GV.ROAD_INIT_X;
            road.y = GV.ROAD_INIT_Y;

            //地图规格申明
            var text:TextField = new TextField;
            text.htmlText = "地图规格：50*50方格，障碍物500方格　　　　寻路算法：A*（星）　　　制作：sunbright";
            addChild(text);
            text.x = 25;
            text.y = 530;
            text.width = 500;
            text.selectable = false;
            text.mouseEnabled = false;
            text.setTextFormat(new TextFormat("宋体",12,0xffffff));
            text = null;
        }

    }

}

定义参数的类：GV.as

package{

    public class GV{

        public function GV(){
            throw new Error("变量");
        }

        //Road创建的初始x、y坐标
        public static const ROAD_INIT_X:int = 25;
        public static const ROAD_INIT_Y:int = 25;

        //纵横方块参数
        public static const WIDTH_NUMBER:int = 50;
        public static const HEIGHT_NUMBER:int = 50;
        public static const WIDTH_TOTAL:int = 500;
        public static const HEIGHT_TOTAL:int = 500;
        public static const GRID_WIDTH:int = 10;
        public static const GRID_HEIGHT:int = 10;

        //障碍物个数
        public static const THING_NUMBER:int = 500;

        //state状态参数表示
        public static const HAVE_THING:int = 1;
        public static const IMPASSE_VALUE:int = 2;
        public static const MAIN_VALUE:int = 8;

        //路径耗费固定值
        public static const BIAS_VALUE:int = 14;
        public static const LINE_VALUE:int = 10;

        //文本表示
        public static const IMPASSE:String = "死路！";
        public static const RESULT_FRONT:String = "用时 ";
        public static const RESULT_BACK:String = " 毫秒";

    }

}

主要算法所存在的Road.as类

package code{

    import flash.display.Sprite;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    import flash.text.TextFormat;
    import flash.utils.clearInterval;
    import flash.utils.getTimer;
    import flash.utils.setInterval;

    public class Road extends Sprite{

        private var lands:Sprite;
        private var things:Sprite;
        private var c:Coordinate;
        private var main:Main;
        private var click:Sprite;
        private var drawPath:Sprite;
        private var result:TextField;

        private var unlockList:Array;
        private var lockList:Object;

        private var targetIX:int;
        private var targetIY:int;

        private var intervalID:int = 0;
        private var startTime:int;
        private var endTime:int;

        public function Road(){
            init();
        }

        //初始化
        private function init():void{
            //创建坐标
            c = new Coordinate;

            //创建文本框
            result = new TextField;
            result.mouseEnabled = false;
            result.autoSize = "left";
            result.y = -20;
            result.selectable = false;
            result.defaultTextFormat = new TextFormat("宋体",12,0xffffff);
            addChild(result);
            result.text = "结果";

            //创建平原
            lands = new Sprite;
            lands.mouseChildren = false;
            lands.mouseEnabled = false;
            addChild(lands);
            lands.graphics.beginFill(0xff0000);
            lands.graphics.lineStyle(0);
            lands.graphics.drawRect(0,0,GV.WIDTH_TOTAL,GV.HEIGHT_TOTAL);

            for(var i:int = 1; i < GV.WIDTH_NUMBER; i ++){
                lands.graphics.moveTo(GV.GRID_WIDTH * i,0);
                lands.graphics.lineTo(GV.GRID_WIDTH * i,GV.HEIGHT_TOTAL);
                lands.graphics.endFill();

                lands.graphics.moveTo(0,GV.GRID_HEIGHT * i);
                lands.graphics.lineTo(GV.WIDTH_TOTAL,GV.GRID_HEIGHT * i);
                lands.graphics.endFill();
            }

            //创建障碍层
            things = new Sprite;
            things.mouseChildren = false;
            things.mouseEnabled = false;
            addChild(things);

            //创建路线绘制层
            drawPath = new Sprite;
            addChild(drawPath);

            //创建操控人
            main = new Main;
            addChild(main);

            //创建控制区
            click = new Sprite;
            click.graphics.beginFill(0,0);
            click.graphics.drawRect(0,0,GV.WIDTH_TOTAL,GV.HEIGHT_TOTAL);
            addChild(click);
            click.addEventListener(MouseEvent.CLICK,clickHandle);

            //开始初始化
            randomState();
            createRoad();
        }

        //随机生成障碍
        private function randomState():void{
            var ix:int;
            var iy:int;
            var i:int = 0;

            //随机障碍
            while(i < GV.THING_NUMBER){
                ix = int(Math.random() * GV.WIDTH_NUMBER);
                iy = int(Math.random() * GV.HEIGHT_NUMBER);

                if(c[ix][iy] == null){
                    i ++;
                    c[ix][iy] = GV.HAVE_THING;
                }
            }

            //随机摆放操控人
            while(true){
                ix = int(Math.random() * GV.WIDTH_NUMBER);
                iy = int(Math.random() * GV.HEIGHT_NUMBER);

                if(c[ix][iy] == null){
                    c[ix][iy] = GV.MAIN_VALUE;
                    break;
                }
            }
        }

        //创建马路现状
        private function createRoad():void{
            for(var i:int = 0; i < GV.WIDTH_NUMBER * GV.HEIGHT_NUMBER; i ++){
                var state:State = new State;
                var ix:int = i % GV.WIDTH_NUMBER;
                var iy:int = Math.floor(i / GV.HEIGHT_NUMBER);
                state.value = c[ix][iy];

                switch(state.value){
                    case GV.HAVE_THING://如果等于1表示有障碍
                        var thing:Thing = new Thing;
                        thing.x = ix * GV.GRID_WIDTH;
                        thing.y = iy * GV.GRID_HEIGHT;
                        things.addChild(thing);
                        thing = null;
                    break;
                    case GV.IMPASSE_VALUE://如多等于2表示死路
                        //死路只需将value设置成2即可！
                    break;
                    case GV.MAIN_VALUE://如果等于8表示操控人
                        main.x = ix * GV.GRID_WIDTH;
                        main.y = iy * GV.GRID_HEIGHT;
                    break;
                }
                c[ix][iy] = state;
            }
        }

        //点击触发
        private function clickHandle(e:MouseEvent):void{
            drawPath.graphics.clear();
            targetIX = Math.floor(e.localX / GV.GRID_WIDTH);
            targetIY = Math.floor(e.localY / GV.GRID_HEIGHT);

            //时间记录
            startTime = getTimer();
            var path:Array = seekRoad();
            endTime = getTimer();

            //根据路径开始走路
            walkRoad(path);
            path = null;
        }

        //开始走路
        private function walkRoad(path:Array):void{
            //显示寻路消耗时间
            result.text = GV.RESULT_FRONT + (endTime - startTime) + GV.RESULT_BACK;

            //判断是否为死路
            if(path.length == 0){
                result.text = GV.IMPASSE + result.text;
            }

            drawPath.graphics.lineStyle(2,0xffffff);
            path.just = true;
            intervalID = setInterval(walkRoadHandle,50,path);
        }

        //走路处理
        private function walkRoadHandle(path:Array):void{
            //是否路已经走完
            if(path.length == 0){
                //结束走路
                clearInterval(intervalID);

                //开启触发器
                click.mouseEnabled = true;

                return;
            }

            //开始走路
            var obj:Object = path.shift();
            main.x = obj.x;
            main.y = obj.y;
            obj = null;

            //绘制路径
            if(path.just){
                path.just = false;
                drawPath.graphics.moveTo(main.x + 5,main.y + 5);
            }else{
                drawPath.graphics.lineTo(main.x + 5,main.y + 5);
            }
        }

        //开始寻路
        private function seekRoad():Array{
            //关闭触发器
            click.mouseEnabled = false;

            //判断目标点是不是有障碍，或者是不是死路
            if(c[targetIX][targetIY].isThing || c[targetIX][targetIY].isWalk){
                return new Array;
            }

            //寻路初始化
            var path:Array = new Array;
            unlockList = new Array;
            lockList = new Object;

            //初始标记
            var ix:int = main.ix;
            var iy:int = main.iy;

            //创建开始标记
            var sign:Sign = new Sign(ix,iy,0,0,null);
            lockList[ix + "_" + iy] = sign;

            while(true){
                //生成八个方向的标记开启
                addUnlockList(createSign(ix + 1,iy - 1,true ,sign));
                addUnlockList(createSign(ix + 1,iy ,false,sign));
                addUnlockList(createSign(ix + 1,iy + 1,true ,sign));
                addUnlockList(createSign(ix - 1,iy + 1,true ,sign));
                addUnlockList(createSign(ix ,iy + 1,false,sign));
                addUnlockList(createSign(ix - 1,iy ,false,sign));
                addUnlockList(createSign(ix - 1,iy - 1,true ,sign));
                addUnlockList(createSign(ix ,iy - 1,false,sign));

                //判断开启列表是否已经为空
                if(unlockList.length == 0){
                    break;
                }

                //从开启列表中取出h值最低的标记
                unlockList.sortOn("f",Array.NUMERIC);
                sign = unlockList.shift();
                lockList[sign.ix + "_" + sign.iy] = sign;
                ix = sign.ix;
                iy = sign.iy;

                //判断是否找出路径
                if(ix == targetIX && iy == targetIY){
                    while(sign != null){
                        path.push(sign.getSign());
                        sign = sign.p;
                    }
                    break;
                }
            }

            sign = null;

            return path.reverse();
        }

        //添加到开启标记列表
        private function addUnlockList(sign:Sign):void{
            if(sign){
                unlockList.push(sign);
                unlockList[sign.ix + "_" + sign.iy] = sign;
            }
        }

        //生成标记
        private function createSign(ix:int,iy:int,p:Boolean,_p:Sign):Sign{
            //是否出格
            if(ix < 0 || iy < 0 || ix >= GV.WIDTH_NUMBER || iy >= GV.HEIGHT_NUMBER){
                return null;
            }

            //是否有障碍物
            if(c[ix][iy].isThing){
                return null;
            }

            //是否已经加入关闭标记列表
            if(lockList[ix + "_" + iy]){
                return null;
            }

            //是否已经加入开启标记列表
            if(unlockList[ix + "_" + iy]){
                return null;
            }

            //判断当斜着走的时候，它的上下或者左右是否有障碍物
            if(p){
                if(c[_p.ix][iy].isThing || c[ix][_p.iy].isThing){
                    return null;
                }
            }

            var cx:Number = Math.abs(targetIX - ix);
            var cy:Number = Math.abs(targetIY - iy);
            return new Sign(ix,iy,
                            p ? GV.BIAS_VALUE : GV.LINE_VALUE,
                            (cx + cy) * 10,
                            _p);
        }

    }

}

标记数据记录，Sign.as类

package code{

    public class Sign{

        private var _ix:Number;
        private var _iy:Number;
        private var _p:Sign;
        private var _f:int = 0;
        private var _g:int = 0;
        private var _h:int = 0;
        //f表示路径评分、g表示当前移动耗费、h表示当前估计移动耗费
        //公式：f = g + h，表示路径评分的算法
        //ng值表示以父标记为主标记的g值
        //nh值表示当前估计移动耗费

        public function Sign(_ix:Number,_iy:Number,ng:int,nh:int,_p:Sign = null){
            this._ix = _ix;
            this._iy = _iy;
            this._p = _p;

            if(_p){
                _g = _p.g + ng;
                _h = nh;
                _f = _g + _h;
            }
        }

        //获取该标记的坐标
        public function getSign():Object{
            return {x:_ix * GV.GRID_WIDTH,y:_iy * GV.GRID_HEIGHT};
        }

        //获取它表示的x坐标
        public function get ix():int{
            return _ix;
        }

        //获取它表示的y坐标
        public function get iy():int{
            return _iy;
        }

        //获取父标记
        public function get p():Sign{
            return _p;
        }

        //获取路径评分
        public function get f():int{
            return _f;
        }

        //获取当前路径移动耗费
        public function get g():int{
            return _g;
        }

        //获取当前路径耗费估值
        public function get h():int{
            return _h;
        }

        //重写toString值
        public function toString():String{
            return ix + "," + iy;
        }

    }

}

某点状态类，State.as

package code{

    public class State{

        public var value:int = 0;

        public function State(){

        }

        //获取是否障碍
        public function get isThing():Boolean{
            return value == GV.HAVE_THING;
        }

        //获取是否死路
        public function get isWalk():Boolean{
            return value == GV.IMPASSE_VALUE;
        }

        //重写toString
        public function toString():String{
            return value.toString();
        }

    }

}

物体类：Thing.as

package code{

    import flash.display.Sprite;

    public class Thing extends Sprite{

        public function Thing(){
            init();
        }

        //初始化
        private function init():void{
            graphics.beginFill(0);
            graphics.drawRect(0,0,GV.GRID_WIDTH,GV.GRID_HEIGHT);

            mouseEnabled = false;
            mouseChildren = false;
        }

}

}

坐标系类，Coordinate.as

package code{

    public dynamic class Coordinate extends Array{

        public function Coordinate(){
            init();
        }

        //初始化
        private function init():void{
            for(var i:int = 0; i < GV.WIDTH_NUMBER; i ++){
                push(new Array(GV.HEIGHT_NUMBER));
            }
        }

    }

}

主角类，Main.as

package code{

    import flash.display.Sprite;

    public class Main extends Sprite{

        public function Main(){
            init();
        }

        //初始化
        private function init():void{
            graphics.beginFill(0x0000ff);
            graphics.drawRect(0,0,GV.GRID_WIDTH,GV.GRID_HEIGHT);

            mouseEnabled = false;
            mouseChildren = false;
        }

        //获取ix坐标
        public function get ix():int{
            return int(x / GV.GRID_WIDTH);
        }

        //获取iy坐标
        public function get iy():int{
            return int(y / GV.GRID_HEIGHT);
        }

    }

}

源文件打包下载
下载源文件，直接打开move.fla运行即可