forked from: forked from: A* Path Finding

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

// forked from Yukulele's forked from: A* Path Finding
// forked from mtok's A* Path Finding
package  
{
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.filters.GlowFilter;
    
    /**
     * ...
     * @author Motoki Matsumoto
     */
    public class AStarTest extends Sprite
    {
        private var _start:Pointer;
        private var _end:Pointer;
        private var _astarGrid:AStarGrid;
        private var _astar:AStar;
        private var _cellSize:Number = 20;
        private var _grid:Grid;
        public function AStarTest() 
        {
            addEventListener(Event.ADDED_TO_STAGE, addedToStageHandler);
        }
        
        private function addedToStageHandler(e:Event):void 
        {
            removeEventListener(Event.ADDED_TO_STAGE, addedToStageHandler);
            
            var size:Number = _cellSize;
            var h:Number = stage.stageHeight;
            var w:Number = stage.stageWidth;
            
            var rows:int = Math.floor(h / size);
            var cols:int = Math.floor(w / size);
            
            var director:GridDirector = new GridDirector(size, cols, rows);
            director.fillColor = 0xffffff;
            director.lineColor = 0xccccff;
            
            var builder:GridBuilder = new GridBuilder();
            var grid:Grid = director.buildGrid(builder);
            addChild(grid);
            _grid = grid;
            
            //grid.addEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
            stage.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
            addChild(_start = new Pointer( size * 0.4, 0xffffff));
            _start.x = size * 0.5;
            _start.y = size * 0.5;
            _start.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);

            addChild(_end = new Pointer( size * 0.4, 0x0));
            _end.x = size * 0.5 + size * (cols - 1);
            _end.y = size * 0.5 + size * (rows - 1);
            _end.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
            _end.addEventListener(MouseEvent.MOUSE_MOVE, redrawe)
            _astarGrid = new AStarGrid(cols, rows);
            _astar = new AStar();
            findPath();
            redraw();
        }
        public function redrawe(e:MouseEvent):void{
            trace("s")
            _end.x = (Math.floor(mouseX / _cellSize) + .5) * _cellSize;
            _end.y = (Math.floor(mouseY / _cellSize) + .5) * _cellSize;
        }

        private function findPath():void
        {
            var s:Number = _cellSize;
            _astarGrid.setStartnode(Math.floor(_start.x / s), Math.floor(_start.y / s));
            _astarGrid.setEndNode(Math.floor(_end.x / s), Math.floor(_end.y / s));
            
            var path:Array;
            var len:int, i:int;
            var node:AStarNode;
            var c:GridCell;
            _astar.findPath(_astarGrid)
        }
        private function redraw():void {
            _grid.reset();
            drawUnWalkables();
            if (_astar.path) {
                drawPath(_astar.path);
            }
        }
        private function drawUnWalkables():void {
            var i:int, j:int;
            var n:AStarNode;
            var c:GridCell;
            var rows:int = Math.floor( stage.stageHeight/ _cellSize);
            var cols:int = Math.floor( stage.stageWidth / _cellSize);
            for (i = 0; i < rows; i++) {
                for (j = 0; j < cols; j++) {
                    n = _astarGrid.getNode(j, i);
                    if (!n.walkable) {
                        c = _grid.getCell(j, i);
                        c.fillColor = 0x0;
                    }
                }
            }
        }
        private function drawPath(path:Array):void {
            var len:int = path.length;
            var i:int = 0;
            var c:GridCell;
            var node:AStarNode
            while (node = path[i++] as AStarNode) {
                c = _grid.getCell(node.x, node.y);
                c.fillColor = 0xff0000;
            }
            
        }
        private function mouseDownHandler(e:MouseEvent):void 
        {
            var sprite:Pointer= e.target as Pointer;
            if (sprite) {
                stage.addEventListener(MouseEvent.MOUSE_MOVE, 
                    function(ev:MouseEvent):void {
                        if (ev.buttonDown) {
                            sprite.x = mouseX;
                            sprite.y = mouseY;
                        }else {
                            sprite.x = (Math.floor(mouseX / _cellSize) + .5) * _cellSize;
                            sprite.y = (Math.floor(mouseY / _cellSize) + .5) * _cellSize;
                            stage.removeEventListener(ev.type, arguments.callee);
                            findPath();
                            redraw();
                        }
                    } );
            }
            
            var cell:GridCell = e.target as GridCell;
            trace(cell);
            var buffer:Vector.<GridCell>;
            if (cell) {
                buffer = new Vector.<GridCell>();
                stage.addEventListener(MouseEvent.MOUSE_MOVE, function(ev:MouseEvent):void {
                    var c:GridCell;
                    var n:AStarNode;
                    if (ev.buttonDown) {
                        c = ev.target as GridCell;
                        if (c) {
                            if (buffer.indexOf(c) > -1) {
                                
                            }else {
                                buffer.push(c);
                                n = _astarGrid.getNode(Math.floor(c.x / _cellSize), Math.floor(c.y / _cellSize));
                                _astarGrid.setWalkable(Math.floor(c.x / _cellSize), Math.floor(c.y / _cellSize), !n.walkable);
                                redraw();
                            }
                        }
                    } else {

                        stage.removeEventListener(ev.type, arguments.callee);
                    }                        findPath();
                        redraw();
                });
            }
            
        }
        
        private function mouseMoveHandler(e:MouseEvent):void 
        {
            var cell:GridCell = e.target as GridCell;
            cell.grid.setChildIndex(cell, cell.grid.numChildren - 1);
            if (cell) {
                cell.filters = [new GlowFilter()];
                cell.addEventListener(MouseEvent.MOUSE_OUT, function(e:MouseEvent):void {
                    var c:GridCell = e.target as GridCell;
                    if (c) {
                        c.filters = [];
                        c.removeEventListener(e.type, arguments.callee);
                    }
                });
                
                var c:uint;
                var _x:int, _y:int;
                var n:AStarNode;
                if (e.buttonDown) {
                    _x = Math.floor(mouseX / _cellSize);
                    _y = Math.floor(mouseY / _cellSize);
                    n = _astarGrid.getNode(_x, _y);
                    _astarGrid.setWalkable(_x, _y, !n.walkable);
                }
            }
        }
        
    }
}


