穴掘り法のアルゴリズム

実際に使っている奴を言葉で説明してみる。
前提として、1（壁）で埋め尽くされた二次配列なマップを想定している。壁の厚さがある迷路を考える。
0.現在地点(x,y)にスタート地点を設定する。（スタート地点＝現在地点は0（通路）にする）
1.現在地点(x,y)から、移動可能な方向を調べてリストにする。（(x+2,y)(x-2,y)(x,y-2)(x,y+2)の四箇所の座標を調べ、そこが壁であれば、移動可能と判定する）
2.移動可能な方向がなければ、3へ。1方向以上あれば、その中からランダムに選んで移動する（移動先と、移動先と現在地点の中間点を通路にする）。現在地点をpushして、それから現在地点に移動先を代入する。1に戻る。
3.pop可能かどうかを調べる。スタックが空ならば、4へ。空でなければ、現在地点にpopして出てきた結果を代入する。1に戻る。
4.迷路の完成。終了。

バリエーション

ゴール地点を作成する場合は、1を以下のように書き換える。
1.現在地点(x,y)が、ゴール地点と同じならば（それは行き止まりとみなして）3へ。そうでなければ現在地点(x,y)から、移動可能な方向を調べてリストにする。（(x+2,y)(x-2,y)(x,y-2)(x,y+2)の四箇所の座標を調べ、そこが壁であれば、移動可能と判定する）

アルゴリズムに含まれる若干の嘘について

このアルゴリズムでは、それ以上通路が掘れなくなった場合、直前の「新たな方向に掘り出せる分岐点」に戻ってそこからやり直すようになっている。しかし、本来の穴掘り法では、直前とは限っておらず、これまで通って来た「新たな方向に掘り出せる分岐点」全ての中から選んでやり直すようになっている。プログラムを本来のアルゴリズムに合わせるのは、不可能ではないが面倒臭いし、それに導入したからと言って人間の目から見て有意な差が生じる訳でもない。