forked from: 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/wz2V
*/
// forked from awef's A*（たぶんバグ持ち）
package
{
//A*
//クリックで別のパターン
//時々最短じゃないルートが出てる気がする
//手順の再現をするようにした
//配色すげー見辛い
//バグは直してない
//黄丸がスタート
//赤丸がゴール
//赤線が求められたルート
//青囲いがオープンリスト入りしているノード
//オレンジ囲いがクローズドリスト入りしているノード
//灰色のでっかいのが、なんちゃって障害物
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.text.TextField;
import gs.TweenMax;
import gs.easing.*;
public class main extends Sprite
{
//全ての表示オブジェクトをここに突っ込んどく
private var disp:Sprite;
//障害物配置用
private var barricade:Array;
//ノード格納用配列
private var nodes:Array;
//スタート・ゴール
private var start:node;
private var goal:node;
//オープンリスト・クローズドリスト
private var oNode:Array;
private var cNode:Array;
//A*アルゴリズムで使う
private var current:Object;
//コードの大幅改変は面倒なので、共通のディレイで対応 ← 初めは大幅に書き換えるつもりだったので、変数のスコープが変わってる。
private var glbDelay:Number;
private const duration:Number = 0.1;
public function main()
{
addChild(disp = new Sprite());
run();
stage.addEventListener(MouseEvent.CLICK, function(e:MouseEvent):void {
removeChild(disp);
addChild(disp = new Sprite());
run();
} );
}
private function run():void
{
glbDelay = 0;
//ループ用
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 //スタートとゴールが別のノード、かつ近すぎないようにする
{
if (nodes.length <= tmp)
{
alert("スタート・ゴールの設定に失敗しました。クリックでリトライして下さい。");
return;
}
goal = nodes[tmp];
tmp++;
}
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];
//スタートの位置に着色
sp = new Sprite();
sp.graphics.beginFill(0xEDD400);
sp.graphics.drawCircle(0, 0, 8);
sp.graphics.endFill();
sp.x = start.x;
sp.y = start.y;
sp.scaleX = 0;
sp.scaleY = 0;
disp.addChild(sp);
TweenMax.to(sp, duration, { delay : delay, scaleX : 1, scaleY : 1, ease : Back.easeOut } );
//ゴールの位置に着色
sp = new Sprite();
sp.graphics.beginFill(0xCC0000);
sp.graphics.drawCircle(0, 0, 8);
sp.graphics.endFill();
sp.x = goal.x;
sp.y = goal.y;
sp.scaleX = 0;
sp.scaleY = 0;
disp.addChild(sp);
TweenMax.to(sp, duration, { delay : delay, scaleX : 1, scaleY : 1, ease : Back.easeOut } );
while (oNode.length > 0)
{
//オープンリストをスコアの低い順にソート
oNode.sortOn("score", Array.NUMERIC);
//最もスコアの低いノードをcurrentノードに設定
current = oNode[0];
if (current.node == goal) break;
else
{
//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
} );
//オープンリスト入りのマーカーを描写
sp = new Sprite();
sp.x = tmp.x;
sp.y = tmp.y;
sp.graphics.lineStyle(2, 0x729fcf);
sp.graphics.drawCircle(0, 0, 6);
sp.alpha = 0;
disp.addChild(sp);
TweenMax.to(sp, duration, { delay : delay, alpha : 1, ease : Back.easeOut } );
}
}
//currentノードをクローズドリストに移動
oNode.splice(0, 1);
cNode.push(current);
//クローズドリスト入りのマーカーを描写
sp = new Sprite();
sp.x = current.node.x;
sp.y = current.node.y;
sp.graphics.lineStyle(2, 0xf57900);
sp.graphics.drawCircle(0, 0, 9);
sp.alpha = 0;
disp.addChild(sp);
TweenMax.to(sp, duration, { delay : delay, alpha : 1, ease : Back.easeOut } );
}
}
if (current.node == goal) //ルートが見つかった場合、ラインを引く
{
tmp = current;
while (tmp.node != start)
{
sp = new Sprite();
sp.alpha = 0;
sp.graphics.lineStyle(2, 0xEF2929);
sp.graphics.moveTo(0, 0);
sp.graphics.lineTo(tmp.parent.node.x - tmp.node.x, tmp.parent.node.y - tmp.node.y);
sp.x = tmp.node.x;
sp.y = tmp.node.y;
sp.scaleX = 0;
sp.scaleY = 0;
disp.addChild(sp);
TweenMax.to(sp, duration, { delay : delay, alpha : 1, scaleX : 1, scaleY : 1, ease : Linear.easeNone } );
tmp = tmp.parent;
}
}
else //ルートが見つからなかった場合、
{
alert("ルートが見つかりませんでした。");
}
}
//ディレイいちいち足すの面倒だし、ゲッタにしといた
private function get delay():Number
{
glbDelay += duration;
return glbDelay;
}
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(0x2e3436, 0.4);
graphics.drawCircle(0, 0, 4);
graphics.endFill();
for each(var tmp:node in connection)
{
graphics.lineStyle(1, 0x2e3436, 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));
}
}