简单的A*寻路算法

package path
{
    import flash.display.Sprite;
    import flash.filters.GlowFilter;
    /**
     * 地图方格
     * @author hyf
     */
    public class Node extends Sprite
    {
        public var canUse:Boolean;
        public var F:int; //路径增量G值
        public var H:Number; //路径增量H值
        private var _G:int;
        private var _select:Boolean;
        public var nodeID:int;
        public var previousNode:Node;
        
        public function Node()
        {
            this.doubleClickEnabled = true;
        }
        
        public function drawRect():void
        {
            var color:uint;
            if (canUse)
            {
                color = 0x99ff99;    
            }
            else
            {
                color = 0x000000;
            }
            this.graphics.beginFill(color, 1);
            this.graphics.lineStyle(0, 0xffffff);
            this.graphics.drawRect(0, 0, 2, 2);
            this.graphics.endFill();
        }
        
        public function get select():Boolean
        {
            return _select;
        }
        
        public function set select(value:Boolean):void
        {
            _select = value;
            if (value)
            {
                this.filters = [new GlowFilter(0xF0D720, 1, 8, 8, 2.8, 3, true)];
            }
            else
            {
                this.filters = [];
            }
        }
        
        public function get G():int
        {
            _G = F + H;
            return _G;
        }
        
        public function set G(value:int):void
        {
            _G = value;
        }
    }

}

 

package path
{
    import com.dept8.Star;
    import flash.display.Sprite;
    import flash.events.MouseEvent;
    /**
     * ...
     * @author hyf
     */
    public class Map extends Sprite
    {
        private var currNode:Node;
        private var desNode:Node;
        private var _star:Star;
        private var controller:PathController;
        
        public function Map()
        {
            controller = PathController.instance;
        }
        
        /**
         *
         * @param    num  格子数目
         * @param    line 几列
         */
        public function setMapCell(num:int ,line:int):void
        {
            controller.line = line;
            controller.maxNode = num;
            var node:Node;
            controller.nodes = new Vector.<Node>(num, true);
            for (var i:int = 0; i < num; i++)
            {
                node = new Node();
                node.canUse = Math.random() > 0.3;
                node.nodeID = i;
                node.drawRect();
                controller.nodes[i] = node;
                node.x = (i % line) * (node.width);
                node.y = int(i / line) * (node.height);
                addChild(node);
                node.addEventListener(MouseEvent.CLICK, onSelectNode);
                node.addEventListener(MouseEvent.DOUBLE_CLICK, onCancel);
            }
        }
        
        private function onSelectNode(e:MouseEvent):void
        {
            if (currNode == null)
            {
                currNode = e.target as Node;
                if (currNode.canUse == false)
                {
                    currNode = null;
                    trace("初始点是障碍!");
                    return;
                }
                currNode.select = true;
                currNode.F = 0;
                currNode.H = 0;
            }
            else
            {
                trace("开始坐标:" + currNode.nodeID);
                clearPath(desNode);
                desNode = e.target as Node;
                if (desNode.canUse == false)
                {
                    trace("结束点是障碍!");
                    return;
                }
                controller.lookPath(currNode, desNode, 8);
            }
            
        }
        
        private function onCancel(e:MouseEvent):void
        {
            var target:Node = e.target as Node;
            if (currNode == target)
            {
                currNode.select = false;
                currNode = null;
            }
            else if (target == desNode)
            {
                desNode.select = false;
                desNode = null;
            }
        }
        
        public function get star():Star
        {
            if (_star == null)
            {
                _star = new Star();
            }
            return _star;
        }
        
        public function clearPath(node:Node):void
        {
            if (!node)
            {
                return;
            }
            node.filters = [];
            if (node.previousNode)
            {
                node = node.previousNode;
                clearPath(node);
            }
        }
    }

}

 

