`

A*寻路 -- 算法优化

 
阅读更多

 

基本思路:

 

1二叉堆

2用version代替close open列表

3用精简的估计公式

4提前运算

5代码本身的优化。

 

这个寻路算法基本还没找到as3写的能超过他的。

 


 

package {
    /**
     * ...
     * @author sliz http://game-develop.net/blog/
     */
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.Sprite;
    import flash.display.StageAlign;
    import flash.display.StageScaleMode;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.Rectangle;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import sliz.miniui.Button;
    import sliz.miniui.Checkbox;
    import sliz.miniui.Label;
    import sliz.miniui.LabelInput;
    import sliz.miniui.layouts.BoxLayout;
    import sliz.miniui.Window;

    public class Test extends Sprite {
        private var _cellSize:int = 5;
        private var _grid:Grid;
        private var _player:Sprite;
        private var _index:int;
        private var _path:Array;

        private var tf:Label;
        private var astar:AStar;

        private var path:Sprite = new Sprite();
        private var image:Bitmap = new Bitmap(new BitmapData(1, 1));
        private var imageWrapper:Sprite = new Sprite();

        public function Test(){
            stage.align = StageAlign.TOP_LEFT;
            stage.scaleMode = StageScaleMode.NO_SCALE;
            stage.frameRate = 100;
            addChild(imageWrapper);
            imageWrapper.addChild(image);
            makePlayer();

            var w:Window = new Window(this, 20, 20, "tool");
            numCols = new LabelInput("numCols ", "numCols");
            numCols.setValue("115");
            w.add(numCols);
            numRows = new LabelInput("numRows ", "numRows");
            w.add(numRows);
            numRows.setValue("115");
            cellSize = new LabelInput("cellSize", "cellSize");
            cellSize.setValue("4");
            w.add(cellSize);
            density = new LabelInput("density ", "density");
            density.setValue("0.1");
            w.add(density);
            isEight = new Checkbox("eight directions");
            isEight.setToggle(true);
            w.add(isEight);
            tf = new Label("info");
            w.add(tf);
            w.add(new sliz.miniui.Link("author sliz"));
            var btn:Button = new Button("new", 0, 0, null, newMap);
            w.add(btn, null, 0.8);
            w.setLayout(new BoxLayout(w, 1, 5));
            w.doLayout();
            imageWrapper.addEventListener(MouseEvent.CLICK, onGridClick);
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
            imageWrapper.addChild(path);
            makeGrid();
        }

        private function newMap(e:Event):void {
            makeGrid();
        }

        private function makePlayer():void {
            _player = new Sprite();
            _player.graphics.beginFill(0xff00ff);
            _player.graphics.drawCircle(0, 0, 2);
            _player.graphics.endFill();
            imageWrapper.addChild(_player);
        }

        private function makeGrid():void {
            var rows:int = int(numRows.getValue());
            var cols:int = int(numCols.getValue());
            _cellSize = int(cellSize.getValue());
            _grid = new Grid(cols, rows);
            for (var i:int = 0; i < rows * cols * Number(density.getValue()); i++){
                _grid.setWalkable(Math.floor(Math.random() * cols), Math.floor(Math.random() * rows), false);
            }
            _grid.setWalkable(0, 0, true);
            _grid.setWalkable(cols / 2, rows / 2, false);
            if (isEight.getToggle())
                _grid.calculateLinks();
            else
                _grid.calculateLinks(1);
            astar = new AStar(_grid);
            drawGrid();
            isClick = false;
            _player.x = 0;
            _player.y = 0;
            path.graphics.clear();
        }


        private function drawGrid():void {
            image.bitmapData = new BitmapData(_grid.numCols * _cellSize, _grid.numRows * _cellSize, false, 0xffffff);
            for (var i:int = 0; i < _grid.numCols; i++){
                for (var j:int = 0; j < _grid.numRows; j++){
                    var node:Node = _grid.getNode(i, j);
                    if (!node.walkable){
                        image.bitmapData.fillRect(new Rectangle(i * _cellSize, j * _cellSize, _cellSize, _cellSize), getColor(node));
                    }
                }
            }
        }

        private function getColor(node:Node):uint {
            if (!node.walkable)
                return 0;
            if (node == _grid.startNode)
                return 0xcccccc;
            if (node == _grid.endNode)
                return 0xcccccc;
            return 0xffffff;
        }

        private function onGridClick(event:MouseEvent):void {
            var xpos:int = Math.floor(mouseX / _cellSize);
            var ypos:int = Math.floor(mouseY / _cellSize);
            xpos = Math.min(xpos, _grid.numCols - 1);
            ypos = Math.min(ypos, _grid.numRows - 1);
            _grid.setEndNode(xpos, ypos);

            xpos = Math.floor(_player.x / _cellSize);
            ypos = Math.floor(_player.y / _cellSize);
            _grid.setStartNode(xpos, ypos);
            findPath();
            path.graphics.clear();
            path.graphics.lineStyle(0, 0xff0000, 0.5);
            path.graphics.moveTo(_player.x, _player.y);
        }

        private function findPath():void {
            var time:int = getTimer();
            if (astar.findPath()){
                time = getTimer() - time;
                tf.text = time + "ms   length:" + astar.path.length;
                _path = astar.path;
                _index = 0;
                isClick = true;
            } else {
                time = getTimer() - time;
                tf.text = time + "ms 找不到";
            }
        }

        private var isClick:Boolean = false;
        private var numCols:LabelInput;
        private var numRows:LabelInput;
        private var cellSize:LabelInput;
        private var density:LabelInput;
        private var isEight:Checkbox;

        private function onEnterFrame(event:Event):void {
            if (!isClick){
                return;
            }
            var targetX:Number = _path[_index].x * _cellSize + _cellSize / 2;
            var targetY:Number = _path[_index].y * _cellSize + _cellSize / 2;
            var dx:Number = targetX - _player.x;
            var dy:Number = targetY - _player.y;
            var dist:Number = Math.sqrt(dx * dx + dy * dy);
            if (dist < 1){
                _index++;
                if (_index >= _path.length){
                    isClick = false;
                }
            } else {
                _player.x += dx * .5;
                _player.y += dy * .5;
                path.graphics.lineTo(_player.x, _player.y);
            }
        }
    }
}


/**
 * ...
 * @author sliz http://game-develop.net/blog/
 */
class AStar {
    //private var _open:Array;
    private var _open:BinaryHeap;
    private var _grid:Grid;
    private var _endNode:Node;
    private var _startNode:Node;
    private var _path:Array;
    public var heuristic:Function;
    private var _straightCost:Number = 1.0;
    private var _diagCost:Number = Math.SQRT2;
    private var nowversion:int = 1;

    public function AStar(grid:Grid){
        this._grid = grid;
        heuristic = euclidian2;

    }

    private function justMin(x:Object, y:Object):Boolean {
        return x.f < y.f;
    }

    public function findPath():Boolean {
        _endNode = _grid.endNode;
        nowversion++;
        _startNode = _grid.startNode;
        //_open = [];
        _open = new BinaryHeap(justMin);
        _startNode.g = 0;
        return search();
    }

    public function search():Boolean {
        var node:Node = _startNode;
        node.version = nowversion;
        while (node != _endNode){
            var len:int = node.links.length;
            for (var i:int = 0; i < len; i++){
                var test:Node = node.links[i].node;
                var cost:Number = node.links[i].cost;
                var g:Number = node.g + cost;
                var h:Number = heuristic(test);
                var f:Number = g + h;
                if (test.version == nowversion){
                    if (test.f > f){
                        test.f = f;
                        test.g = g;
                        test.h = h;
                        test.parent = node;
                    }
                } else {
                    test.f = f;
                    test.g = g;
                    test.h = h;
                    test.parent = node;
                    _open.ins(test);
                    test.version = nowversion;
                }

            }
            if (_open.a.length == 1){
                return false;
            }
            node = _open.pop() as Node;
        }
        buildPath();
        return true;
    }

    private function buildPath():void {
        _path = [];
        var node:Node = _endNode;
        _path.push(node);
        while (node != _startNode){
            node = node.parent;
            _path.unshift(node);
        }
    }

    public function get path():Array {
        return _path;
    }

    public function manhattan(node:Node):Number {
        return Math.abs(node.x - _endNode.x) + Math.abs(node.y - _endNode.y);
    }

    public function manhattan2(node:Node):Number {
        var dx:Number = Math.abs(node.x - _endNode.x);
        var dy:Number = Math.abs(node.y - _endNode.y);
        return dx + dy + Math.abs(dx - dy) / 1000;
    }

    public function euclidian(node:Node):Number {
        var dx:Number = node.x - _endNode.x;
        var dy:Number = node.y - _endNode.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    private var TwoOneTwoZero:Number = 2 * Math.cos(Math.PI / 3);

    public function chineseCheckersEuclidian2(node:Node):Number {
        var y:int = node.y / TwoOneTwoZero;
        var x:int = node.x + node.y / 2;
        var dx:Number = x - _endNode.x - _endNode.y / 2;
        var dy:Number = y - _endNode.y / TwoOneTwoZero;
        return sqrt(dx * dx + dy * dy);
    }

    private function sqrt(x:Number):Number {
        return Math.sqrt(x);
    }

    public function euclidian2(node:Node):Number {
        var dx:Number = node.x - _endNode.x;
        var dy:Number = node.y - _endNode.y;
        return dx * dx + dy * dy;
    }

    public function diagonal(node:Node):Number {
        var dx:Number = Math.abs(node.x - _endNode.x);
        var dy:Number = Math.abs(node.y - _endNode.y);
        var diag:Number = Math.min(dx, dy);
        var straight:Number = dx + dy;
        return _diagCost * diag + _straightCost * (straight - 2 * diag);
    }
}

class Grid {

    private var _startNode:Node;
    private var _endNode:Node;
    private var _nodes:Array;
    private var _numCols:int;
    private var _numRows:int;

    private var type:int;

    private var _straightCost:Number = 1.0;
    private var _diagCost:Number = Math.SQRT2;

    public function Grid(numCols:int, numRows:int){
        _numCols = numCols;
        _numRows = numRows;
        _nodes = new Array();

        for (var i:int = 0; i < _numCols; i++){
            _nodes[i] = new Array();
            for (var j:int = 0; j < _numRows; j++){
                _nodes[i][j] = new Node(i, j);
            }
        }
    }

    /**
     *
     * @param    type    0四方向 1八方向 2跳棋
     */
    public function calculateLinks(type:int = 0):void {
        this.type = type;
        for (var i:int = 0; i < _numCols; i++){
            for (var j:int = 0; j < _numRows; j++){
                initNodeLink(_nodes[i][j], type);
            }
        }
    }

    public function getType():int {
        return type;
    }

    /**
     *
     * @param    node
     * @param    type    0八方向 1四方向 2跳棋
     */
    private function initNodeLink(node:Node, type:int):void {
        var startX:int = Math.max(0, node.x - 1);
        var endX:int = Math.min(numCols - 1, node.x + 1);
        var startY:int = Math.max(0, node.y - 1);
        var endY:int = Math.min(numRows - 1, node.y + 1);
        node.links = [];
        for (var i:int = startX; i <= endX; i++){
            for (var j:int = startY; j <= endY; j++){
                var test:Node = getNode(i, j);
                if (test == node || !test.walkable){
                    continue;
                }
                if (type != 2 && i != node.x && j != node.y){
                    var test2:Node = getNode(node.x, j);
                    if (!test2.walkable){
                        continue;
                    }
                    test2 = getNode(i, node.y);
                    if (!test2.walkable){
                        continue;
                    }
                }
                var cost:Number = _straightCost;
                if (!((node.x == test.x) || (node.y == test.y))){
                    if (type == 1){
                        continue;
                    }
                    if (type == 2 && (node.x - test.x) * (node.y - test.y) == 1){
                        continue;
                    }
                    if (type == 2){
                        cost = _straightCost;
                    } else {
                        cost = _diagCost;
                    }
                }
                node.links.push(new Link(test, cost));
            }
        }
    }

    public function getNode(x:int, y:int):Node {
        return _nodes[x][y];
    }

    public function setEndNode(x:int, y:int):void {
        _endNode = _nodes[x][y];
    }

    public function setStartNode(x:int, y:int):void {
        _startNode = _nodes[x][y];
    }

    public function setWalkable(x:int, y:int, value:Boolean):void {
        _nodes[x][y].walkable = value;
    }

    public function get endNode():Node {
        return _endNode;
    }

    public function get numCols():int {
        return _numCols;
    }

    public function get numRows():int {
        return _numRows;
    }

    public function get startNode():Node {
        return _startNode;
    }

}

class Link {
    public var node:Node;
    public var cost:Number;

    public function Link(node:Node, cost:Number){
        this.node = node;
        this.cost = cost;
    }

}

class BinaryHeap {
    public var a:Array = [];
    public var justMinFun:Function = function(x:Object, y:Object):Boolean {
        return x < y;
    };

    public function BinaryHeap(justMinFun:Function = null){
        a.push(-1);
        if (justMinFun != null)
            this.justMinFun = justMinFun;
    }

    public function ins(value:Object):void {
        var p:int = a.length;
        a[p] = value;
        var pp:int = p >> 1;
        while (p > 1 && justMinFun(a[p], a[pp])){
            var temp:Object = a[p];
            a[p] = a[pp];
            a[pp] = temp;
            p = pp;
            pp = p >> 1;
        }
    }

    public function pop():Object {
        var min:Object = a[1];
        a[1] = a[a.length - 1];
        a.pop();
        var p:int = 1;
        var l:int = a.length;
        var sp1:int = p << 1;
        var sp2:int = sp1 + 1;
        while (sp1 < l){
            if (sp2 < l){
                var minp:int = justMinFun(a[sp2], a[sp1]) ? sp2 : sp1;
            } else {
                minp = sp1;
            }
            if (justMinFun(a[minp], a[p])){
                var temp:Object = a[p];
                a[p] = a[minp];
                a[minp] = temp;
                p = minp;
                sp1 = p << 1;
                sp2 = sp1 + 1;
            } else {
                break;
            }
        }
        return min;
    }
}

class Node {
    public var x:int;
    public var y:int;
    public var f:Number;
    public var g:Number;
    public var h:Number;
    public var walkable:Boolean = true;
    public var parent:Node;
    //public var costMultiplier:Number = 1.0;
    public var version:int = 1;
    public var links:Array;

    //public var index:int;
    public function Node(x:int, y:int){
        this.x = x;
        this.y = y;
    }
}

  • 大小: 15.8 KB
分享到:
评论

相关推荐

    A*寻路 -- 更加真实 的路径(二)

    A*算法作为其中的一种高效寻路算法,被广泛应用。本文将深入探讨A*寻路算法,以及它如何提供更加真实的路径计算。我们将通过源码分析来理解其工作原理,并探索在实际项目中如何运用。 A*算法是Dijkstra算法的一个...

    【转】A*寻路 -- 弗洛伊德(Floyd)算法

    A*(A-star)寻路算法是一种启发式搜索算法,它的主要目标是在一个带有成本的图中找到从起点到终点的最短路径。A*算法结合了Dijkstra算法的最优化特性以及最佳优先搜索的效率,通过使用一个评估函数来预测从当前节点...

    cocos creator 实现A*寻路

    A*(A-Star)寻路算法是路径规划领域中一种广泛应用的算法,它结合了Dijkstra算法的最短路径特性与优先级队列的效率优势。在Cocos Creator中,利用JavaScript实现A*寻路算法可以为游戏或交互式应用提供高效、智能的...

    A*走路 自动寻路A*算法 易语言源码优化版

    这个“A*走路 自动寻路A*算法 易语言源码优化版”是一个用易语言实现的A*算法优化版本,适用于游戏开发、地图导航等场景,帮助程序自动找到从起点到终点的最短路径。 A*算法的核心在于结合了Dijkstra算法的最短路径...

    A*寻路算法 源码

    A*寻路算法(A* Pathfinding Algorithm)是游戏开发、地图导航、机器人路径规划等领域广泛应用的一种高效路径搜索算法。它结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索,...

    A*寻路算法《三》

    A*寻路算法是计算机图形学、游戏开发和人工智能领域中的一个重要算法,它用于寻找从起点到终点的最短路径。本节将深入探讨A*算法的原理、工作流程及其在Unity引擎中的应用。 A*算法的核心思想是结合了Dijkstra算法...

    极度优化的A*寻路算法

    A*(A-star)寻路算法是一种广泛应用在游戏开发、地图导航、机器人路径规划等领域的图搜索算法。它结合了Dijkstra算法的最短路径保证和Greedy最佳优先搜索的效率,通过引入启发式函数来指导搜索过程,使得在有限计算...

    C# A*寻路算法 带测试界面

    A*(A-Star)寻路算法是一种广泛应用在游戏开发、地图导航、机器人路径规划等领域的高效路径搜索算法。它结合了Dijkstra算法的全局最优性和Greedy Best-First Search算法的局部优先性,通过引入启发式函数来指导搜索...

    a*寻路算法,c++类

    **A*寻路算法**是一种广泛应用的路径搜索算法,它结合了Dijkstra算法的最短路径特性以及优先级队列的效率,同时引入了启发式信息以提高搜索速度。在游戏开发、图形图像处理、地图导航等领域,A*算法被广泛用于计算两...

    A*寻路算法源码 附带桌面演示工具

    A*算法是自动寻路的理想解决办法 像自动寻找NPC 自动寻找地图出口 我写的这个只是简单的实现了功能 在运算效率上没有做优化 在接下来的版本中我会增加二*堆算法 来提高A*算法的效率 请大家多多关注 包中还有一个我用...

    A*寻路源代码:A Star Path Finding

    A*(A-Star)寻路算法是一种广泛应用在游戏开发、地图导航、图形处理等领域中的高效路径搜索算法。它结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过评估节点的启发式信息来找到从起点到终点的...

    A*寻路Pro3.6

    **A*寻路算法详解** A*(A-Star)寻路算法是一种在图形或网格中寻找最短路径的搜索算法,广泛应用于游戏开发、地图导航、网络路由等多个领域。其核心在于结合了Dijkstra算法的全局最优性与曼哈顿距离(或欧几里得...

    A*寻路算法《六》

    A*寻路算法是计算机图形学、游戏开发和人工智能领域中的一个重要算法,它用于寻找从起点到终点的最短路径。这个算法结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索,使...

    A*寻路算法代码示例333

    A*(A-star)寻路算法是一种广泛应用在游戏开发、地图导航、机器人路径规划等领域的高效路径搜索算法。它的核心思想是在Dijkstra算法的基础上引入了启发式信息,以更智能的方式寻找从起点到目标点的最短路径。下面将...

    A* 寻路算法实例

    A*(发音为 "A-star")寻路算法是一种在图形中寻找最短路径的高效算法,广泛应用于游戏开发、地图导航、网络路由等领域。它结合了Dijkstra算法的全局最优性和最佳优先搜索的效率,通过引入启发式函数来估计从起点到...

    A*智能寻路算法

    **A* 智能寻路算法** A*(发音为 "A-star")是一种在图形搜索中广泛应用的路径寻找算法,特别是在游戏开发、地图导航、机器人路径规划等领域。它结合了Dijkstra算法的最短路径特性与启发式搜索的优势,以更高效的...

    封装好的寻路算法 A*算法

    6. **性能优化**: - 使用记忆化(Memoization)技术,存储已经计算过的节点状态,避免重复计算。 - 利用数据结构优化,如使用四向连接或八向连接减少搜索空间。 7. **适用性**: - A*算法适用于各种复杂度的...

    a*寻路 c++实现

    在C++中实现a*寻路算法,通常会用到数据结构如二叉堆(优先队列)来优化性能。在此项目中,八方向的移动模型被采用,意味着在网格环境中,每个节点可以向上、下、左、右以及对角线方向移动,这大大增加了路径的可能...

    一个A*寻路算法

    A*寻路算法,只是保证在低消耗的情况在最短的时间找出路径,但A*寻路算法寻出来的路不一定是最近,但也绝对不会远的离谱,可也不排除你对路径评分算法的优化可以做到最快最短最低消耗,或者对最终路径的优化来达到...

Global site tag (gtag.js) - Google Analytics