プチコンで遊ぼう! (はてなブログ版)

任天堂3DSのプチコンで遊ぼう! [twitter:@eida_s]

はてなダイアリーから移行しました。 はてなダイアリーのURLを開いても自動的にこちらにリダイレクトされますのでご了承ください。

再帰的アルゴリズムで迷路をつくる

ツイッター再帰アルゴリズムで迷路を作る画像が流れてきてエモい感じだったので早速つくってみました。

プログラム名: MAZE
公開キー: NKQE345D
公開日: 2018/12/12
バージョン: 0.01

元にしたのは以下のページです。
Buckblog: A Better Recursive Division Algorithm
ソースはよくわからなかったため、動画をもとに「こうなってるんだろう」という勝手な推測のもとにつくりましたw
なので領域のとり方のところとかが少しちがいます。

もともと再帰的な領域分割アルゴリズムはあって、それをもうちょっとそれらしくした、というのが「A Better Recursive Division Algorithm」ということのようです。
そのざっくりとした考え方を以下に示します。
(元ネタのページの番号とは対応していません。)

着目している領域を適当に2つの領域に分割し、その領域同士の境界にカベを立て、立てたカベのうち1か所に穴を開けます。
それをさらに小さい領域にどんどん適用していくと迷路になる、というものです。
以下では、着目している領域を黄色、2つに分割した領域の1つを赤、もう1つを緑と表現します。

(0) 領域全体を黄色に塗ります。
(1) 黄色に塗られた領域の2つのマスを適当(ランダム)にとり、1つを赤、もう1つを緑の初期点とします。
    この時、黄色の領域が1マスかしかなく、赤と緑の両方の初期点を置けない場合は再帰終了で、もとの処理に戻ります。
(2) 赤と緑の領域を1マスずつ交互にかつ適当(ランダム)に広げていきます。
    この時、塗ることができるのは黄色のマスだけで、他方の色に塗られたマスを塗ることはできません。
    塗るマスがなくなるまで(2)を繰り返します。
    赤と緑のどちらかが先にもう塗るマスがなくなっても、他方にまだ塗ることができる箇所があれば(2)を繰り返します。
(3) 赤と緑の境界にカベを作ります。
(4) (3)でつくったカベのどこか1か所、カベを消去します。
(5) 赤だった領域を黄色に塗って、(1)からの処理を再帰的に実行します。
(6) 緑だった領域を黄色に塗って、(1)からの処理を再帰的に実行します。

これで処理は終了です。

(2)のランダムに領域を広げていくところのやり方を変えると、形が変わってきます。
今回自分が作ったプログラムでは、作るのが簡単、という理由でランダムウォークにしましたが、この場合、細くて短い通路ができやすいため、十字路ができやすいように思います。(これはあまり自分の好みでないです。)
ここを元ネタのページのように初期位置から均等に近く広がっていくようにするといい感じになりそうな気がしますので、その気がありましたら改良してみてください。

以上です。