A*（たぶんバグ持ち）
A*
クリックで別のパターン
時々最短じゃないルートが出てる気がする
黄がスタート
青がゴール
赤が求められたルート
紫がクローズリスト入りしているノード
緑がオープンリスト入りしているノード
灰色のでっかいのが、なんちゃって障害物
/**
* Copyright awef ( http://wonderfl.net/user/awef )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/zQxr
*/
package
{
//A*
//クリックで別のパターン
//時々最短じゃないルートが出てる気がする
//黄がスタート
//青がゴール
//赤が求められたルート
//紫がクローズリスト入りしているノード
//緑がオープンリスト入りしているノード
//灰色のでっかいのが、なんちゃって障害物
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.text.TextField;
public class main extends Sprite
{
private var disp:Sprite = new Sprite();
public function main()
{
addChild(disp);
run();
stage.addEventListener(MouseEvent.CLICK, function(e:MouseEvent):void {
removeChild(disp);
disp = new Sprite();
addChild(disp);
run();
} );
}
private function run():void
{
//障害物配置用
var barricade:Array;
//ノード格納用配列
var nodes:Array;
//スタート・ゴール
var start:node;
var goal:node;
//オープンリスト・クローズリスト
var oNode:Array;
var cNode:Array;
//A*アルゴリズムで使う
var current:Object;
//手順の可視化用
var nav:Sprite;
//ループ用
var tmp:*;
var tmp2:*;
var i:int;
var sp:Sprite;
//ランダムに障害物を配置
barricade = new Array();
for (i = 0; i < 3; i++)
{
sp = new Sprite();
sp.alpha = 0.1;
sp.graphics.beginFill(0x000000);
sp.graphics.drawCircle(0, 0, 50);
sp.graphics.endFill();
sp.x = Math.floor(Math.random() * stage.stageWidth);
sp.y = Math.floor(Math.random() * stage.stageHeight);
disp.addChild(sp);
barricade.push(sp);
}
nodes = new Array();
//ランダムにノードを散らす
for (i = 0; i < 90; i++ )
{
tmp = new node();
do
{
tmp.x = Math.floor(Math.random() * stage.stageWidth);
tmp.y = Math.floor(Math.random() * stage.stageHeight);
}while (barricade.some(function(item:*, index:int, array:Array):Boolean { return item.hitTestObject(tmp); } ))
nodes.push(tmp);
disp.addChild(tmp);
}
//近いノードと接続
for each(tmp in nodes)
{
for each(tmp2 in nodes)
if (tmp != tmp2 && 80 > tmp.dist(tmp2))
tmp.connect(tmp2, true);
}
//スタート、ゴールを決定
start = nodes[0];
tmp = 1;
do //スタートとゴールが別のノード、かつ近すぎないようにする
{
goal = nodes[tmp];
tmp++;
if (nodes.length <= tmp)
{
alert("スタート・ゴールの設定に失敗しました。クリックでリトライして下さい。");
return;
}
}
while (start == goal || 300 > start.dist(goal))
//オープンリスト、クローズリスト {node:node, cost:int, heuristic:int, score:int, parent:Object} ← こんなのを格納
oNode = new Array();
cNode = new Array();
oNode.push( {
"node" : start,
"cost" : 0,
"heuristic" : start.dist(goal),
"score" : start.dist(goal),
"parent" : new Object() //ダミー
} );
oNode[0].parent = oNode[0];
while (oNode.length > 0)
{
//オープンリストをスコアの低い順にソート
oNode.sortOn("score", Array.NUMERIC);
//最もスコアの低いノードをcurrentノードに設定
current = oNode[0];
if (current.node == goal) break;
else
{
//currentノードをクローズリストに移動
oNode.splice(0, 1);
cNode.push(current);
//currentノードの接続先を調査
for each(tmp in current.node.connection)
{
//オープンリストにもクローズリストにも登録されていない場合、オープンリストに追加
if (!oNode.some(function(item:Object, index:int, array:Array):Boolean { return (tmp == item.node); })
&& !cNode.some(function(item:Object, index:int, array:Array):Boolean { return (tmp == item.node); }))
{
oNode.push( {
"node" : tmp,
"cost" : current.cost + tmp.dist(current.node),
"heuristic" : tmp.dist(goal),
"score" : current.cost + tmp.dist(current.node) + tmp.dist(goal),
"parent" : current
} );
}
}
}
}
//手順可視化レイヤの追加
nav = new Sprite();
nav.alpha = 0.6;
disp.addChild(nav);
//スタート・ゴールの位置に着色
nav.graphics.beginFill(0xFFFF00);
nav.graphics.drawCircle(start.x, start.y, 6);
nav.graphics.endFill();
nav.graphics.beginFill(0x0000FF);
nav.graphics.drawCircle(goal.x, goal.y, 6);
nav.graphics.endFill();
//オープンリストを塗る
for each(tmp in oNode)
{
nav.graphics.lineStyle(2, 0x00FF00);
nav.graphics.drawCircle(tmp.node.x, tmp.node.y , 4);
}
//クローズリストを塗る
for each(tmp in cNode)
{
nav.graphics.lineStyle(2, 0xFF00FF);
nav.graphics.drawCircle(tmp.node.x, tmp.node.y , 4);
}
if (current.node == goal) //ルートが見つかった場合、ラインを引く
{
nav.graphics.lineStyle(2, 0xFF0000);
nav.graphics.moveTo(current.node.x, current.node.y);
tmp = current;
while (tmp.node != start)
{
nav.graphics.moveTo(tmp.node.x, tmp.node.y);
nav.graphics.lineTo(tmp.parent.node.x, tmp.parent.node.y);
nav.graphics.beginFill(0xFF0000);
nav.graphics.drawCircle(tmp.node.x, tmp.node.y, 4);
nav.graphics.endFill();
tmp = tmp.parent;
}
}
else //ルートが見つからなかった場合、
{
alert("ルートが見つかりませんでした。");
}
}
private function alert(msg:String):void
{
var tf:TextField = new TextField();
tf.text = msg;
tf.width = 465;
disp.addChild(tf);
}
}
}
import flash.display.Sprite
//ノード。単純に、ノードの位置と接続の関係のみを表す。
class node extends Sprite
{
public var connection:Array = new Array();
function node()
{
draw();
}
public function draw():void
{
graphics.clear();
graphics.beginFill(0x000000, 0.4);
graphics.drawCircle(0, 0, 4);
graphics.endFill();
for each(var tmp:node in connection)
{
graphics.lineStyle(1, 0, 0.1);
graphics.moveTo(0, 0);
graphics.lineTo(tmp.x - x, tmp.y - y);
}
}
//targetと接続
//hogehoge == trueの場合、双方向接続にする （引数の良い名前が思い浮かばなかった）
public function connect(target:node, hogehoge:Boolean = false):void
{
disConnect(target); //多重接続対策
connection.push(target);
if (hogehoge)
target.connect(this);
draw();
}
//targetと切断。多重接続も全部切ってくれるはず。（未検証）
public function disConnect(target:node):void
{
connection = connection.filter(function(item:node, index:int, array:Array):Boolean { return (target != item); } );
draw();
}
//ノード間の距離を測定する
public function dist(target:node):int
{
return Math.sqrt(Math.pow(x - target.x, 2) + Math.pow(y - target.y, 2));
}
}