/**
* Copyright mtok ( http://wonderfl.net/user/mtok )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hOYq
*/
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;
}
}