迷路の自動生成 - 大人になってからの再学習

海外のサイト「krazydad」の「迷路」のコーナーがすごい。

■ Printable Mazes for Kids | krazydad
http://krazydad.com/mazes/

Easy, Intermediate, Challenging, Tough, Super Tough とレベル分けされていて、
こども向けという位置づけながら、Super Toughレベルは大人でも十分楽しめる。

次のものは、Super Tough レベルの迷路の一例。

このような迷路が1つのPDFファイルに20個収録されていて、それぞれのレベルごとに50ファイルある。
つまり、レベルごとに1000個、全部で6000個の迷路があることになる！（これにプラスして輪郭が動物の形をした迷路が1700個ある。）
これらはすべて無料でダウンロードできる。

迷路の本によくある、飾りはなく、シンプルに迷路を解くだけ。
ひたすら迷路を解きたい人にはいいかも。

よく見ると、複数種類のパターンに基づいて、プログラムで自動生成しているように見える。
さすがに全部の迷路を人手で作ることはできないだろう。

迷路生成については、壁を伸ばしていく方法、穴を伸ばしていく方法など、複数のアルゴリズムがある。

■迷路自動生成アルゴリズム
 http://www5d.biglobe.ne.jp/%257Estssk/maze/make.html

迷路の自動生成について、一般的には次のように考えることができる。
(1) 迷路の壁の基準となる格子パターンを最初に作る（例えば、正方形を敷き詰めた方眼紙のようなパターン、正六角形を敷き詰めたハニカムパターン）
(2) 格子パターンと双対なグラフを作る
(3) このグラフに対して、極大木（spanning tree）を生成する。これが迷路の経路になる。
(4) 最初の格子パターンで、迷路の経路を横切らない辺を迷路の壁とする。

もう少し高度な話として、何かの形に見える迷路を自動生成する研究論文も存在する。
例えば、下の迷路はコンピュータによって自動生成されたものだ。