package path
{
    import flash.filters.GlowFilter;
    import flash.utils.getTimer;
    /**
     * ...
     * @author hyf
     */
    public class PathController
    {
        private static var _instance:PathController;
        private static var openList:Vector.<Node> = new Vector.<Node>();
        private static var closeList:Vector.<Node> = new Vector.<Node>();
        private var _nodes:Vector.<Node>;
        public var line:int;
        public var maxNode:int;
        private var beginTime:int;
        
        public function PathController()
        {
            if (_instance)
            {
                throw new Error("Singleton!");
            }
        }
        
        static public function get instance():PathController
        {
            if (_instance == null)
            {
                _instance = new PathController();
            }
            return _instance;
        }
        
        public function get nodes():Vector.<Node>
        {
            return _nodes;
        }
        
        public function set nodes(value:Vector.<Node>):void
        {
            _nodes = value;
        }
        
        public function addOpenList(node:Node):void
        {
            if (openList.indexOf(node) == -1)
            {
                openList.push(node);
                node.G = node.previousNode.G + 1;
            }
        }
        
        public function addCloseList(node:Node):void
        {
            if (closeList.indexOf(node) == -1)
            {
                closeList.push(node);
            }
        }
        
        public function getLeftNode(node:Node):Node
        {
            if (node.nodeID - 1 < 0 || node.nodeID - 1 > maxNode)
            {
                return null;
            }
            return nodes[node.nodeID - 1];
        }
        
        public function getRightNode(node:Node):Node
        {
            if (node.nodeID + 1 < 0 || node.nodeID + 1 > maxNode)
            {
                return null;
            }
            return nodes[node.nodeID + 1];
        }
        
        public function getLeftUpNode(node:Node):Node
        {
            if (node.nodeID - line - 2 > 0 && node.nodeID - line - 1 < maxNode)
            {
                return nodes[node.nodeID - line - 1];
            }
            return null;
        }
        
        public function getLeftDownNode(node:Node):Node
        {
            if (node.nodeID + line > 0 && node.nodeID + line + 1 < maxNode)
            {
                return nodes[node.nodeID + line + 1];
            }
            return null;
        }
        
        public function getRightUpNode(node:Node):Node
        {
            if (node.nodeID - line > 0 && node.nodeID - line + 1 < maxNode)
            {
                return nodes[node.nodeID - line + 1];
            }
            return null;
        }
        
        public function getRightDownNode(node:Node):Node
        {
            if (node.nodeID + line + 2 > 0 && node.nodeID + line + 1 < maxNode)
            {
                return nodes[node.nodeID + line + 1];
            }
            return null;
        }
        
        public function getUpNode(node:Node):Node
        {
            if (node.nodeID - line < 0 || node.nodeID - line > maxNode)
            {
                return null;
            }
            return nodes[node.nodeID - line];
        }
        
        public function getDownNode(node:Node):Node
        {
            if (node.nodeID + line < 0 || node.nodeID + line >= maxNode)
            {
                return null;
            }
            return nodes[node.nodeID + line];
        }
        
        public function lookPath(beginNode:Node, desNode:Node, direction:int):void
        {
            beginTime = getTimer();
            openList = new Vector.<Node>();
            closeList = new Vector.<Node>();
            beginNode.G = 0; //每次开始都要重置G和H的值,并清空开启和关闭列表,不然会有问题
            beginNode.H = 0;
            openList.push(beginNode);
            var currNode:Node = beginNode;
            label1:
            do
            {
                currNode = getSuitNearNode();
                addCloseList(currNode);
                openList.splice(openList.indexOf(currNode), 1);
                var nearNodes:Vector.<Node> = getAllNearNode(currNode, direction);
                label2:
                for (var i:int = 0; i < nearNodes.length; i++)
                {
                    if (nearNodes[i] == null)
                    {
                        continue label2;
                    }
                    if (nearNodes[i].canUse == false || closeList.indexOf(nearNodes[i]) != -1)
                    {
                        continue label2;
                    }
                    if (openList.indexOf(nearNodes[i]) == -1)
                    {
                        openList.push(nearNodes[i]);
                        nearNodes[i].previousNode = currNode;
                        nearNodes[i].F = currNode.F + 1;
                        nearNodes[i].H = int(getNodeH(desNode,nearNodes[i]));
                        nearNodes[i].G = nearNodes[i].F + nearNodes[i].H;
                    }
                    else
                    {
                        //trace("~~~~~");
                        if (nearNodes[i].G < currNode.G)
                        {
                            //trace("~~~~~");
                            nearNodes[i].previousNode = currNode;
                            nearNodes[i].F = currNode.F + 1;
                            nearNodes[i].H = int(getNodeH(desNode,nearNodes[i]));
                            nearNodes[i].G = nearNodes[i].F + nearNodes[i].H;
                            //nearNodes.sort(onSort);
                        }
                    }
                }
                if (openList.indexOf(desNode) != -1)
                {
                    break label1;
                }
                if (openList.length == 0)
                {
                    trace("没有找到路径!");
                }
            }
            while (openList.length > 0);
            showPath(desNode);
            trace("寻找路径花费:" + ((getTimer() - beginTime)) + "ms");
        }
        
        /**
         * 从附近的格子中找出G+H值最低的
         * @return
         */
        public function getSuitNearNode():Node
        {
            var node:Node;
            var value:int = int.MAX_VALUE;
            for (var i:int = 0; i < openList.length; i++)
            {
                if ((openList[i].G + openList[i].H) < value)
                {
                    value = openList[i].G + openList[i].H;
                    node = openList[i];
                }
            }
            return node;
        }
        
        /**
         * 计算两点间的曼哈顿距离
         * @param    currNode
         * @param    desNode
         * @return
         */
        private function getNodeH(currNode:Node ,desNode:Node):Number
        {
            var result:Number;
            result = Math.abs(currNode.x - desNode.x) + Math.abs(currNode.y - desNode.y);
            return result;
        }
        
        /**
         * 找到一个格子附近的格子
         * 4方向
         * @param    node
         * @param direction 方向
         * @return
         */
        public function getAllNearNode(node:Node, direction:int):Vector.<Node>
        {
            var nearNodes:Vector.<Node> = new Vector.<Node>();
            var downNode:Node = getDownNode(node);
            if (downNode)
            {
                nearNodes.push(downNode);
            }
            var upNode:Node = getUpNode(node);
            if (upNode)
            {
                nearNodes.push(upNode);
            }
            var leftNode:Node = getLeftNode(node);
            if (leftNode)
            {
                nearNodes.push(leftNode);
            }
            var rightNode:Node = getRightNode(node);
            if (rightNode)
            {
                nearNodes.push(rightNode);
            }
            if (direction == 8)
            {
                var leftUpNode:Node = getLeftUpNode(node);
                if (leftUpNode)
                {
                    nearNodes.push(leftUpNode);
                }
                var leftDownNode:Node = getLeftDownNode(node);
                if(leftDownNode)
                {
                    nearNodes.push(leftDownNode);
                }
                var rightUpNode:Node = getRightUpNode(node);
                if (rightUpNode)
                {
                    nearNodes.push(rightUpNode);
                }
                var rightDownNode:Node = getRightDownNode(node);
                if (rightDownNode)
                {
                    nearNodes.push(rightDownNode);
                }
            }
            //nearNodes.sort(onSort);
            return nearNodes;
        }
        
        private function onSort(first:Node, next:Node):int
        {
            return first.G - next.G;
        }
        
        private function showPath(node:Node):void
        {
            if (node.previousNode == null)
            {
                trace("No path found!");
                return;
            }
            node.filters = [new GlowFilter(0xff0000, 1, 8, 8, 2.8, 3, true)];
            if (node.previousNode)
            {
                node = node.previousNode;
                showPath(node);
            }
        }
    }

}

 

package
{
    import com.dept8.components.MyScrollArrowDown_upSkin;
    import com.dept8.components.MyScrollArrowUp_upSkin;
    import com.dept8.components.MyScrollBar_thumbIcon;
    import com.dept8.components.MyScrollThumb_overSkin;
    import com.dept8.components.MyScrollThumb_upSkin;
    import com.dept8.components.MyScrollTrack_skin;
    import fl.controls.UIScrollBar;
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.TimerEvent;
    import flash.text.TextField;
    import flash.utils.ByteArray;
    import flash.utils.setInterval;
    import flash.utils.Timer;
    import path.Map;
    import sort.Chinese;
    
    /**
     * ...
     * @author hyf
     */
    public class Main extends Sprite
    {
        private static var count:int = 0;
        
        public function Main():void
        {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(e:Event = null):void
        {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            // entry point
            var map:Map = new Map();
            map.setMapCell(200000, 400);
            addChild(map);
        }
        
        private function onTimer(e:TimerEvent):void
        {
            count ++;
            trace(count);
        }
        
    }
    
}

简单的A*寻路算法

上一篇:点击跳转另一页面显示本页面


下一篇:<摘录>MBR和分区表