はじめまして。@chick307 です。自分が作った洞窟もぐりが openleap の優秀賞をいただくことができきました。洞窟もぐりはローグライクというジャンルのゲームで、毎プレイごとにダンジョンが変化するのが特徴です。その中で使われている、ダンジョンマップを生成するアルゴリズムを解説してみようと思います。

おおまかな流れ

乱暴に言えば『いくつか部屋を作って、それを通路でつなぐだけ』でマップはできます。しかし、何も考えずにそれをやろうとすると、部屋と部屋が重なってしまったり、通路をつなげる処理が複雑になるなどの問題点があり、難しくなってしまいます。

フロア全体をいくつかの矩形に分割してから、その矩形の中に部屋を作ることで、そういった問題点を回避することが可能です。部屋どうしが重なることはなくなり、通路も矩形の境界線を使って簡単に作れるようになります。

以下、『フロアを矩形に分割→部屋を作成→通路を作成→』という順番で解説していきます。

フロアの分割

はじめに、フロアを複数の矩形に分割します。二分割を繰り返したり、縦横を決まった数均等に分割するなど様々な方法があります。

洞窟もぐりでは均等に分割する方法を使っています。1つの部屋から伸びる通路が最高でも上下左右の4本だけなので、シンプルなマップになるのが特徴です。プログラムもシンプルになります。

部屋の作成

次に、作った矩形の中に1つずつ部屋を作ります。洞窟もぐりでは『部屋は矩形の1/3より大きくする』というルールを作って、極端に小さいマップができるのを防いでいます。

また、矩形の上端と左端の1マス、右端と下端の2マスは空けておく必要があります。このスペースがないと通路を作ったとき、マップが変になってしまうからです。

計算式は以下のようになります。「[A, B]」は「A 以上 B 以下の整数をランダムに選ぶ」という意味です。

• 部屋の幅 = [矩形の幅 / 3, 矩形の幅 - 3]
• 部屋の高さ = [矩形の高さ / 3, 矩形の高さ - 3]
• 部屋のX座標 = [矩形のX座標 + 1, 矩形のX座標 + 矩形の幅 - 部屋の幅 - 2]
• 部屋のY座標 = [矩形のY座標 + 1, 矩形のY座標 + 矩形の高さ - 部屋の高さ - 2]

通路の作成

部屋Xが入っている、矩形Xを部屋Xの親と呼ぶことにします。親どうしが隣接している部屋があるとき、その2部屋の間に通路を通すことができます。

1. 左右に隣接している部屋Aと部屋Bの間に通路をのばす場合を例にします。
   
2. まず部屋Aの右端から、通路にする場所をランダムに選びます。
   
3. その場所から矩形Aの右端(矩形Bの左端)まで通路を掘ります。
   
4. 同じように部屋Bからも、位置をランダムに選んで通路を掘ります。
   
5. 最後に間を掘れば部屋AB間の通路が完成します。
   
6. これを、すべての隣接する部屋どうしで行います。
   

通路の削除

このままだと、すべての部屋に2本以上の通路が伸びていて、行き止まりがありません。行き止まりになる部屋があると、さらにダンジョンらしくなるので、作った通路をいくつかランダムに削除します。

注意する点として、すべての部屋どうしを通路で繋げる必要があります。ローグライクゲームでは最低でも、最初にプレイヤーの配置される部屋と、出口のある部屋が繋がっていないと、クリアができません。

孤立した部屋をつくらないように通路を削除していきます。

1. すべての部屋に同じマークを付ける
2. 通路をランダムに選んで、削除する
3. 適当に選んだ部屋に新しいマークを付ける
4. その部屋から、通路でつながっている部屋に、同じマークを付けていく
5. 新しいマークが付いていない部屋が1つでもあれば、削除した通路をもとに戻す
6. 何回か手順2に戻る

マップの作成

部屋と通路の位置が決まってから、マップを作ります。ローグライクゲームを作る場合、アイテムや階段を部屋に配置するので、部屋の座標データを用意すると便利です。

マップチップは、歩ける場所と歩けない場所を塗りつぶした後で、壁などを描くと楽だと思います。

ちなみに、洞窟もぐりのマップは2Dですが、頑張れば3Dのマップも作成できると思います。

最後に

洞窟もぐりで実際に使われたアルゴリズムを解説してみました。これらのアルゴリズム以外にも沢山の選択肢があり、どの方法を用いるかによって、できるマップの性質も変わるので、色々試してみると面白いと思います。先に通路を通して、後から部屋を作るアルゴリズムもあるようです。

このアルゴリズムは、ローグライクはもちろん、それ以外のジャンルのゲームにも応用できると思うので、ぜひプログラミングしてみてください。

No related posts.