forked from: AStar
/**
* Copyright fakestar0826 ( http://wonderfl.net/user/fakestar0826 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/uc8U
*/
// forked from fakestar0826's AStar
package {
import flash.events.Event;
import flash.events.MouseEvent;
import flash.display.StageScaleMode;
import flash.display.StageAlign;
import flash.display.Sprite;
[SWF(backgroundColor = 0xFFFFFF)]
public class Pathfinding extends Sprite
{
private var _grid:Grid;
private var _gridView:GridView;
public function Pathfinding()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
_grid = new Grid(50, 30);
_grid.setStartNode(0, 2);
_grid.setEndNode(48, 27);
_gridView = new GridView(_grid);
_gridView.x = 20;
_gridView.y = 20;
addChild(_gridView);
}
}
}
import flash.events.MouseEvent;
import flash.display.Sprite;
class Grid
{
private var _startNode:Node;
private var _endNode:Node;
private var _nodes:Array;
private var _numCols:int;
private var _numRows:int;
public function Grid(numCols:int, numRows:int)
{
_numCols = numCols;
_numRows = numRows;
_nodes = new Array();
for(var i:int = 0;i < _numCols;i++)
{
_nodes[i] = new Array();
for(var j:int = 0;j < numRows;j++)
{
_nodes[i][j] = new Node(i, j);
}
}
}
public function getNode(x:int, y:int):Node
{
return _nodes[x][y] as Node;
}
public function setEndNode(x:int, y:int):void
{
_endNode = _nodes[x][y] as Node;
}
public function setStartNode(x:int, y:int):void
{
_startNode = _nodes[x][y] as Node;
}
public function setWalkable(x:int, y:int, value:Boolean):void
{
_nodes[x][y].walkable = value;
}
public function get endNode():Node
{
return _endNode;
}
public function get numCols():int
{
return _numCols;
}
public function get numRows():int
{
return _numRows;
}
public function get startNode():Node
{
return _startNode;
}
}
class Node
{
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:Node;
public var costMultiplier:Number = 1.0;
public function Node(x:int, y:int)
{
this.x = x;
this.y = y;
}
}
class AStar
{
private var _open:Array;
private var _closed:Array;
private var _grid:Grid;
private var _endNode:Node;
private var _startNode:Node;
private var _path:Array;
// private var _heuristic:Function = manhattan;
private var _heuristic:Function = euclidian;
// private var _heuristic:Function = diagonal;
private var _straightCost:Number = 1.0;
private var _diagCost:Number = Math.SQRT2;
public function AStar()
{
}
public function findPath(grid:Grid):Boolean
{
_grid = grid;
_open = new Array();
_closed = new Array();
_startNode = _grid.startNode;
_endNode = _grid.endNode;
_startNode.g = 0;
_startNode.h = _heuristic(_startNode);
_startNode.f = _startNode.g + _startNode.h;
return search();
}
public function search():Boolean
{
var node:Node = _startNode;
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);
for (var i:int = startX; i <= endX; i++)
{
for (var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
// if (test == node || !test.walkable) continue;
if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}
var cost:Number = _straightCost;
if (!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
//var g:Number = node.g + cost;
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(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
{
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 Node;
}
buildPath();
return true;
}
private function buildPath():void
{
_path = new Array();
var node:Node = _endNode;
_path.push(node);
while (node != _startNode)
{
node = node.parent;
_path.unshift(node);
}
}
public function get path():Array
{
return _path;
}
private function isOpen(node:Node):Boolean
{
for (var i:int = 0; i < _open.length; i++)
{
if (_open[i] == node)
{
return true;
}
}
return false;
}
private function isClosed(node:Node):Boolean
{
for (var i:int = 0; i < _closed.length; i++)
{
if (_closed[i] == node)
{
return true;
}
}
return false;
}
private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost +
Math.abs(node.y + _endNode.y) * _straightCost;
}
private function euclidian(node:Node):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:Node):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 GridView extends Sprite
{
private var _cellSize:int = 10;
private var _grid:Grid;
/**
* コンストラクタ
*/
public function GridView(grid:Grid)
{
_grid = grid;
for (var i:int = 0; i < _grid.numCols; i++)
{
for (var j:int = 0; j < _grid.numRows; j++)
{
var mult:Number = Math.sin(i * 0.25) + Math.cos(j * 0.2 + i * 0.05);
_grid.getNode(i, j).costMultiplier = Math.abs(mult) + 1;
}
}
drawGrid();
findPath();
addEventListener(MouseEvent.CLICK, onGridClick);
}
/**
* 格子のマスをそれぞれのノードの状態に基づいて色づけして描画する。
*/
public function drawGrid():void
{
graphics.clear();
for (var i:int = 0; i < _grid.numCols; i++)
{
for (var j:int = 0; j < _grid.numRows; j++)
{
var node:Node = _grid.getNode(i, j);
graphics.lineStyle(0);
graphics.beginFill(getColor(node));
graphics.drawRect(i * _cellSize, j * _cellSize,
_cellSize, _cellSize);
}
}
}
/**
* ノードの状態に基づいて色を決める。
*/
private function getColor(node:Node):uint
{
if (!node.walkable) return 0;
if (node == _grid.startNode) return 0x666666;
if (node == _grid.endNode) return 0x666666;
var shade:Number = 300 - 70 * node.costMultiplier;
return shade << 16 | shade << 8 | shade;
}
/**
* GridViewへのクリックイベントを処理する。
* クリックされたマスを調べて、walkable状態を反転する。
*/
private function onGridClick(event:MouseEvent):void
{
var xpos:int = Math.floor(event.localX / _cellSize);
var ypos:int = Math.floor(event.localY / _cellSize);
_grid.setWalkable(xpos, ypos, !_grid.getNode(xpos, ypos).walkable);
drawGrid();
findPath();
}
/**
* AStarのインスタンスを生成して、経路探索に用いる。
*/
private function findPath():void
{
var astar:AStar = new AStar();
if (astar.findPath(_grid))
{
// showVisited(astar);
showPath(astar);
}
}
/**
* 訪問済みのノードをハイライト表示する。
*/
private function showVisited(astar:AStar):void
{
var visited:Array = astar.visited;
for (var i:int = 0; i < visited.length; i++)
{
graphics.beginFill(0xcccccc);
graphics.drawRect(visited[i].x * _cellSize, visited[i].y * _cellSize, _cellSize, _cellSize);
graphics.endFill();
}
}
/**
* 探索した経路をハイライト表示する。
*/
private function showPath(astar:AStar):void
{
var path:Array = astar.path;
for (var i:int = 0; i < path.length; i++)
{
graphics.lineStyle(0);
graphics.beginFill(0);
graphics.drawCircle(path[i].x * _cellSize + _cellSize / 2,
path[i].y * _cellSize + _cellSize / 2,
_cellSize / 3);
graphics.endFill();
}
}
}