迷路のアルゴリズム

2000.5.26 by R. Saito

ある日迷路はどうやって作るのであろうか? と思いました。気になると変な物で、アルゴリズムを考えないとどうも納得しません。

以下に私の(たぶん普通の)アルゴリズムを示します。何かのおやくに立てば幸です。

このアルゴリズムは、2 次元の迷路で、壁も通路も四角形(コマ)で表現されています。コマが空白になれば通路、そのままなら壁です。(2n+1)x(2m+1) の奇数個のコマが長方形に並んだもの A_ij (i=1,..,2n+1, j=1,..,2m+1) を考えます。

このとき、A_ij で i と j がともに奇数の場合のところは全て壁とします。また、 i と j がともに偶数の場合のコマは最終的に全て空白となります。(こうしないと、壁がうまくつながりません。9x9 の下の例をご覧下さい。) ですから手で迷路を書く場合には、(1) まず全てを壁にして、(2) 次に、i と j がともに偶数の場合のコマを全て空白にします。(1 個おきに縦横空白が並びます。)、 (3) 迷路はその空白と空白の間を適当に除くことによって作ることができます。

■■■■■■■■■　　　　 ■■■■■■■■■　　　　 ┏　┳━━━━━┓
■□■□■□■□■　　　　 ■□■□□□□□■　　　　 ┃　┃　　　　　┃
■■■■■■■■■　　　　 ■□■□■□■□■　　　　 ┃　┃　┃　┃　┃
■□■□■□■□■　　　　 ■□□□■□■□■　　　　 ┃　　　┃　┃　┃
■■■■■■■■■　→→　 ■■■■■□■■■　→→　 ┣━━━┛　┗━┫
■□■□■□■□■　　　　 ■□□□□□□□■　　　　 ┃　　　　　　　┃
■■■■■■■■■　　　　 ■■■□■■■■■　　　　 ┣━━　━━━━┫
■□■□■□■□■　　　　 ■□□□□□□□■　　　　 ┃　　　　　　　┃
■■■■■■■■■　　　　 ■■■■■■■■■　　　　 ┗━━━━━━　┛

以下プログラムをつくる場合の手順(アルゴリズム)を示します。

(壁の設定)一番外側のコマは、壁としてそのまま使います。その方がプログラムを使う場合簡単に記述できます。また最初は全てのコマが埋まっているとします。

■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■

(穴ほり)出発点☆から穴をほっていきます。いく方向は乱数で決めます。のランダムに穴ほりしながら進むのは、 i と j がともに偶数の場合の近接する 2 点の間で穴をほっていきます。
穴をほる条件は、行く先がすでにほられていないことです。したがって穴ほりで戻ることはできません。このランダムに歩く作業は、あるコマでどの方向にも行けなくなった時に終了します。
```
■■■■■■■■■
■☆■□□□■■■
■□■■■□■■■
■□□□□□■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
■■■■■■■■■
```
(次の出発点の選択) しかしこれでは、全てのところの穴を開けたわけではないので、次に枝道を作ります。すでにほってあるコマのうち i と j がともに偶数のコマの中で、そのコマを出発点として掘り出すことのできる方向が 1 つ以上あるコマ★を全て選びます。そのなかから次の出発点☆を乱数で選びます。そして、(穴ほり)に戻って再び掘り進めます。ここで注意したいのは、次の穴ほりの作業で、前に選ばれた★の候補がいく方向がなくなって候補でなくなることがあるということです。(例: 下の図の一番左の★)
```
■■■■■■■■■　　　　■■■■■■■■■ 
■□■□□★■■■　　　　■□■□□★■■■ 
■□■■■□■■■　　　　■□■■■□■■■ 
■★□☆□★■■■　　　　■□□□□☆■■■ 
■■■■■■■■■　→→　■■■□■■■■■ 
■■■■■■■■■　　　　■□■★■■■■■ 
■■■■■■■■■　　　　■□■□■■■■■ 
■■■■■■■■■　　　　■□□★■■■■■ 
■■■■■■■■■　　　　■■■■■■■■■ 
```
i と j がともに偶数のコマの空白がなくなったら全て終了します。こうすれば、長方形の全ての空間を、通路の作る一つの空間 (閉曲線で囲まれた空間)で埋め作ることができます。できたパターンから始点と終点を、 i と j がともに偶数のコマの中から、任意に選ぶことができます(外壁に穴を開けても ok )。始点と終点を結ぶ線は 1 通りしかできません。

迷路の中で、複数のゴールを見せかけに作り、どちらが本当のゴールかわからない構造を作ることもできます。この時は、空白の空間は複数の閉曲線で囲まれた空間の集まりで、長方形を埋め尽くします。この時は、複数のゴールからの迷路を順番に、穴ほりをしていけば ok です。出発点についたゴールが正しいゴールになります。

JIS コードの中には├ ┬ ┤ などの罫線の記号がありますから、これを壁のつながりに併せて書けばより本格的な迷路にすることができます。Visual 系プログラム言語を使えば、迷路の途中にいろいろな仕掛けを設定することも可能です。

3 次元迷路は、2 次元の 4 方向を 6 方向に変えることができます。ただし、上に行ったりしたに行ったりするのを少し抑制したい場合には乱数の重みを変えます。蜂の巣格子の迷路、n 次元迷路も同様です。答えの線を結んで絵をつくりたい場合には、最初の乱数で進むのを手作業で行い、残りをアルゴリズムで行うようにします。

C++ Builder で作ったプログラムもおいておきました。

rsaito@ee.uec.ac.jp