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