ダンジョン自動生成の検証

既に前回の記事からひと月半が経ちました。
なんかイラスト描くとか言ってましたが、既に打ち砕かれました。
普通に忙しいのもありますが、ある週はノロになったり別の週も体調壊したり、色々です。

さて、そういうどうでも良い話はさておき、タイトルの通りダンジョン自動生成のアルゴリズムを検証してみたという話。
前々からやってみたかったものですが、なんだかめんどくさそーとか思って手を付けてなかった部分です。
気まぐれでやる気になったのでやってみました。

アルゴリズムの選定

こういった要件で使用されるアルゴリズムは、主に「穴掘り法」と呼ばれるもの、「区域分割法」と呼ばれるものの二種類のようです。
よりマッチすると思われる後者を選択しました。

アルゴリズム解説

ということで区域分割法をベースに、自分なりに理想に近くなるようにアレンジしたものをざっくりまとめます。

空間の分割

初めに大きな空間を一つ用意し、縦横いずれかに二つに分割します。
このとき幅（縦分割の場合は高さ）は一定の範囲内でランダムとします。
求められた乱数と、元の大きさからその乱数を減算して残った分とで二つに空間になります。
その二つの空間を、また同じようにそれぞれ縦横いずれかに分割します。
そしてまた四つの空間を分割。。。
という具合に、「次に分割したら小さくなりすぎるよ」というところまで続け、分割が終わったものからリストへ放り込みます。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1353821098400387074

部屋を作る

分割が終わった空間の中に収まるように、ランダムな大きさで部屋を作っていきます。
空間と部屋は必ず一対一となります。
部屋が空間の中のどの位置にあるかも、はみ出ない範囲でランダムに取ります。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1354175134777503744

部屋を通路でつなげる

部屋を作っただけだと行き来ができないので、必ず全部屋に到達できるように通路でつなげてやる必要があります。
これが結構ややこしかったのですが、最終的に
・左上の部屋から全部順番に繋げていく
・一本道だとつまらないので、ランダムで余分な道を作る
というやり方を採用しました。
↓みたいな結果になります。

https://twitter.com/blackpman/status/1355135054029021187

完成

という感じで最低限の実装はできたかな、と思います。
実際はこの作り方だとえらく部屋数が少なくなってしまったり、乱数次第で微妙な結果が出たりするので要調整ということで。

ソースコード

何の整理もしていないし、変数名もあまりにいい加減ですが載せておきます。
描画はDXライブラリを使っています。

ではまたそのうち。