電電高専生日記

迷路の経路探索プログラムを作成しました

2015/07/19 00:22

卒研に関することで最近、迷路の経路探索をするプログラムを考え、作ることになりました。
自分は情報系学科の学生ではないのでアルゴリズムなどに詳しくなく、結構苦労しましたが、なんとか完成しました。
卒研ではC++で書きましたが、JavaScriptで書き直してこのブログで動作させてみます。

デモ

グレーが壁、白が通路となります。クリックで反転します。

↓x(0~8) →y(0~8)

START-X: START-Y:
 GOAL-X:  GOAL-Y:



x-y座標でそれぞれのブロックに座標がつけられています。横方向がxで、左端から0~8。縦方向がyで、上端から0~8。
スタートとゴールの位置は通路(白い部分)を指定してください。座標は0番から始まることに注意してください。

探索プログラム

関数の再帰処理で解いてます。
①現在地x座標、②現在地y座標、③各ブロックの既に通ったかの情報(9×9の二次元配列)、④ここまでの経路(配列)、この4つを引数としてます。隣のブロック(上下左右)が通路であり、まだ通っていないのなら、そのブロックへ移り再帰処理です。ゴールに着くか、移動できる隣のブロックが無くなった場合は再帰呼び出しはされません。
ソースを以下に示します。

function search(px, py, _passedBlock, _path){
		var passedBlock=[];
		for (var i=0; i<_passedBlock.length; i++){
			passedBlock[i]=[];
			for (var j=0; j<_passedBlock[i].length; j++){
				passedBlock[i][j]=_passedBlock[i][j];
			}
		}
		var path=[];
		for (var i=0; i<_path.length; i++){
			path[i]=_path[i];
		}
		passedBlock[py][px]=1; //現在地を通ったものとする。
		path.push({x:px, y:py}); //ここまでの経路に現在地を追加する
		
		if (px==GOAL_X && py==GOAL_Y){ //ゴールに着いたとき
			//テキストエリアに出力 ここは省略
			return;
		}
	
		if (py>0 && !block[py-1][px] && !passedBlock[py-1][px]){
			var _passedBlock=passedBlock;
			var _path=path;
			search(px,py-1,_passedBlock,_path); //上のブロックへ
		}
		if (HEIGHT-1>py && !block[py+1][px] && !passedBlock[py+1][px]){
			var _passedBlock=passedBlock;
			var _path=path;
			search(px,py+1,_passedBlock,_path); //下のブロックへ
		}
		if (px>0 && !block[py][px-1] && !passedBlock[py][px-1]){
			var _passedBlock=passedBlock;
			var _path=path;
			search(px-1,py,_passedBlock,_path); //左のブロックへ
		}
		if (WIDTH-1>px && !block[py][px+1] && !passedBlock[py][px+1]){
			var _passedBlock=passedBlock;
			var _path=path;
			search(px+1,py,_passedBlock,_path); //右のブロックへ
		}
}

最初に呼び出すときは、値が全て0のサイズ9×9の二次元配列と、サイズ0の配列を、それぞれ_passedBlockと_pathに当てて実引数として渡します。
ところでなぜsearch関数内でpassedBlockとpathを作り直しているかというと、仮引数をそのまま使うと、実引数を参照してしまうからです。(多分、原因は配列だからだと思う)。それだと何故困るかというと、経路が複数ある場合、おかしなことになってしまうからです。たとえば、2つ目の経路の探索中、1つ目の経路で通ったからといって既にゴールのブロックは通ったものとして扱われてしまいます。それを防ぐため、passedBlockとpathは作り直して、実引数の値を参照しないようにしています。そこが一番悩みました。

  • このエントリーをはてなブックマークに追加

最新記事

コメント(0)





プロフィール

名前:elkosendiary

性別:男

生年:1995年


2011年4月 高専入学
2016年3月 高専卒業
2016年4月 大学編入学
2018年3月 大学卒業予定

にほんブログ村 大学生日記ブログ 理系大学生へ
にほんブログ村

カテゴリ
Adsense
月別アーカイブ
ブログ内検索

アクセス

昨日のPV数:
全期間PV数:

おすすめ記事

「高専大学編入ログ」を作成しました

自作ゲーム「Defend PortMoresby!」バージョン3

【改良版】 RaspberryPiで作ったカメラ付き戦車ラジコン