import flash.display.Graphics;
import flash.display.Sprite;
import flash.events.Event;
class Pointer extends Sprite{
    private var _radisu:Number;
    private var _color:uint;
    public function Pointer(radius:Number, color:uint = 0xff0000) {
        _radisu = radius;
        _color = color;
        _draw();
    }
    private function _draw():void {
        var g:Graphics = graphics;
        g.lineStyle(1, 0x0);
        g.beginFill(_color);
        g.drawCircle(0, 0, _radisu);
        g.endFill();
    }
}
class GridDirector {
    private var _cellSize:Number = 15;
    private var _fillColor:uint = 0x0;
    private var _lineColor:uint = 0x333333;
    private var _rows:uint;
    private var _cols:uint;
    public function GridDirector(size:Number, cols:uint, rows:uint) {
        _cellSize = size;
        _rows = rows;
        _cols = cols;
    }
    public function buildGrid(builder:GridBuilder):Grid {
        builder.makeTiles(_cols, _rows, _cellSize);
        builder.drawCells(fillColor, lineColor);
        return builder.getGrid();
    }
    
    public function get fillColor():uint { return _fillColor; }
    public function set fillColor(value:uint):void 
    {
        _fillColor = value;
    }
    
    public function get lineColor():uint { return _lineColor; }
    public function set lineColor(value:uint):void 
    {
        _lineColor = value;
    }
    
    public function get cellSize():Number { return _cellSize; }
    public function set cellSize(value:Number):void 
    {
        _cellSize = value;
    }
    
    public function get rows():uint { return _rows; }
    public function set rows(value:uint):void 
    {
        _rows = value;
    }
    
    public function get cols():uint { return _cols; }
    public function set cols(value:uint):void 
    {
        _cols = value;
    }
}
class GridBuilder {
    private var _grid:Grid;
    public function GridBuilder() {
    }
    public function getGrid():Grid {
        return _grid;
    }
    public function makeTiles(cols:uint, rows:uint, size:Number):void {
        _grid = new Grid(cols, rows, size);
        _grid.tileCells();
    }
    public function drawCells(fillColor:uint, lineColor:uint):void {
        _grid.fillColor = fillColor;
        _grid.lineColor = lineColor;
        //trace(fillColor.toString(16), lineColor.toString(16));
        _grid.reset();
    }
}
class Grid extends Sprite{
    private var _size:Number;
    private var _numRows:int;
    private var _numCols:int;
    private var _cells:Vector.<GridCell>;
    private var _fillColor:uint = 0x0000cc;
    private var _lineColor:uint = 0x333333;
    public function Grid(cols:int, rows:int, size:Number) {
        _size = size;
        _numCols = cols;
        _numRows = rows;
    }
    public function tileCells():void {
        var i:int, j:int;
        var cell:GridCell;
        _cells = new Vector.<GridCell>();
        for ( i = 0; i < _numRows; i++) {
            for (j = 0; j < _numCols; j++) {
                cell = new GridCell(this);
                cell.x = j * _size;
                cell.y = i * _size;
                addChild(cell);
                _cells.push(cell);
            }
        }
    }
    public function reset():void {
        _draw();
    }
    private function _draw():void {
        var c:GridCell;
        for (var i:int = 0; i < _cells.length; i++) {
            c = _cells[i] as GridCell;
            c.draw(_fillColor, _lineColor);
        }
    }
    public function getCell(x:int, y:int):GridCell {
        var c:GridCell;
        c = _cells[y * _numCols + x];
        return c;
    }
    public function get size():Number { return _size; }
    public function set size(value:Number):void 
    {
        _size = value;
    }
    
    public function get fillColor():uint { return _fillColor; }
    public function set fillColor(value:uint):void 
    {
        _fillColor = value;
    }
        
