幅優先探索(BFS)
迷路生成（穴掘り法）
http://wonderfl.net/code/c753aea9f78f70c78522bda1546912b15568436d
深さ優先探索(DFS)
http://wonderfl.net/code/2fe2b7feed97268aa569ab138932603ec82d047d
/**
* Copyright matsu4512 ( http://wonderfl.net/user/matsu4512 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6PCb
*/
/*
迷路生成（穴掘り法）
http://wonderfl.net/code/c753aea9f78f70c78522bda1546912b15568436d
深さ優先探索(DFS)
http://wonderfl.net/code/2fe2b7feed97268aa569ab138932603ec82d047d
*/
package {
import caurina.transitions.Tweener;
import flash.display.Shape;
import flash.display.Sprite;
/*
幅優先探索によって迷路のスタートからゴールまでの最短経路を求める。
*/
[SWF(width=500, height=500, backgroundColor=0x000000)]
public class BFS extends Sprite
{
//フィールドの情報を格納する配列。１は道、０は壁。
private var field:Array;
//フィールドのサイズ
private var fsize:int = 31;
//マスの数
private var size:int = fsize*fsize;
//道を伸ばす方向, 東西南北の順
private var dir_ary:Array = [-fsize, 1, fsize, -1];
//辿った道を記録しておく配列
private var trace_ary:Array = [];
//一マスのサイズ
private var mass_size:Number;
//可視化のために通った道を全て記録しておく配列
private var route_records:Array = [];
private var ball:Sprite = new Sprite();
//隣接行列
private var ad_mat:Array = [];
//一度訪れた場所を記録しておく配列
private var visited:Array = [];
//探索に必要なQueue
private var queue:Array = [];
private var startNode:int, endNode:int;
public function BFS()
{
mass_size = 500 / fsize;
create_maze();
for(var i:int = 0; i < size; i++){
if(field[i]) draw(i);
}
startBfs();
ball.graphics.beginFill(0x0000ff);
ball.graphics.drawRect(0, 0, mass_size, mass_size);
ball.graphics.endFill();
ball.x = 0;
ball.y = 0;
addChild(ball);
draw(startNode, 0xfff000);
draw(endNode, 0x00ff00);
//可視化の開始
visualize(0);
}
//隣接行列の生成
private function create_ad_mat():void{
var len:int = field.length;
while(len--) ad_mat[len] = [];
for(var i:int = 0; i < fsize; i++){
for(var j:int = 0; j < fsize; j++){
var p:int = i*fsize+j;
ad_mat[p][p] = 0;
if(i == 0 || j == 0 || i == fsize-1 || j == fsize-1) continue;
if(field[p]){
if(field[p+1]) ad_mat[p][p+1] = ad_mat[p+1][p] = 1;
else ad_mat[p][p+1] = ad_mat[p+1][p] = 0;
if(field[p-1]) ad_mat[p][p-1] = ad_mat[p-1][p] = 1;
else ad_mat[p][p-1] = ad_mat[p-1][p] = 0;
if(field[p+fsize]) ad_mat[p][p+fsize] = ad_mat[p+fsize][p] = 1;
else ad_mat[p][p+fsize] = ad_mat[p+fsize][p] = 0;
if(field[p-fsize]) ad_mat[p][p-fsize] = ad_mat[p-fsize][p] = 1;
else ad_mat[p][p-fsize] = ad_mat[p-fsize][p] = 0;
}
}
}
}
private function startBfs():void{
create_ad_mat();
for(var i:int = 0; i < size; i++)
if(field[i]) startNode = i;
for(i = size-1; i > 0; i--)
if(field[i]) endNode = i;
for (i = 0; i < size; i++ ) visited[ i ] = false;
queue.push(new Node(startNode, null));
visited[startNode] = true;
bfs();
}
//幅優先探索でゴール地点を探索
private function bfs():void{
var cur_node:Node;
while(1){
cur_node = queue.pop() as Node;
for(var i:int = 0; i < size; i++){
if(ad_mat[cur_node.pos][i] && !visited[i]){
visited[i] = true;
route_records.push(i);
queue.unshift(new Node(i, cur_node));
if(i == endNode) return;
}
}
}
}
private function create_maze():void{
//迷路のフィールドのサイズを20*20で確保 ＆ 初期化
//まずは外枠以外全て壁にする。
field = [];
for(var i:int = 0; i < fsize; i++){
for(var j:int = 0; j < fsize; j++){
if(i == 0 || i == fsize-1 || j%fsize == 0 || (j+1)%fsize == 0){
field[i*fsize+j] = 1;
}
else field[i*fsize+j] = 0;
}
}
//１～(fsize-2)の間の奇数な乱数を生成。
var odd_x:int = Math.random() * int((fsize-2)/2+1) * 2 + 1;
var odd_y:int = Math.random() * int((fsize-2)/2+1) * 2 + 1;
//fieldに対応した値に直して渡す。
create_path(odd_y*fsize + odd_x);
//外枠を壁にする
for(i = 0; i < fsize; i++){
for(j = 0; j < fsize; j++){
if(i == 0 || i == fsize-1 || j%fsize == 0 || (j+1)%fsize == 0) field[i*fsize+j] = 0;
}
}
}
//指定された地点から道を作る関数
private function create_path(pos:int):void{
var dir_ary2:Array = dir_ary.slice(0, 4);
for(var i:int = 4; i > 0; i--){
//道を伸ばす方向をランダムに決める
var dir:int = int(Math.random()*i);
//指定した方向の２マス先まで調べる
for(var j:int = 0; j < 2; j++){
if(field[pos + dir_ary2[dir]*(j+1)]) break;
}
if(j == 2) break;
dir_ary2.splice(dir, 1);
}
//どちらも壁ならば、その２マスを道にする。
if(j == 2){
field[pos + dir_ary2[dir]] = field[pos + dir_ary2[dir]*2] = 1;
pos += dir_ary2[dir];
//移動する
pos += dir_ary2[dir];
//通った道の記録
trace_ary.push(pos);
//新たに道を作る
create_path(pos);
}
//道が作れなかったら、一つ前に戻る。
else{
//初期位置に戻ってきたら終了
if(trace_ary.length == 1) return;
create_path(trace_ary.pop());
}
}
private function draw(pos:int, c:uint=0xffffff):void{
var rect:Shape = new Shape();
rect.graphics.beginFill(c);
rect.graphics.drawRect(0, 0, mass_size, mass_size);
rect.graphics.endFill();
rect.x = pos%fsize*mass_size;
rect.y = int(pos/fsize)*mass_size;
addChild(rect);
}
//route_recordsに記録されている道順にオブジェクトを移動させる
private function visualize(i:int):void{
Tweener.addTween(ball, {x:route_records[i]%fsize*mass_size, y:int(route_records[i]/fsize)*mass_size, time:0.01,
onComplete:function():void{
draw(route_records[i], 0xff0000);
if(i == route_records.length-2){
var node:Node = queue.shift().pre_node;
while(node.pre_node != null){
draw(node.pos, 0x000fff);
node = node.pre_node;
}
return;
}
visualize(i+1);
}
});
}
}
}
class Node{
public var pos:int;
public var pre_node:Node;
public function Node(pos:int, pre_node:Node){
this.pos = pos;
this.pre_node = pre_node;
}
}