AStar

/**
 * Copyright fakestar0826 ( http://wonderfl.net/user/fakestar0826 )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/nrZ5
 */

package {
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.display.StageScaleMode;
    import flash.display.StageAlign;
    import flash.display.Sprite;
    
    [SWF(backgroundColor = 0xFFFFFF)]
    public class Game extends Sprite
    {
        private var _cellSize:int = 20;
        private var _grid:Grid;
        private var _player:Sprite;
        private var _index:int;
        private var _path:Array;

        public function Game()
        {
            stage.align = StageAlign.TOP_LEFT;
            stage.scaleMode = StageScaleMode.NO_SCALE;

            makePlayer();
            makeGrid();
            stage.addEventListener(MouseEvent.CLICK, onGridClick);
        }

        /**
         * プレーヤのスプライトを生成する。ここではただの丸。
         */
        private function makePlayer():void
        {
            _player = new Sprite();
            _player.graphics.beginFill(0xff0000);
            _player.graphics.drawCircle(0, 0, 5);
            _player.graphics.endFill();
            _player.x = Math.random() * 600;
            _player.y = Math.random() * 600;
            addChild(_player);
        }

        /**
         * 格子を生成し、ランダムに立ち入り禁止ノードにする。
         */
        private function makeGrid():void
        {
            _grid = new Grid(30, 30);
            for (var i:int = 0; i < 200; i++)
            {
                _grid.setWalkable(Math.floor(Math.random() * 30),
                                  Math.floor(Math.random() * 30),
                                  false);
            }
            drawGrid();
        }

        /**
         * 格子のマス目をその状態に基づいて色づけして描画する。
         */
        private function drawGrid():void
        {
            graphics.clear();
            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);
                    graphics.lineStyle(0);
                    graphics.beginFill(getColor(node));
                    graphics.drawRect(i * _cellSize,
                                      j * _cellSize, _cellSize,
                                      _cellSize);
                }
            }
        }

        /**
         * ノードの状態に応じて色を決める。
         */
        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;
        }

        /**
         * GridViewへのクリックイベントを処理する。
         * スタートとゴールのノードを設定して経路探索する。
         */
        private function onGridClick(event:MouseEvent):void
        {
            var xpos:int = Math.floor(mouseX / _cellSize);
            var ypos:int = Math.floor(mouseY / _cellSize);
            _grid.setEndNode(xpos, ypos);

            xpos = Math.floor(_player.x / _cellSize);
            ypos = Math.floor(_player.y / _cellSize);
            _grid.setStartNode(xpos, ypos);

            drawGrid();
            findPath();
        }

        /**
         * AStarのインスタンスを生成して、経路探索に用いる。
         */
        private function findPath():void
        {
            var astar:AStar = new AStar();
            if (astar.findPath(_grid))
            {
                _path = astar.path;
                _index = 0;
                addEventListener(Event.ENTER_FRAME, onEnterFrame);
            }
        }

        /**
         * 経路上の次のノードを選んで、ゆっくり近づく。
         */
        private function onEnterFrame(event:Event):void
        {
            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)
                {
                    removeEventListener(Event.ENTER_FRAME, onEnterFrame);
                }
            }
            else
            {
                // 目標まで道のりの半分まで移動することによりイージングする
                _player.x += dx * 0.5;
                _player.y += dy * 0.5;
            }
        }
    }
}

import flash.events.MouseEvent;
import flash.display.Sprite;

class Grid
{
    private var _startNode:Node;
    private var _endNode:Node;
    private var _nodes:Array;
    private var _numCols:int;
    private var _numRows:int;
    
    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);
            }

        }

    }
    
    public function getNode(x:int, y:int):Node
    {
        return _nodes[x][y] as Node;
    }
    
    public function setEndNode(x:int, y:int):void
    {
        _endNode = _nodes[x][y] as Node;
    }
    
    public function setStartNode(x:int, y:int):void
    {
        _startNode = _nodes[x][y] as Node;
    }
    
    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 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 function Node(x:int, y:int)
    {
        this.x = x;
        this.y = y;
    }

}

class AStar
{
    private var _open:Array;
        private var _closed:Array;
        private var _grid:Grid;
        private var _endNode:Node;
        private var _startNode:Node;
        private var _path:Array;
//      private var _heuristic:Function = manhattan;
        private var _heuristic:Function = euclidian;
//      private var _heuristic:Function = diagonal;
        private var _straightCost:Number = 1.0;
        private var _diagCost:Number = Math.SQRT2;

