[Rust] 自然に見える迷路の生成

Rust でやるゲーム開発アルゴリズムシリーズ、第4弾ぐらいでしょうか？
今回はプログラム的に迷路生成をします。

元々は、四分木による経路探索をテストするために考えたものですが、これはこれで独立した知見になりそうなので別記事にしました。

自然に見える迷路とは

何をもって自然な迷路というかは、人によると思いますが、ここでは次のような感じのものを指します。

ある程度迷路としての構造を持ちながらも、分岐やループを持ち、道幅をいくらか持つことによってエージェント同士がすれ違えるようにします。
また、壁の形状にノイズを加えて単調にならないようにしています。

総合的には、鍾乳洞のような天然の洞窟というほどは自然ぽくはありませんが、完全に人工的な環境というわけでもない、ほどほどに自然な迷路を目指します。

このような地形のプロシージャル生成については、様々な方法があります。
ここで紹介するのはごく一部で、目的に応じていろいろな組み合わせを検討する必要があるでしょう。

パーリンノイズの2値化

自然に見える環境の生成というコンテキストで真っ先に候補に挙がるのが、パーリンノイズです。
ある程度連続性を保ちながら、自然な乱雑さを導入することができるアルゴリズムで、様々なところで使われています。

基本的には乱数シードからスカラー場を生成するアルゴリズムと考えて良いです。
オクターブや Persistence というパラメータで滑らかさや詳細度を調整できます。
英語版のWikipedia が読めれば自前で実装するには十分でしょう(例によって日本語版は死んでいますが…)。

これを迷路の生成に応用する最も単純な方法は、パーリンノイズ場を閾値で2値化することです。
しかし、迷路の生成アルゴリズムとして使うには一つ大きな欠点があります。
それは、接続性が保証されないということです。

下図では、パーリンノイズで生成した地形のうち、接続されている「島」をラベリングで色分けしたものです。
ゲーム的には、接続されていない島はアクセスの手段がないので、存在している意味がありません。^[1]

まず、簡単に対策できる方法としては、ラベリングした島のうち最も大きいもの以外は壁で埋めてしまうということがあります。

しかし、この方法はマップがスケールすると無駄になる面積が増えてくるので望ましくありません。

他にもいろいろ試しはしたのですが、面積とメモリの有効活用と自然に見えることを両立するアルゴリズムはなかなか簡単にはできませんでした。
結果的に次に述べるアルゴリズムを採用しました。

Rooms アルゴリズム

便宜的に Rooms アルゴリズムと呼んでいますが、いくつかのアルゴリズムを組み合わせたものであり、 「Rooms」に由来する部分は最初のほうだけです。
ローグライクゲームの部屋と通路のランダム生成を参考にしています。

まずは、部屋の「種」をグリッド上に配置します。

次に、グリッド上の「種」を迷路生成アルゴリズムで接続します。
迷路生成そのものにもいろいろなアルゴリズムがありますが、ここでは中央からランダムに枝を伸ばしていく方法を取りました。
自然に見せるためループも許しています。

次に、「種」のうちいくつかの半径を拡張して、「小部屋」にします。
基地などを作る程度の広さを確保します。
通路として機能させるため、全ての「種」は拡張しません。

さらに、グリッドが人工的すぎるので、「種」の位置を少しランダムに振って多様性を出します。^[2]

最後に、パーリンノイズを加えて少し境界を乱雑にして完成です。
パーリンノイズを加える以上、接続していない島ができてしまう可能性は残りますので、最大面積の島だけを残す処理は必要です。

さらなる拡張のアイデア

ゲーム性にランダム性を追加するには、他にもいろいろなパラメータをパーリンノイズで振ることが考えられます。
例えば標高や資源の密度をパーリンノイズでバリエーションを増してやれば、戦略性に幅が出ます。
いずれにしても、迷路生成やパーリンノイズなどのアルゴリズムを組み合わせていろいろなことが実現できるのが面白いところで、ひょっとしたらゲームそのものより面白いかもしれません。

経路探索との組み合わせ

ひとたびアルゴリズムを実現してしまえば、簡単にスケールを拡張できるのが良いところです。
下の図では 512 x 512 ピクセルのグリッドで生成したマップで、経路探索のグラフを白い線で可視化しています。
様々なレベルの複雑度を持つ迷路の経路探索がこれで簡単にテストできるようになりました。

参考

Rooms アルゴリズムはこちらの Pull Requestで実装しています。

脚注

1. もちろん、環境を動的に改変可能なゲームにすれば、マインクラフトのように穴を掘って接続することも可能になり、それはそれで面白いゲームデザインになりえます。
   しかし、ここでは swarm-rs プロジェクトのための自律行動エージェントの経路探索のために作る迷路なので、できるだけ複雑な迷路を静的に生成するというのが要請です。

2. 最初から全空間にランダムに種をばら撒けばもっと自然に見えるのではないかと思いましたが、実際にやってみるとランダムな偏りが大きすぎて、マップの面積の有効活用という意味ではいまいちでした。
   また、ランダムすぎても「使い物にならない」マップが生成される確率が上がるので、ランダムであればよいというものでもありません。
   グリッドを原点として少しランダムさを加える方法は、空間をまんべんなく網羅しつつランダムさを含めることができ、サンプリング手法としても使われることがあります。