A* Path Finding ... @author Motoki Matsumoto mtok forked:1favorite:11lines:521license : 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 Math.floor Math.floor test test callee callee search search Math.abs Math.abs type type color color Boolean Boolean mouseY mouseY mouseX Math.min sort new page view favorite forked pv744 forked from: A* Path Finding Yukulele forked:2 favorite:2lines:520 (diff:6)