PathResolver A*
/**
* Copyright snamura ( http://wonderfl.net/user/snamura )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/nGLv
*/
// forked from snamura's PathResolver base
package
{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.Dictionary;
import flash.utils.setTimeout;
[SWF(width="465",height="465",frameRate="24",backgroundColor="#ffffff")]
public class PathResolveBase extends Sprite
{
private var _text:TextField;
// 経路計算テスト用マップのための配列
// とりあえず正方形のみ
// 0 = 通路
// 1 = スタート地点
// 2 = ゴール地点
// 8 = 壁
private var map:Array = [
1, 8, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 8, 0, 0,
0, 8, 0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 0, 0,
0, 8, 0, 8, 0, 0, 8, 0, 8, 8, 8, 8, 8, 8, 8, 0,
0, 8, 0, 8, 0, 8, 8, 0, 0, 8, 0, 0, 0, 0, 0, 0,
0, 0, 0, 8, 0, 0, 8, 8, 0, 8, 0, 8, 8, 8, 8, 8,
8, 8, 8, 8, 0, 0, 8, 0, 0, 8, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 8, 0, 0, 8, 0, 8, 8, 8, 8, 8, 0,
0, 0, 0, 8, 8, 0, 0, 8, 0, 0, 8, 0, 0, 8, 0, 0,
0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 8,
8, 8, 0, 8, 8, 8, 0, 0, 8, 8, 8, 0, 8, 8, 8, 0,
0, 0, 0, 0, 0, 8, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0,
0, 0, 0, 8, 0, 8, 0, 0, 8, 0, 8, 8, 8, 0, 8, 8,
8, 8, 8, 0, 0, 8, 0, 8, 8, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 8, 8, 0, 0, 8, 0,
0, 0, 8, 8, 0, 0, 8, 0, 0, 0, 8, 0, 8, 8, 8, 0,
0, 0, 0, 0, 0, 0, 8, 0, 8, 0, 0, 0, 0, 0, 8, 2
];
// フィールドの大きさ（1辺のノード数）
private var fieldLength:int;
// スタート地点
private var start:Node;
// ゴール地点
private var goal:Node;
// ノード配列
private var nodes:Array = [
];
public function PathResolveBase()
{
initNodes();
drawPath();
}
/**
* 初期ノードを構成します。
*/
private function initNodes():void
{
trace("initNode");
// 正方形を前提としてノードの幅を取得
fieldLength = Math.sqrt(map.length);
for (var x:int = 0; x < fieldLength; x++)
{
for (var y:int = 0; y < fieldLength; y++)
{
// ノードの配列番号を取得
var index:int = x + y * fieldLength;
// ノードの種類を取得
var type:int = map[index];
var node:Node = new Node(index, x, y, true);
if (type == 8)
{
// 壁タイプ
node.walkable = false;
node.draw(0x333333);
}
else
{
// 通行可能タイプ
if (type == 1)
{
// スタート地点
start = node;
node.draw(0xcc6666);
}
else if (type == 2)
{
// ゴール地点
goal = node;
node.draw(0x66cc66);
}
else
{
node.draw(0xffffff);
}
}
nodes[index] = node;
addChild(node);
}
}
}
/**
* 最短経路を取得し、経路を色づけします。
*/
private function drawPath():void
{
var path:Array = resolvePath();
for (var i:int = 0; i < path.length; i++)
{
var node:Node = path[i];
setTimeout(node.draw, i * 100, 0xcc9999);
}
}
/**
* スタート地点からゴール地点までの最短経路を計算し、
* 経路となるノードの配列を返却します。
*/
private function resolvePath():Array
{
// 手動による計算。最短経路を求めるアルゴリズムに変更します。
var close:Dictionary = new Dictionary(true);
var open :Array = [];
var len:int = nodes.length;
// 全ノードのコストをリセット
for (var i:int = 0; i < len; i++)
{
var n:Node = nodes[i];
n.fcost = 0;
n.gcost = 0;
n.hcost = 0;
n.camefrom = null;
}
// 開始地点のコスト情報を更新
start.gcost = 0;
start.hcost = start.distance(goal);
start.fcost = start.hcost;
open.push(start);
while (open.length > 0)
{
// もっともコストの低いノードを取得
open.sortOn("fcost", Array.NUMERIC);
var x:Node = open.shift();
// ゴールに到達していれば完了
if (x == goal)
{
// ゴールから逆算して経路を構築
var route:Array = [];
var from:Node = goal.camefrom;
while (from != start && from != null)
{
route.unshift(from);
from = from.camefrom;
}
return route;
}
// クローズドリストへ追加
close[x] = true;
// 接続しているノードの一覧を取得
var neighbors:Array = [];
if (x.fieldX > 0)
neighbors.push(nodes[x.index-1]);
if (x.fieldX < fieldLength - 1)
neighbors.push(nodes[x.index+1]);
if (x.fieldY > 0)
neighbors.push(nodes[x.index-16]);
if (x.fieldY < fieldLength - 1)
neighbors.push(nodes[x.index+16]);
var nlen:int = neighbors.length;
for (var j:int = 0; j < nlen; j++)
{
var y:Node = neighbors[j];
// 壁は無視
if (!y.walkable || close[y] != null)
{
continue;
}
var tcost:int = x.gcost + 1;
var tbetter:Boolean = false;
var tadd:Boolean = false;
if (!open.indexOf(y) >= 0)
{
y.hcost = goal.distance(y);
tadd = true;
tbetter = true;
}
else if (tcost < y.gcost)
{
tbetter = true;
}
if (tbetter)
{
y.camefrom = x;
y.gcost = tcost;
y.fcost = tcost + y.hcost;
if (tadd)
open.push(y);
}
}
}
return null;
}
/**
* 指定位置のノードを取得します。
*/
private function getNode(x:int, y:int):Node
{
return nodes[x + y * fieldLength];
}
}
}
import flash.display.Sprite;
import flash.events.EventDispatcher;
// 経路探索のためのノードクラス
internal class Node extends Sprite {
// 配列インデクス
internal var index:int;
// ノードX座標
internal var fieldX:int;
// ノードY座標
internal var fieldY:int;
// 通行可能フラグ
internal var walkable:Boolean;
// A*用経路記録用変数
// このノードを通った時の推定最短距離
public var fcost:int;
// スタート地点からこのノードまでの最短距離
public var gcost:int;
// このノードからゴールまでの推定距離
public var hcost:int;
public var camefrom:Node;
public function Node(index:int, fieldX:int, fieldY:int, walkable:Boolean)
{
this.index = index;
this.fieldX = fieldX;
this.fieldY = fieldY;
this.walkable = walkable;
this.x = fieldX * 20 + 70;
this.y = fieldY * 20 + 70;
}
internal function draw(background:uint):void
{
graphics.clear();
graphics.lineStyle(1);
graphics.beginFill(background);
graphics.drawRect(0,0,20,20);
}
internal function distance(node:Node):int
{
return Math.abs(fieldX - node.fieldX) + Math.abs(fieldY - node.fieldY);
}
}