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



プチコン4で迷路自動生成プログラム

名前: 小川 邦久 リンク: https://kunisan.jp 日付: 2021年5月16日
プチコン4で迷路自動生成プログラムTwitterのタイムラインを見ていると、時折自動生成された迷路の画像が出てくることがあります。以前から「これができるとゲーム作りの幅が広がる」とは思っていたのですが、あまり深く調べることはありませんでした。しかし先日、ふと頭の中に迷路生成のアルゴリズムのようなものが浮かびました。「せっかくなので形にしてみよう」ということで、プログラムにしてみたところ、うまく動いてくれました。

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

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

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



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

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

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



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

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

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

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



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





プチコン4関連記事(リンク一覧): ワンパクと三角 - プチコン4でシンプル「三角渡り」ゲーム / わなげ - プチコン4でシンプルな輪投げゲーム / 何の変哲もないシューティング - プチコン4で1980年代風のシンプルシューティング / 迷路を爆撃せよ - 自動生成した迷路を破壊するゲーム(プチコン4) / プチコン4で迷路自動生成プログラム / ...(記事連続表示)

関連カテゴリー: ニンテンドー関連記事, プチコン4関連記事


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


1)商品の宣伝、宗教や政治活動の勧誘など、本サイトの趣旨に合わない書き込みはご遠慮ください。
2)個人、団体への誹謗中傷や、差別的な発言、公序良俗に反する表現は禁止します。
3)本ブログへの書き込みによって何らかの問題が発生した場合、KUNISAN.JP管理者までご連絡いただければ、内容の修正、削除を行います(その他の責任については負いかねます)。
4)製作者サイドの都合により、予告無く書き込みの一部または全てが削除されることがあります。あらかじめご了承ください。
5)迷惑メールやコンピュータウィルス被害を防止するため、必要な場合以外にはメールアドレスを書き込まないことをお勧めします。

タイトル
お名前 (※必須)
Eメール
ホームページ

コメント (※必須)


画像ファイル(サイズ:10MB以下 形式:gif,jpeg,jpg,png)