前置き

3Dのアクションゲームを作っていると、大量のステージをバリエーション豊かに作る作業がめんどくさいと感じてきます。

丹精込めてオブジェクトを配置して導線を考える作業は確かに楽しいですが、
「個人でゲームを作って完成させる」という目標がある場合、量が必要な作業はストレスにもなり得ます。

モチベーションが維持している間にゲームを作り切るには、コンテンツの量産フェーズをいかに短縮してうんたらかんたら以下略

プログラムだけみたい人

GitHub：https://github.com/lisearcheleeds/DungeonMaker

概要

以下のパラメータを指定してランダム生成した2次元配列のダンジョンデータを出力します。
※ここでは「タイル」と言ったら不思議のダンジョンでいう1マスをイメージしてください

マップサイズ（10x10なら10x10のセクションが生成される）
セクションサイズ（10x10なら10x10のタイルが生成される）
開始位置となるセクションをマップの外周にするか
終了位置となるセクションをマップの外周にするか
ランダム化する歪みの強さ
その他
- セクション内で追加で生成する基準点数（int範囲）
- セクション1つごとの部屋の数（int範囲）
- 部屋から追加で生成される廊下の数（int範囲）
- 部屋の横幅（int範囲）
- 部屋の縦幅（int範囲）

例えばマップサイズ: 4x4、セクションサイズ: 10x10で生成したタイルデータがこれです

                                                                                                                        
                                                                                                                        
                                                                                                                        
       ■  ■  ■  ■                                         ■  ■  ■  ■  ■                                                 
       ■  ■  ■  ■                    ■  ■  ■  ■           ■  ■  ■  ■  ■                                                 
       ■  ■  ☆  ■                    ■  ■  ■  ■  ■  ■  ■  ■  ■  ☆  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ☆    
       ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ☆  ■           ■  ■  ■  ■  ■                                            ■    
             ■                       ■  ■  ■  ■           ■  ■  ■  ■  ■                                            ■    
             ■                                                                                                     ■    
             ■                                                                                                     ■    
             ■  ■  ■  ■  ■                                                                                         ■    
             ■  ■  ■  ■  ■                                                                                         ☆    
             ■  ■  ■  ☆  ■  ■  ■  ■  ■  ■  ■  ■                                                                    ■    
                ■  ■  ■  ■                    ■                 ■  ■  ■  ■  ☆  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■    
                                        ■  ■  ■  ■  ■           ■                                                       
                                        ■  ■  ■  ■  ■           ■                                                       
                                        ■  ■  ☆  ■  ■           ■                                                       
                                        ■  ■  ■  ■  ■           ■                                                       
                                              ■                 ■                                                       
                                              ■                 ■                                                       
                                              ■                 ■                                                       
       ■  ■  ■  ■  ■                          ■                 ■                                                       
       ■  ■  ■  ■  ■                          ■                 ■                                                       
       ■  ■  E  ■  ■                          ■                 ■                                                       
       ■  ■  ■  ■  ■                          ■                 ■                                                       
                ■                             ■           ■  ■  ■  ■  ■                                                 
                ■                             ■           ■  ■  ■  ■  ■                             S                   
                ■                             ■           ■  ■  ☆  ■  ■                             ■                   
                ■                 ☆  ■  ■  ■  ■           ■  ■  ■  ■  ■                             ■                   
                ■                 ■                                   ■                             ■                   
          ■  ■  ■  ■              ■                                   ■                             ■                   
          ■  ■  ■  ■              ■                             ■  ■  ■  ■                          ■                   
          ■  ■  ☆  ■              ■                             ■  ■  ■  ■                          ■                   
          ■  ■  ■  ■              ■                             ■  ■  ☆  ■                          ■                   
                ■                 ■                             ■  ■  ■  ■                    ■  ■  ■  ■                
                ■                 ■                             ■  ■  ■  ■                    ■  ■  ■  ■                
                ■                 ■                                   ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ☆  ■                
                ■  ■  ■  ■  ■  ■  ■  ■  ☆                                                     ■  ■  ■  ■

セクションデータがこれです

 ┏  ━  ━  ┓ 
 ┗  ┓  ┏  ┛ 
 E  ┃  ┃  S 
 ┗  ┛  ┗  ┛

気付いたかもしれませんが、不思議のダンジョン風ではないです。

まぁ一本道+αなダンジョンが欲しかったのでそう生成していますが、部屋から追加で生成される廊下の数を1以上にすれば多分不思議のダンジョンっぽくなります。

どうやって作るか

ダンジョンを自動生成するにあたって、この4つを考慮します。

マップ領域全体を出来るだけ使うこと
到達出来ない空間を生成しないこと
道が直線的ではないこと
一番奥がゴールであること

並べてみると結構めんどくさい条件です。
例えば開始位置からランダムな方向にマップを掘り続けるなんて方針でプログラムを書き出したら、まぁ出来るかもしれませんが条件付けが大量に発生しそうです。

そこで考え方としては部屋や道を最初から作り始めるのではなく、
部屋のサイズや道の長さは曖昧なまま、先に全体像を作った後にラスタライズのようなことをするのが良さそうです。

アイデア

条件の「マップ領域全体を出来るだけ使う」「到達出来ない空間を生成しない」は

開始位置と終了位置を最初に決めてパスを繋ぐ
パスが維持出来るならパスを歪ませる
2~3を繰り返す（可能な限りor任意の回数）

という方法で条件をクリア出来そうです。

つまり先にStartとEndを繋げてしまって

S ━━━━ E

こういう回り道を繰り返すと

S ━┓┏━━ E
   ┗┛

S ━┓┏━━ E
  ┏┛┗┓
  ┗━━┛

こういう道が生成される事を利用します

S ━┓┏━━ E
┏━━┛┗━━┓
┗━━━━━━┛

これを繰り返すことで、前述の4つの条件をすべて満たせそうです。
この生成した「全体像」はセクションという単位で利用します。

1つのセクション内に基準点（☆）を一つ設けてタイル状のデータを生成する時にその点を中心に廊下を作り、部屋を生成するセクションだった場合は部屋を作ります。

パスを繋げた時にStartからEndまでの道のりのうち何番目のセクションかというのが一緒にわかるので、
基準点（☆）から次のセクションの方向に廊下を伸ばし、X/Y軸が合致したタイミングで廊下を曲げます。

おわりに

細かい計算式などはリポジトリを見てください。
GitHub：https://github.com/lisearcheleeds/DungeonMaker

この手法のデメリットはお察しの通り座標計算がややこしい所ですが、
メリットとしてレベルデザインが非常に行いやすい所です。

「最初の部屋にはゴブリンを置こう」「最後の部屋にはボスを置こう」「途中で休憩所を設置しよう」など、
通常のRPGやアクションゲームを作る時にランダム生成なのに部屋単位で難易度を調整出来たりするため、
チュートリアルも含めた全ダンジョンランダム生成という銘が打てます。