🔰

迷路アルゴリズム3種でかんたんダンジョン

2024/06/02に公開

定番迷路アルゴリズム

いかにもゲーム制作に使えそうな、定番の迷路アルゴリズム3種類をまとめてみます。
(迷路アルゴリズム御三家)

  1. 壁倒し法
  2. 穴掘り法
  3. 壁伸ばし法

ここでは、迷路の描画にOpenProcessingを利用します。
使い方に関しては、p5.jsをかじる本を参考にして頂けると幸いです。

壁倒し法

最初に紹介するのは最もシンプルな"壁倒し法"です。
この手法は、その名の通り"壁を倒す"アルゴリズムです。


壁倒し法

壁倒し法の手順は次の通りです。

  1. 迷路の周囲に外壁を作る
  2. 外壁より内部のスペースに"柱"を1マスおきに並べる
  3. 並べた"柱"それぞれを起点に"上下左右"いずれか1マスを"壁"とする


壁倒し法(途中まで)

完成コードを見てみましょう。(クリックで全コードを見る事ができます)

壁倒し法(完成コード)

具体的に迷路を作っている関数は、"createMaze()"です。

main.js(抜粋)
// 省略
function createMaze(){

	// 1, 迷路の周囲に外壁を作る
	for(let r=0; r<ROWS; r++){
		for(let c=0; c<COLS; c++){
			maze[r][c] = (r==0||c==0||r==ROWS-1||c==COLS-1)?M_WALL:M_ROAD;
		}
	}
	// 2, 外壁より内部のスペースに"柱"を1マスおきに並べる
	for(let r=0; r<ROWS; r++){
		for(let c=0; c<COLS; c++){
			if(maze[r][c] == M_WALL) continue;
			maze[r][c] = (r%2==0&&c%2==0)?M_PILLAR:M_ROAD;
		}
	}
	// 3, 並べた"柱"それぞれを起点に"上下左右"いずれか1マスを"壁"とする
	for(let r=2; r<ROWS; r++){
		for(let c=2; c<COLS; c++){
			if(maze[r][c] == M_PILLAR){
				if(r==2){
					setWall(r, c, true);// 1段目の柱からは上下左右に
				}else{
					setWall(r, c, false);// 2段目の柱からは下左右のみ
				}
			}
		}
	}
}
// 省略

完成した配列を元に壁、柱を描画する事で迷路は完成します。

こちらで動作確認をする事ができます。

穴掘り法

次に紹介するのは、穴掘り法です。
こちらは先ほどとは視点を変え、"通路"に焦点を当てたアルゴリズムです。
文字通り、"穴を掘る"手順で迷路を構築します。


穴掘り法

穴掘り法の手順は次の通りです。

  1. 全てのマスを壁で埋める
  2. 通路の開始位置を決める(行奇数,列奇数)
  3. 進行方向の4方向をシャッフルした配列を用意する
  4. シャッフルした進行方向それぞれに道を作る(進める所まで)


穴掘り法(途中まで)

完成コードを見てみましょう。(クリックで全コードを見る事ができます)

穴掘り法(完成コード)

具体的に通路を作っている関数は、"extendRoad()"です。
穴掘り法では、開始箇所を起点にして4方向に通路を作っていきます。
いずれかの外壁か、他の通路とぶつかる一歩手前まで通路を作り(穴を掘る)ます。

main.js(抜粋)
// 省略
function extendRoad(r, c){

	// 3, 進行方向4方向をシャッフルした配列を用意する
	const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
	for(let i=dirs.length-1; 0<i; i--){
		const tmp = dirs[i];
		const rdm = floor(random()*dirs.length);
		dirs[i] = dirs[rdm];
		dirs[rdm] = tmp;
	}

	// 4, シャッフルした進行方向それぞれに道を作る(進める所まで)
	for(let dir of dirs){
		const oR = dir[0];
		const oC = dir[1];
		if(r+oR<1 || ROWS-1<=r+oR) continue;        // 上下枠である場合
		if(c+oC<1 || COLS-1<=c+oC) continue;        // 左右枠である場合
		if(maze[r+oR][c+oC] == M_ROAD) continue;    // 1歩通路である場合
		if(maze[r+oR*2][c+oC*2] == M_ROAD) continue;// 2歩通路である場合
		maze[r+oR][c+oC]     = M_ROAD;   // 1歩道にする
		maze[r+oR*2][c+oC*2] = M_ROAD;   // 2歩道にする
		roads.push({r:r+oR,   c:c+oC});  // 道を記録する
		roads.push({r:r+oR*2, c:c+oC*2});// 道を記録する
		extendRoad(r+oR*2, c+oC*2);      // 再帰処理
	}
}
// 省略

完成した配列を元にし描画する事で迷路は完成します。

こちらで動作確認をする事ができます。

壁伸ばし法

最後は壁伸ばし法です。
こちらは穴掘り法に似ていて、"壁を伸ばす"手法で迷路を構築していきます。


壁伸ばし法

壁伸ばし法の手順は次の通りです。

  1. 外壁1マス以外を道にする
  2. 壁を伸ばす起点(グリッドのrとcが共に奇数)箇所を洗い出す
  3. 起点をシャッフルする
  4. 起点が無くなるまで壁を伸ばしていく


壁伸ばし法(途中まで)

完成コードを見てみましょう。(クリックで全コードを見る事ができます)

壁伸ばし法(完成コード)

壁伸ばし法では、壁を止める判定が多少複雑になります。
特に、伸ばしている自身の壁に囲まれた場合は処理をやりなおします。
2歩先まで通路だった場合は壁を伸ばし、その後再帰処理で壁を伸ばします。
具体的な判定部分のコードは以下の通りです。

main.js
// 省略
function extendWall(r, c, walls){

	if(isEnd(walls)) {// 自分の壁に囲まれている場合はやりなおす
		extendWall(walls[0].r, walls[0].c, []);
		return;
	}

	if(maze[r][c] == M_WALL) return;
	walls.push({r:r, c:c});

	const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
	// 要素が少ないのでlengthを使う
	for(let i=dirs.length-1; 0<i; i--){
		const tmp = dirs[i];
		const rdm = floor(random()*dirs.length);
		dirs[i] = dirs[rdm];
		dirs[rdm] = tmp;
	}

	for(let dir of dirs){
		const oR = dir[0];
		const oC = dir[1];
		if(isWall(r+oR*2, c+oC*2, walls)) continue;// 自分の壁である場合
		if(maze[r+oR][c+oC] != M_ROAD) continue;// 1歩通路でない場合
		if(maze[r+oR*2][c+oC*2] == M_ROAD){// 2歩通路である場合
			walls.push({r:r+oR, c:c+oC});
			extendWall(r+oR*2, c+oC*2, walls);// 2歩目から再帰処理
			return;
		}
		// 壁に接続する
		walls.push({r:r+oR, c:c+oC});
		for(let wall of walls) maze[wall.r][wall.c] = M_WALL;// 壁を確定させる
		drawWall(walls);// 壁を描画する
		return;
	}
}
// 省略

完成した配列を元に壁を描画する事で迷路は完成します。

こちらで動作確認をする事ができます。

最後に

以上、3つのアルゴリズムを紹介しました。
それぞれ実装方法が異なるものの、動かしながら比較すると特徴がわかるので面白いですよ。
是非試してみてくださいね。

今回は以上になります。
ここまで読んでいただき有難うございました。(ง๑•̀ω•́)ง✧

Discussion