概要

さて、ローグライク系の地形生成アルゴリズムはもはや何かを新しく語るまでもなく、様々な方に紹介されています。
私もそんな巨人の肩に乗りながら、地形生成アルゴリズムを作りつつ某ローグライクゲームのwikiを眺めていると、
「形状によって恣意性が大きすぎないか？それぞれ複数の生成アルゴリズムがないと難しそう」という思考に至りました。

例えば、典型的なランダムに道を伸ばして、いい感じに部屋を作るパターンだと、格子型や外周型のような形状は生成されにくく、逆に部屋を作ってから道を繋ぐようなパターンだと、行き止まりのできるような形状は生成されにくいです(そもそもアルゴリズムによってはできない場合もある)。
そもそも大部屋の場合は部屋しかありませんし、飛び地の場合は繋がっている部分が分断されている（分裂地形）場合があります。
さらに、シャッフルダンジョンというものも存在していて、こちらは有限な地形のパターンの中から一つをランダムに出しているだけです（こっちは本記事の対象外）。
ここで挙げた部屋のタイプは、最後の方に作例として画像を貼っているので、そちらをご覧ください。

なぜ、恣意性が必要なのか

なぜ、ランダムなダンジョンなのに恣意的な部分が見受けられるのでしょう？アルゴリズムの欠陥で、偏りが生まれてしまっている？
ゲームとしてランダムダンジョンを扱うには、探索していて楽しい！！と思えるような地形が求められます。
ランダムになり過ぎてしまうと、理不尽なクソゲーになってしまったり（そもそもローグライクはちょっと理不尽めのバランスに如何に対応できるかという楽しさもありますが）、開発者も想像がつかないような形状が出来上がってバランス崩壊につながったり。
逆に、パターンを絞ってしまうと、知ってるパターンをこなすだけになってしまって、毎回地形が変わるという意味が失われてこっちもクソゲーになってしまいます。

常に見たことがない地形を探索させたい、その上である程度体験をコントロールしたい。
だけど、いろんな生成パターンを考えるのはめんどくさい！形状ごとの楽しさがどうなるのかも分からない！！
そもそも、形状を一つ作るだけでもめんどくさい！！いい感じの楽しいランダムな形状が欲しい！！
ゲーム開発者はわがままなのだ！！

というわけで、いい感じにランダムで、いい感じに恣意的なランダムダンジョンを作ってみました。

作り方

今回のアルゴリズムは、ある程度のパターンはプログラムじゃなくて設計図として外部データ(ScriptableObject)にしてしまって、その設計図を元にプログラムがある程度のランダム性を加えてダンジョンを組み立てる、という思考法です。

設計図が恣意性を加える部分で、プログラムがランダム性を加える部分という認識です。
設計図に入力する情報をコントロールすることで、ランダムな部分を増やしたり、恣意的な部分を増やしたりできます。

大まかな流れはこんな感じ。
1. マップの設計図を人力で作る
2. 設計図を元にマップを作る
3. 設計図をたくさん作って、ダンジョンやフロアごとに抽選してあげればおk

設計図を人力で作る

設計図に書き込む情報をまとめるとこんな感じ。

変数名	役割
Size	盤面のサイズ
MinRoomNum MaxRoomNum	部屋の最大数下限値と上限値を設定して、組み立て時にランダムに決定
MinRandomBranchNum MaxRandomBranchNum	一通り道を繋げた後で、余分に道を足す数どことどこを繋ぐかはランダム下限値と上限値を設定して、組み立て時にランダムに決定
Sections	区域の定義情報区域ごとにさらに以下を設定・index ・左上座標・範囲・部屋の最小サイズ・絶対に部屋を作るかどうか・部屋を作るか抽選するときの重み
Connections	デフォルトの区域の接続情報 fromとtoのペアを列挙して指定 fromとtoは区域のindex
AutoGenerateDefaultConnections	デフォルトの区域接続情報をランダムに自動生成するかどうか詳しくは【道を作る】で記載

コードはこちらを参照

設計図を元にマップを作る

区域を用意

設計図を元に盤面の内部をいくつかの区域(Section)に分割します。
画像では綺麗なタイル状に並べていますが、重ならなければバラバラにずらして並べても大丈夫です。

部屋を作る

まず絶対に作りたい部屋(Room)を作ります。
次に、ランダムにできることになっている部屋を作ります。部屋の最大数に達するか、部屋を作ることになっている区域がなくなれば終了。
どこの区域に部屋を作るかは、設計図の区域ごとの重みを参照して重み抽選で決めます。
最後に部屋を作らなかった区域に、道の中継点（Relay）を設定。中継点はあとで道を繋ぐ際に使います。

一通り部屋を作り終わったところがこんな感じ（飛び飛びにある点が中継点）。

部屋を作るときの注意

道と重ならないように、部屋の最大面積は区域のサイズよりXYがそれぞれ2ずつ小さい矩形になります（青が区域の範囲だとして、白が部屋の最大面積）。

部屋を作るときに出口(Joint)の予定地も決めておきましょう。
出口同士が隣り合わないように、1、3、5あるいは2、4、6のように奇数か偶数の飛び番にする必要があります。
奇数と偶数どっちを使うかは乱数。
部屋の形状によっては、例えば上辺と右辺の交点付近で出口同士が隣り合ってしまったり、重なってしまったりすることがありますが(角と角など)、
あくまで同じ辺上で飛び飛びになっていれば良いので、問題ありません。

道を作る

接続情報整理

いきなり盤面の座標に道を置いていくのではなく、設計図と区域の情報から改めて区域同士の接続情報を整理します。

まず設計図にデフォルトの接続情報があればそれを使い、デフォルトの接続情報を自動生成することになっていたら自動生成(AutoGenerateDefaultConnectionsがtrueなら)。
自動で生成する場合は、適当に一筆書きをします。まずランダムに区域を決めて、隣接していてまだどこからも繋がってない区域をランダムに選んで繋ぐ。これを候補がなくなるまで繰り返す。この段階で繋がってない区域があっても後で繋ぐから問題無し。

こんな感じで繋ぐイメージ（これは自動で生成したやつ）。

盤面の区域の中で、どことも繋がっていない区域があれば、すでにどこかに繋がっている区域と繋がっていない区域の接続情報を作ります。
これをどことも繋がってない区域がなくなるまで繰り返します（厳密には、接続可能でどことも繋がっていない区域がなくなるまで。そもそも区域が隣接していない場合は繋がない）。

どこからも繋がってなかった右上が伸びた。

最後に、設計図の全部の道を繋げたあとで、余分に足す道の数からランダムに道の数を決めて、ランダムに適当な区域の接続情報を作ります。

道を伸ばす

どの区域(from)からどの区域(to)に道(Branch)を作るのかは一つ前の手順で決まりました。
そして、部屋ごとの出口も座標も先ほど決めましたし、部屋がない区域は中継点を作ったのでそれを使うこととしましょう。
それを１個１個参照しながら道を繋ぎます。区域Aの部屋と区域Bの部屋を繋ぐ、区域Bの部屋と区域Cの中継点を繋ぐ、といった感じ。

やり方は単純
区域Aから区域Bの境界点C1にかけて１本伸ばす