        public function AStar()
        {
        }

        public function findPath(grid:Grid):Boolean
        {
            _grid = grid;
            _open = new Array();
            _closed = new Array();

            _startNode = _grid.startNode;
            _endNode = _grid.endNode;

            _startNode.g = 0;
            _startNode.h = _heuristic(_startNode);
            _startNode.f = _startNode.g + _startNode.h;

            return search();
        }

        public function search():Boolean
        {
            var node:Node = _startNode;
            while (node != _endNode)
            {
                var startX:int = Math.max(0, node.x - 1);
                var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
                var startY:int = Math.max(0, node.y - 1);
                var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

                for (var i:int = startX; i <= endX; i++)
                {
                    for (var j:int = startY; j <= endY; j++)
                    {
                        var test:Node = _grid.getNode(i, j);
                        // if (test == node || !test.walkable) continue;
                        if(test == node || 
                           !test.walkable ||
                           !_grid.getNode(node.x, test.y).walkable ||
                           !_grid.getNode(test.x, node.y).walkable)
                        {
                            continue;
                        }

                        var cost:Number = _straightCost;
                        if (!((node.x == test.x) || (node.y == test.y)))
                        {
                            cost = _diagCost;
                        }
                        //var g:Number = node.g + cost;
                        var g:Number = node.g + cost * test.costMultiplier;
                        var h:Number = _heuristic(test);
                        var f:Number = g + h;
                        if (isOpen(test) || isClosed(test))
                        {
                            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.push(test);
                        }
                    }
                }
                _closed.push(node);
                if (_open.length == 0)
                {
                    trace("no path found");
                    return false
                }
                _open.sortOn("f", Array.NUMERIC);
                node = _open.shift() as Node;
            }
            buildPath();
            return true;
        }

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

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

        private function isOpen(node:Node):Boolean
        {
            for (var i:int = 0; i < _open.length; i++)
            {
                if (_open[i] == node)
                {
                    return true;
                }
            }
            return false;
        }

        private function isClosed(node:Node):Boolean
        {
            for (var i:int = 0; i < _closed.length; i++)
            {
                if (_closed[i] == node)
                {
                    return true;
                }
            }
            return false;
        }

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

        private 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) * _straightCost;
        }

        private 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);
        }

        public function get visited():Array
        {
            return _closed.concat(_open);
        }

}

class GridView extends Sprite
{
    private var _cellSize:int = 10;
    private var _grid:Grid;
    
    public function GridView(grid:Grid)
    {
        _grid = grid;
        drawGrid();
        findPath();
        addEventListener(MouseEvent.CLICK, onGridClick);
    }
    
    public function drawGrid():void
    {
        graphics.clear();
        
        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);
                graphics.lineStyle(0);
                graphics.beginFill(getColor(node));
                graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
            }

        }

    }
    
    private function getColor(node:Node):uint
    {
        if(!node.walkable)
        {
            return 0x000000;
        }
        if(node == _grid.startNode)
        {
            return 0x666666;
        }
        if(node == _grid.endNode)
        {
            return 0x666666;
        }
        
        return 0xFFFFFF;
    }
    
    private function onGridClick(e:MouseEvent):void
    {
        var xpos:int = Math.floor(e.localX / _cellSize);
        var ypos:int = Math.floor(e.localY / _cellSize);
        
        _grid.setWalkable(xpos, ypos, !_grid.getNode(xpos, ypos).walkable);
        
        drawGrid();
        findPath();
    }
    
    private function findPath():void
    {
        var astar:AStar = new AStar();
        
        if(astar.findPath(_grid))
        {
            showVisited(astar);
            showPath(astar);
        }

    }
    
    private function showVisited(astar:AStar):void
    {
        var visited:Array = astar.visited;
        for(var i:int = 0;i < visited.length;i++)
        {
            graphics.beginFill(0xCCCCCC);
            graphics.drawRect(visited[i].x * _cellSize, visited[i].y * _cellSize, _cellSize, _cellSize);
            graphics.endFill();
        }

    }
    
    private function showPath(astar:AStar):void
    {
        var path:Array = astar.path;
        for(var i:int = 0;i < path.length;i++)
        {
            graphics.lineStyle(0);
            graphics.beginFill(0xFFFFFF);
            graphics.drawCircle(path[i].x * _cellSize + _cellSize / 2, path[i].y * _cellSize + _cellSize / 2, _cellSize / 3);
            graphics.endFill();
        }

    }




}