KUNISAN.JPブログコメント書き込み

Twitterのタイムラインを見ていると、時折自動生成された迷路の画像が出てくることがあります。以前から「これができるとゲーム作りの幅が広がる」とは思っていたのですが、あまり深く調べることはありませんでした。しかし先日、ふと頭の中に迷路生成のアルゴリズムのようなものが浮かびました。「せっかくなので形にしてみよう」ということで、プログラムにしてみたところ、うまく動いてくれました。

迷路生成のルールはこんな感じです。
1)1本目の通路を生成開始。基本は通路が行き止まりになるまで迷路の生成を続ける(ただしランダムで終了あり)。
2)座標をランダムに取って、既に通路があるところであれば、そこから分岐した通路を生成開始。基本は通路が行き止まりになるまで迷路の生成を続ける(ただしランダムで終了あり)。
3)画面上に新たに通路を生成できなくなるまで2)を繰り返す。

自分では「我流のアイデア」と思っていたこの迷路作成のアルゴリズムは、「穴掘り法」という名前で既に存在していました。いずれにしても、思った通りに迷路を自動生成するプログラムができて嬉しく思いました。

以下、穴掘り法のプログラムと迷路自動生成の動画です。



これをきっかけに、ネットで迷路の自動生成について調べていると、「棒倒し法」がより簡単に実装できて一般的であることがわかりました。せっかくなので、自分でも作ってみることにしました。

棒倒し法のルールはこんな感じです。
1)フィールド上に1マス置きに「棒(壁)」を設置する。ただし、画面の端のマスは上下左右とも空白であること。
2)一番上の棒からスタート、ランダムに上下左右のいずれかに倒す形で、倒した所のマスも壁として埋めていく。ただし、既に壁として埋まっているところには棒は倒せない。
3)上から2番目以降の棒も随時倒していくが、これ以降は下と左右のみ倒せる(上には倒せない)。既に壁として埋まっているところには棒は倒せない。

以下、棒倒し法のプログラムと迷路自動生成の動画です。



棒倒し法の方が圧倒的に短くシンプルなプログラムにはなりますが、迷路に短い分岐が多くなってしまうのと、スタートとゴールを設置した際に、解法が「一旦上に向かって、その後に下に降りていく」というワンパターンな感じになってしまいます。個人的には穴掘り法の方が好みです。

一方、穴掘り法については迷路の規模が大きくなると描画に時間がかかってしまうことと、「長くくねくね」とした感じの通路になりがちということがあります。

ついでに、「迷路を自動的に解く」プログラムも作ってみることにしました。以下のようなルールで迷路を解いていきます。
1)スタート地点から進行できる方向に行ける所まで進めていく。
2)行き止まりになったら、逆に戻るようにして分岐の手前までを塗りつぶして、次にここに辿り着かないようにする。
3)2)を繰り返しながら行き止まりをつぶしていくうちに、ゴールまでの道のりがあぶり出されていく。

以下、迷路を自動的に解くプログラム(一部)と動画です。この動画の迷路の生成は棒倒し法ですが、もちろん穴掘り法でもこのプログラムは適用できます。



穴掘り法、壁倒し法以外に、「壁伸ばし法」という方法もメジャーなようです。今のところ試してはないですが、また時間のある時にプログラムを作ってみようと思います。

プチコン4関連記事(リンク一覧): プチリバーシ - プチコン4でシンプルなオセロ風ゲーム / プチエアホッケー - プチコン4でシンプルなエアホッケーゲーム / ムカデ四匹対戦ゲーム - プチコン4でCOM対戦型ゲーム / 慣性シューティング イネルシア - プチコン4でエクセリオン風ゲーム / フルーツ好きのアルパカさん - プチコン4で物理演算系ジャンプアクションゲーム / ...(記事連続表示)

100 迷路 本 Mazes Book: 本 迷路 大人のための迷路パズルブック男の子と女の子大人のアクティビティブックゲーム迷路簡単に難しい迷路ブック大人 をAmazon.co.jpでチェック