先ず、縦横それぞれ奇数個サイズのマスを想定する。
左上を原点として、
偶数座標のマスが迷路の壁となり、奇数座標が迷路の通路として使用される。
最初に全てのマスを「壁」として初期化する。
以降の例では、■を壁、□を通路として表示する。
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
縦横それぞれ奇数座標のマスをランダムに選択する。
下図では、左上を原点(0,0)として右に3、下に3の地点を選択したものとする。
(「○」を現在の注目点を意味する)
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■○■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
次に穴を掘る方向をランダムに選択し、
その方向に2マス先のマスを調べて、まだ通路でなければ通路にして2マス分を
通路に変える。
以下の例では現在の注目点から下に通路を延ばそうして、下に2マス先を調べ
て、まだ通路になっていなかったので、下に2マス分延ばした状態である。
(同時に注目点も移動させる)
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■□■■■■■
■■■□■■■■■
■■■○■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
移動先の点で先ほどと同様に、次の方向をランダムに選択し、選択した方向の
2マス先の状態を調べ、通路でない場合にはそちらの方向に通路を延ばしてい
くという操作を繰り返す。
もし、ランダムに選択した方向の2マス先が通路であった場合は、通路を延ば
す作業はここで一旦終了する。
以下の図において、左に通路を延ばそうとした場合、左に2マス先は既に通路
になっているので、これ以上通路を延ばせない。
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■□■■■■■
■■■□■■■■■
■■■□■○■■■
■■■□■□■■■
■■■□□□■■■
■■■■■■■■■
通路を延ばせなくなった場合は、新たに
縦横それぞれ奇数座標のマスをランダムに選択し、そのマスを起点として通路
を延ばす作業を行なう。
以上の作業を、通路を延ばせるマスが無くなるまで繰り返す。
以下の図では、どの奇数座標点をとっても、通路を延ばすことができないので
終了である。
■■■■■■■■■
■□□□□□□□■
■□■■■■■□■
■□■□■□□□■
■□■□■■■□■
■□■□■□■□■
■□■□■□■□■
■□□□□□■□■
■■■■■■■■■
通路を延ばしていく際に延ばせる方向がある限り延ばしていき、
どの方向にも通路が延ばせなくなった場合には、これまで進んできた通路上で
一つ前の地点に戻って他の方向に通路が延ばせないかを調べていく。
上で説明したアルゴリズムの場合では、以下の状態で左に通路を延ばそうとして
延ばせなかった場合は、新たな起点から通路延ばすようになっていたが、
簡易アルゴリズムでは、他の方向を調べて通路を延ばせるようであれば、そち
らに通路を延ばしていく。
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■□■■■■■
■■■□■■■■■
■■■□■○■■■
■■■□■□■■■
■■■□□□■■■
■■■■■■■■■
※ 右と上にはまだ通路を延ばせる。
どちらの方向にも通路を延ばせなくなった場合は、これまで辿ってきた通路を
(2マスずつ)戻りながら通路を延ばせる方向がないかを探していく。
もし通路を延ばせるマスが見付かれば、そこから通路を延ばしていく。
この作業を繰り返していき、迷路作成を開始した最初のマスまで戻ってきたら
作業は終了である。
つまり、(意味的には)深さ優先探索で２次元平面上に通路を延ばしているわけ
であるが、
こうすることで、端から順に迷路が作られるようになり、深さ優先探索での
処理が完了した後には、通路を延ばすことが出来るマスが存在しないことが
保証できる。
ただし、このアルゴリズムでは通路上での枝分かれが発生しない単調な迷路に
なりがちであるため、迷路としては簡単なものになってしまう。