    public function get lineColor():uint { return _lineColor; }
    public function set lineColor(value:uint):void 
    {
        _lineColor = value;
    }
}
class GridCell extends Sprite{
    private var _grid:Grid;
    private var _row:int;
    private var _fcolor:uint;
    private var _lcolor:uint;
    public function GridCell(grid:Grid) {
        super();
        _grid = grid;
    }
    public function draw(fcolor:uint, lcolor:uint):void {
        _fcolor = fcolor;
        _lcolor = lcolor;
        _redraw();
    }
    private function _redraw():void
    {
        graphics.clear();
        var g:Graphics = this.graphics;
        var s:Number = _grid.size;
        g.lineStyle(1, _lcolor, 1);
        g.beginFill(_fcolor, 1);
        g.drawRect(0,0, s, s);
        g.endFill();
    }
    public function get size():Number {
        return _grid.size;
    }
    
    public function get row():int { return _row; }
    public function get fillColor():uint { return _fcolor; }
    public function set fillColor(value:uint):void {
        _fcolor = value;
        _redraw();
    }
    public function get lineColor():uint {
        return _lcolor;
    }
    public function set lineColor(value:uint):void {
        _lcolor = value;
        _redraw();
    }
    public function get grid():Grid { return _grid; }
}
class AStar {
    private var _open:Array;
    private var _closed:Array;
    private var _grid:AStarGrid;
    private var _endNode:AStarNode;
    private var _startNode:AStarNode;
    private var _path:Array;
    private var _huristic:Function = euclidian;
    private var _straightCost:Number = 1.0;
    private var _diagCost:Number = Math.SQRT2;
    public function AStar() {
        
    }
    
    /**
     * 与えられたGridからパスを見つける
     * @param    grid
     * @return
     */
    public function findPath(grid:AStarGrid):Boolean {
        _grid = grid;
        _startNode = grid.startNode;
        _endNode = grid.endNode;
        
        _startNode.g = 0;
        _startNode.h = _huristic(_startNode);
        _startNode.f = _startNode.g + _startNode.h;
        
                var ret:Boolean = search();
                if(!ret){
                    _path = [];
                }
        return ret;
    }
    
    private function search():Boolean
    {
        var node:AStarNode = _startNode;
        _open = [];
        _closed = [];
        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);
            
            var i:int, j:int;
            var test:AStarNode ;
            for (i = startX; i <= endX; i++) {
                for (j = startY; j <= endY; j++) {
                    test = _grid.getNode(i, j);
                    
                    if (test == node || !test.walkable) continue;
                    
                    //コストを計算
                    var cost:Number = _straightCost;
                    if (!((node.x == test.x) || (node.y == test.y))) {
                        cost = _diagCost;
                    }
                    var g:Number = node.g + cost;
                    var h:Number = _huristic(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 {
                        //Openリストに追加
                        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 AStarNode;
        }
        
        buildPath();
        return true;
    }
    
    private function buildPath():void
    {
        _path = [];
        
        var node:AStarNode = _endNode;
        _path.push(node);
        while (node != _startNode) {
            node = node.parent;
            _path.unshift(node);
        }
    }
    public function get openList():Array {
        return _open;
    }
    public function get closedList():Array {
        return _closed;
    }
    public function get path():Array {
        return _path;
    }
    private function isClosed(node:AStarNode):Boolean
    {
        var i:int, len:int = _closed.length;
        for (i = 0; i < len; i++) {
            if (_closed[i] == node) {
                return true;
            }
        }
        return false;
    }
    
    private function isOpen(node:AStarNode):Boolean
    {
        var i:int, len:int = _open.length;
        for (i = 0; i < len; i++) {
            if (_open[i] == node) {
                return true;
            }
        }
        return false;
        
    }
    private function manhattan(node:AStarNode):Number {
        return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
    }
    private function euclidian(node:AStarNode):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:AStarNode):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 AStarGrid {
    private var _startNode:AStarNode;
    private var _endNode:AStarNode;
    private var _nodes:Array;
    private var _numCols:int;
    private var _numRows:int;
    
    public function AStarGrid (numCols:int, numRows:int) {
        _numCols = numCols;
        _numRows = numRows;
        _nodes = [];
        
        var i:int, j:int;
        for (i = 0; i < _numCols; i++) {
            _nodes[i] = [];
            for (j = 0; j < _numRows; j++) {
                _nodes[i][j] = new AStarNode(i, j);
            }
        }
    }
    public function getNode(x:int, y:int):AStarNode {
        return _nodes[x][y] as AStarNode;
    }
    public function setEndNode(x:int, y:int):void {
        _endNode = _nodes[x][y] as AStarNode;
    }
    public function setStartnode(x:int, y:int):void {
        _startNode = _nodes[x][y] as AStarNode;
    }
    public function setWalkable(x:int, y:int, value:Boolean):void {
        var n:AStarNode = _nodes[x][y] as AStarNode;
        n.walkable = value;
    }
    
    public function get startNode():AStarNode { return _startNode; }
    public function get endNode():AStarNode { return _endNode; }
    public function get numCols():int { return _numCols; }
    public function get numRows():int { return _numRows; }
    
}

class AStarNode {
    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:AStarNode;
    public function AStarNode(x:int, y:int) {
        this.x = x;
        this.y = y;
    }
}