迷路生成アルゴリズムの可視化
穴掘り法・棒倒し法・クラスカル法・ウィルソン法など 10 種類のアルゴリズムで、迷路ができていく様子をアニメーションで見られます。同じシードで作った迷路の行き止まりの数や正解の道の長さを比べられます。
- 壁
- 候補
- 作業中
- 注目しているマス・正解の道
- スタート
- ゴール
穴掘り法（再帰的バックトラック）: 再生を押すと迷路を作り始めます
- 行き止まり
- —
- 分かれ道
- —
- 正解の道
- —
同じシードでの比較
行を押すとそのアルゴリズムに切り替えます。部屋の数は 240。直進率は、通路が 2 方向にある部屋のうち、曲がらずに通り抜ける部屋の割合です。正解の道は左上から右下までのマスの数です。
| アルゴリズム | 手数 | 行き止まり | 分かれ道 | 直進率 | 正解の道 |
|---|---|---|---|---|---|
| 480 | 2310% | 21 | 43% | 152 | |
| 209 | 6728% | 59 | 54% | 92 | |
| 296 | 6828% | 58 | 49% | 88 | |
| 418 | 6326% | 56 | 31% | 100 | |
| 378 | 7431% | 66 | 40% | 64 | |
| 240 | 9238% | 73 | 41% | 72 | |
| 978 | 6226% | 55 | 46% | 76 | |
| 4460 | 6929% | 58 | 49% | 84 | |
| 240 | 6226% | 60 | 62% | 60 | |
| 240 | 6828% | 62 | 51% | 64 |
使い方
- アルゴリズムを選んで「再生」を押すと、迷路ができていく様子をアニメーションで見られます。
- 「新しい迷路」を押すと乱数のシードが変わり、すべてのアルゴリズムの迷路を作り直します。下の比較表には、同じシードで 10 種類のアルゴリズムが作った迷路の特徴が並びます。
- 迷路ができあがったら「正解の道を表示」で、左上のスタート（緑）から右下のゴール（赤）までの道を重ねて表示できます。
- 最後まで再生した後にアルゴリズムやシードを変えると、新しい迷路がすぐに表示されます。アルゴリズムを切り替えながら迷路の形の違いを見比べられます。
- 「1 手」は、通路を 1 か所掘る・壁を 1 か所立てる・1 歩歩くなど、アルゴリズムの 1 回の操作です。手数のスライダーで好きな場面に移動できます。
- キーボードでは Space で再生 / 一時停止、← → で 1 手戻る / 進む、Home で最初へ、End で最後へ移動します。
迷路のしくみ
- マス目の奇数番目の行と列が交わるマスを「部屋」、部屋と部屋の間のマスを通路か壁にします。どのアルゴリズムも、すべての部屋が 1 本の道でつながり、ループも行けない場所もない迷路（完全迷路）を作ります。そのため、どの 2 つの部屋の間にも道はちょうど 1 つです。
- 作り方は、すべて壁の状態から通路を「掘る」もの、部屋だけがある状態から壁を壊して「つなぐ」もの、何もない状態から「壁を立てる」ものの 3 つに分かれます。
- 色の「候補」はこれからつなぐ部屋（プリム法）、「作業中」は掘っている途中の道（穴掘り法・サイドワインダー法）、歩いている道（ウィルソン法）、延ばしている途中の壁（壁延ばし法）です。
- 部屋をつなぐ道は、部屋を点、通路を辺とみなすと全域木になります。迷路を作ることは、マス目のグラフからランダムな全域木を選ぶことと同じです。
アルゴリズムの特徴
| アルゴリズム | 作り方 | しくみ | できる迷路 |
|---|---|---|---|
| 穴掘り法（再帰的バックトラック） | 掘る | まだ掘っていない隣の部屋へ進めるだけ進み、行き詰まったら掘ってきた道を戻って別の方向を探す（深さ優先探索） | 長い一本道が多く、行き止まりが少ない。正解の道も長く曲がりくねる |
| 棒倒し法 | 壁を立てる | 等間隔に立てた柱（棒）を、上の行から順にランダムな方向へ 1 マス倒す。一番上の行の柱だけが上へ倒せ、すでに壁のある方向へは倒さない | 短い行き止まりが多い。一番上の行のほかは上へ倒さないので、上下に長い壁ができやすい |
| 壁延ばし法 | 壁を立てる | まだ壁でない柱の位置をランダムに選び、既存の壁にぶつかるまで壁を延ばす。延ばしている途中の自分の壁にはぶつからないようにし、行き詰まったら少し戻る | 壁が入り組み、ほどよく分かれ道と行き止まりがある |
| 領域分割法 | 壁を立てる | 広い領域を 1 枚の壁で 2 つに分け、壁に 1 か所だけ穴を開ける。分けた領域にも同じことを、幅か高さが 1 部屋になるまで繰り返す | 長い直線の壁で大きな部屋に区切られた、四角い構造が見える |
| クラスカル法 | つなぐ | 部屋と部屋の間の壁をランダムな順に調べ、両側の部屋がまだつながっていなければ壊す。つながりは Union-Find で管理する（最小全域木のアルゴリズム） | 短い行き止まりが多く、どこも同じような細かい模様になる |
| プリム法 | 掘る | 迷路に隣り合う部屋（候補）からランダムに 1 つ選び、迷路のどれか 1 部屋とつなぐ。新しく隣になった部屋を候補に加える | 最初の部屋から放射状に広がり、短い行き止まりがとても多い |
| ウィルソン法 | つなぐ | 迷路にない部屋からランダムに歩き、迷路にぶつかったら歩いた道を迷路に加える。歩いた道が自分と交わったら、その輪を消してから歩き続ける（ループ消去ランダムウォーク） | 偏りのない迷路（ありうるすべての迷路が同じ確率でできる） |
| アルダス・ブローダー法 | 掘る | ランダムに歩き回り、まだ掘っていない部屋に入ったときだけ、その部屋への道を掘る。すべての部屋を訪れたら終わり | 偏りのない迷路。ただし最後の部屋にたどり着くまでに長い時間がかかる |
| 二分木法 | 掘る | 部屋を 1 つずつ見て、上か左のどちらかにランダムに通路を掘る。隣の部屋を見ないので、とても速く、メモリもいらない | 上の行と左の列が端から端まで一直線。左上へ向かう斜めの偏りが強い |
| サイドワインダー法 | 掘る | 行ごとに左から横へ掘り進め、ランダムなところで区切る。区切った区間からランダムに 1 部屋選んで上へ掘る | 上の行が一直線。下から上へは素直に登れるが、横方向に長い通路ができやすい |
ウィルソン法とアルダス・ブローダー法は、ありうるすべての迷路を同じ確率で作ります（一様全域木）。ほかのアルゴリズムは作りやすい形に偏りがあり、その偏りが比較表の行き止まりの割合や正解の道の長さに表れます。