こんばんは。きわさです。
プログラムで迷路を作成するためのアルゴリズムについてです。
今回は穴掘り法という方法で行っていきます。
穴掘り法
穴掘り法はその名の通り？穴を掘っていき迷路を作る方法です。
前提として、迷路の大きさは奇数x奇数である必要があります。
今回は説明用に9マスx9マスの画像を用意しました。
灰色は壁、迷路では通行不可のマスです。
つまり全てが通行不可ということです。
ここから通行可能な道を作っていくのです。
迷路作成の開始位置を決める
まず、開始位置を決めます。
どこでも良いわけではなく、ルールがあります。
縦横どちらも偶数のマスである必要があります。
この画像の黄色のマスのいずれかです。
ここから一つ選んで掘ってみます。
白のマスが掘ったところ、つまり通行可能な道です。
2マス先が壁なら道を広げる
上下左右方向それぞれ2マス先が壁かどうかチェックします。
開始位置に着目すると、左方向には2マス先はないですね。
上下右は2マス先は壁、つまり掘り進めることができます。
この3方向のうち1方向を選び道を広げます。
今回は右を選びます。
右に進みました。
そして次はこの位置で再度上下左右をチェックします。
左方向2マス先は、来た道のため、壁ではありません。
上下右はまた壁ですね。
次は上を選びます。
上に進みました。
今回は上はマスがなく、下は道なので、進めるのは左右のみです。
次は左に進みます。
行き止まりになったら戻る
進んだ位置で上下左右をチェックすると、
上と左はマスがなく、下と右は2マス先は道です。
こうなったらこの方向は終了です。
一つ前に戻ります。
まだ右が残っているので右に進みます。
このように上下左右の2マス先をチェックし、壁なら進み、
行き止まりになったら戻り、別方向に進む。
これを最後まで繰り返していくのが穴掘り法です。
最後まで掘り進めてみます。
完成
完成ですね。
見て気づいたかもしれませんが、
穴掘り法にはいくつか特徴があります。
それは、
・一番外側は必ず壁になる
・すべての道は必ず繋がっている
・分かれ道はそれぞれ決して合流しない
ということです。
また、ここまでわかると、
迷路の大きさが奇数x奇数であることや
開始位置が縦横偶数の位置でなければいけないこともわかりますね。
以上が穴掘り法のアルゴリズムです。