幅優先探索(BFS)

迷路生成（穴掘り法）
http://wonderfl.net/code/c753aea9f78f70c78522bda1546912b15568436d
深さ優先探索(DFS)
http://wonderfl.net/code/2fe2b7feed97268aa569ab138932603ec82d047d

matsu4512

forked:0
favorite:7
lines:159
license : MIT License
modified : 2010-01-10 13:54:15

Embed: Tweet

/*
 迷路生成（穴掘り法）
 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;
	}
}

Code Fullscreen

Preview Fullscreen

WinField95

Hio818214

yoshimax

TUNCAYS

clockmaker

vnflash :

SEARCH BFS

Good :