はじめに

この記事は東京高専プロコンゼミ① Advent Calendar 2021 20日目(!?)の記事です
その②はこちら: https://adventar.org/calendars/6569

執筆時点で既にハワイ標準時ですら遅刻の大遅刻をやらかしてます、すみません...

今回はネタが本当になくてずっと悩んでいたのですが、ようやくローグライクのダンジョン生成というネタを思いついたので今回はこれについて書いていきます。

ローグライクとは

ローグライクはゲームジャンルの1つで、特徴としては
　　- グリッドで区切られたマップ
　　- ダンジョンはランダム生成
　　- ダンジョンごとにプレイヤーのステータスがリセットされる
などが挙げられます。
主に風来のシレンシリーズやポケモン不思議のダンジョンシリーズが有名でプレイしたことのある方も多いのかなと思います。

ダンジョン生成アルゴリズム

今回はダンジョンの自動生成をしたいので、生成アルゴリズムを考える必要があります。
少し調べてみたところ、RoguelikeDevコミュニティというローグライクの開発について議論をし合うコミュニティがあり、そこが生成アルゴリズムの一覧をまとめて公開しているのでこれを参考にしました。（RoguelikeDevコミュニティの皆さん、ありがとうございました）

一覧には様々なアルゴリズムが記載させているのですが、今回は最も基本的なBasic BSP Dungeon Generation(以下BSP)を使用することにします。

BSPは簡単に説明すると、あるエリアを何度か分割して、分割したエリアそれぞれに部屋を生成した後それらを道でつなげていくという手法です。
この部屋を生成したあとに道でつなげる手法を実装する上で問題になってくるのが、孤立した部屋と、道と部屋の衝突ですが、BSPはこれらの問題を簡単な実装で解決することができます。

以下では図を使って詳しく説明して行きたいと思います。
今回の例ではあるエリアを3回分割(8個部屋が生成される)することを考えます。

まずは，あるエリアを3回分割します。分割する際に縦割りにするか横割りにするかは自由です。また、分割したエリアにはわかりやすいように「親+AorB」の名前をつけています。

分割が終わったら、それぞれのエリアに収まるよう部屋を生成します。

最後に直近の親が同じ部屋を道でつなげていきます。これによって、必ず全ての部屋を繋げることができます。
また、エリアに複数の部屋がある場合には、一番境界線に近いもの同士を選ぶことで必ず他の部屋と衝突することなくつなぐことができます。

完成したダンジョンはこんな感じです。詳しい説明はwikiにあるので、こちらも合わせて参考にしてください。

実装

pythonで実装したものがこちらです。

終わりに

小学生の頃、ポケモン不思議のダンジョンが大好きでめっちゃ遊んでいましたが、今になってダンジョンの生成方法を知るとまた別の面白さが見えて来て、執筆中に買い直してやりたい気分になりました。
今回は単純なBSPを紹介しましたが、他にも面白い生成アルゴリズムがあるので興味がある方はぜひ調べてみてください。

最後になりましたが、ここまで拙い文章に付き合っていただきありがとうございました。