A* Path Finding

...
@author Motoki Matsumoto

forked:1
favorite:11
lines:521
license : MIT License
modified : 2009-10-15 02:20:09

Embed: Tweet

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);
			
			_astarGrid = new AStarGrid(cols, rows);
			_astar = new AStar();
			findPath();
			redraw();
		}
		
		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 {
						findPath();
						redraw();
						stage.removeEventListener(ev.type, arguments.callee);
					}
				});
			}
			
		}
		
		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;
	}
}

Code Fullscreen

Preview Fullscreen

vtstarin

kimo0517

FlashFit

halfmile

tkinjo

raa

eternity_hir..

TmskSt

178ep3

zproxy

teageek

sort

pv744

forked from: A* Path Finding

Yukulele

forked:2
favorite:2
lines:520 (diff:6)