迷路の自動生成アルゴリズム

シェアする

  • このエントリーをはてなブックマークに追加

こんにちは。

最近、Unityで迷路ゲームを制作しており、その様子をブログ記事に書いています。

そのゲームの中で、迷路フィールドをランダムに自動生成しています。

そのアルゴリズムと利点・欠点について書いてみます。

迷路の基本構造

もともと、迷路はテキストファイルから生成しようと考えていました。

AtCoder Beginner Contest 007 C: 幅優先探索のようなテキストを想定していました。

具体的には、下図のようなファイルです。

#######
#S....#
#.###.#
#...#.#
###.###
#....G#
#######

'#'が壁で、'.'が道、'S'がスタートで'G'がゴールです。

しかし、テキスト読み込みにするとWebGLでうまく動かなかったので、自動生成にしました(WebGLでもちゃんと動かす方法はあると思います)。

迷路の自動生成アルゴリズムは様々な種類があります。

参考にしたのは、将棋ソフト「やねうら王」の作者としても知られるやねうらおさんの下記ページです。

古くて新しい自動迷路生成アルゴリズム

この中で触れられている「クラスタリングによる迷路作成」を採用しました。

http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html

この手法にした理由は、迷路が単調にならず、実装が分かりやすいからです。

では、実装方法について書いていきます。

迷路生成アルゴリズム

まず全体のイメージを書きます。

最小全域木を得るためのクラスカル法をイメージすると分かりやすいと思います。

まず、下図のような辺の無いグラフ(点の集まり)を考えます。

例として、迷路のサイズを3×3にしています。

まだ張られていない辺(点線)が12本あります。これらを「辺リスト」に追加します

辺リストからランダムに1本選び、その辺を張ることでループができなければ、その辺を張ります。

選んだ辺を(張っても張らなくても)辺リストから削除します。

この作業を、辺の数が"点の数-1"(ここでは9-1=8)になるまで続けます。

例えば、7本の辺を張り終えたときに、辺が下図の黒実線ようになったとします。

このとき、上側の黒い点線は、張るとループができる辺なので、選んでも張らずに捨てます。

したがって、最後に張られる辺は下側の赤い点線のいずれかになります。

ここで下側の真ん中の辺を選ぶと、冒頭のテキストファイルと同じ迷路が完成します。

ループができるということは、選んだ辺の始点と終点を結ぶ経路がすでに存在するということです。すなわち、始点と終点がすでに同じ連結成分に所属するということです。

したがって、連結成分を保持しておき、辺を張るたびに連結成分を更新していけば、ループ判定が可能になります。

そのために用いるのがUnion-Find木です。

詳しくはUnion-Find木と、それを用いたクラスカル法についてググってください。

上図(辺を7本張った後の図)では、上側の6つの点が同じグループに所属し、下側の3つの点が同じグループに所属しています。黒点線は両端が同じグループになる辺です。

以上が迷路生成の概要です。

具体的には、まず下図のようなフィールドを作成します。

黒斜線の部分は、外壁と柱で、絶対に無くなりません。

赤斜線の部分は、迷路生成時に壊すことがある壁です。これが「まだ張られていない辺」に相当します。

数字が書いてあるのは通常の床(通路)です。この数字をUnion-Find木で使います。

赤ブロックの座標を全て「壁リスト」に入れ、ランダム選択・Union-Find木によるループ判定・壁壊し(ループが発生しない場合のみ)・Union-Find木でunite処理・壁をリストから破棄、を繰り返します。

最後に、左上と右下の床をスタートとゴールにして、迷路の完成です。

利点・欠点

利点

フィールド全体を等しくランダムに扱うので、フィールドに偏りが生まれません。(穴掘り法や棒倒し法は対称性がありません)

そのため、迷路が単調になりません。

また、クラスカル法を知っていれば実装が分かりやすいです。

欠点

ゴールからも分かれ道が発生することがあり、迷路としては無駄な部分が生じます。

上図の迷路で、ゴール(ピンクの位置)の上方に通路がありますが、この部分は迷路に全く必要が無い部分なので、実質フィールドが狭くなってしまっています。

「ゴールの隣の壁は片方しか壊さない」という処理があると良いかもしれません。

また、たまにすごく単純な迷路ができてしまいます。

スタートから1通りしかない道を辿れば、すぐにゴールが目視できます。難易度ゼロです。

これについては、スタートからゴールまで外壁沿いの経路でたどり着ける場合(下→右ルートと右→下ルートの2つのみ)は例外として迷路生成をやり直す処理があると良いかもしれません。

以上が迷路生成のアルゴリズムです。

迷路生成には、他にも棒倒し法や穴掘り法などがあるので、興味のある方はぜひ調べてみて下さい。では。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする