迷路アルゴリズム3種であっさりダンジョン
定番迷路アルゴリズム
いかにもゲーム制作に使えそうな、定番の迷路アルゴリズム3種類をまとめてみます。
(迷路アルゴリズム御三家)
- 壁倒し法
- 穴掘り法
- 壁伸ばし法
ここでは、迷路の描画にOpenProcessingを利用します。
使い方に関しては、p5.jsをかじる本を参考にして頂けると幸いです。
壁倒し法
最初に紹介するのは最もシンプルな"壁倒し法"です。
この手法は、その名の通り"壁を倒す"アルゴリズムです。
壁倒し法
壁倒し法の手順は次の通りです。
- 迷路の周囲に外壁を作る
- 外壁より内部のスペースに"柱"を1マスおきに並べる
- 並べた"柱"それぞれを起点に"上下左右"いずれか1マスを"壁"とする
壁倒し法(途中まで)
完成コードを見てみましょう。(クリックで全コードを見る事ができます)
壁倒し法(完成コード)
具体的に迷路を作っている関数は、"createMaze()"です。
// 省略
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段目の柱からは下左右のみ
}
}
}
}
}
// 省略
完成した配列を元に壁、柱を描画する事で迷路は完成します。
こちらで動作確認をする事ができます。
穴掘り法
次に紹介するのは、穴掘り法です。
こちらは先ほどとは視点を変え、"通路"に焦点を当てたアルゴリズムです。
文字通り、"穴を掘る"手順で迷路を構築します。
穴掘り法
穴掘り法の手順は次の通りです。
- 全てのマスを壁で埋める
- 通路の開始位置を決める(行奇数,列奇数)
- 進行方向の4方向をシャッフルした配列を用意する
- シャッフルした進行方向それぞれに道を作る(進める所まで)
穴掘り法(途中まで)
完成コードを見てみましょう。(クリックで全コードを見る事ができます)
穴掘り法(完成コード)
具体的に通路を作っている関数は、"extendRoad()"です。
穴掘り法では、開始箇所を起点にして4方向に通路を作っていきます。
いずれかの外壁か、他の通路とぶつかる一歩手前まで通路を作り(穴を掘る)ます。
// 省略
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マス以外を道にする
- 壁を伸ばす起点(グリッドのrとcが共に奇数)箇所を洗い出す
- 起点をシャッフルする
- 起点が無くなるまで壁を伸ばしていく
壁伸ばし法(途中まで)
完成コードを見てみましょう。(クリックで全コードを見る事ができます)
壁伸ばし法(完成コード)
壁伸ばし法では、壁を止める判定が多少複雑になります。
特に、伸ばしている自身の壁に囲まれた場合は処理をやりなおします。
2歩先まで通路だった場合は壁を伸ばし、その後再帰処理で壁を伸ばします。
具体的な判定部分のコードは以下の通りです。
// 省略
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