【ツクールMVプラグイン】ダンジョン半自動生成のアルゴリズム
この記事の背景・目的
ツイッターにて「ダンジョンの半自動生成」プラグインを公開したところ，思いのほか多くの方に「いいね」をいただきました。ありがとうございました。
【ダンジョン半自動生成】ダンジョン生成プラグインを公開しました。https://t.co/jJ4LpwUkNz
— くらげや (@kurageya0307) 2018年1月15日
通路を繋げた迷路を作っておけば，自然な感じのダンジョンに仕上げてくれます！皆使って下さい！！#ツクールMV #プラグイン pic.twitter.com/dmSIHpIaPS
このブログにて上記プラグインのアルゴリズムを解説したいと思います。次のツクール・または別のゲーム製作ツールで応用されたのならこれ以上の喜びはありません。
ダンジョン半自動生成アルゴリズム概要
- MapInfo.jsonおよびMapXXX.jsonをロードする。
- 素材マップのタイルを読み込み，準備する。
- テンプレマップのデータを読み込み，通路の位置を把握する。
- 通路の位置から「角」の位置を割り出し，角が丸くなるように修正する。
- 通路を拡げ，ガタガタした感じにする。
- 通行可能なオブジェ・通行不可能なオブジェ・壁の飾りをランダムに配置する。
- 影をつける。
- 3.～7.で作成したデータを元にダンジョンを生成し，保存する。
以降の章でこれらの詳細を説明していきます。
1.と2. マップのロードとタイルの読み込み
MapInfo.jsonとMapXXX.jsonの読み込みはGame_Mapオブジェクトのupdate関数に対しフックさせることで実現しています。データのロードそのものは，DataManagerクラスのloadDataFileを利用しています。プログラムの流れとしては以下のようになります。
- 毎フレーム（？）実行されるupdate関数が呼び出される。
- 条件分岐if(loadAtOnce)に到達する。テンポラリな変数であるloadAtOnceが初期状態ではtrueであるので，if文内の処理（ファイルの読み込み）が行われる。なお， if文内でloadAtOnceはfalseになるので，このif文は文字通りupdate関数内で1回しか実行されない。
- DataManagerクラスのloadDataFileに渡したロード先のグローバル変数が初期状態の「null」から，ファイルロード後のオブジェクトになるまで待つ。具体的には，if文の条件としてif(ロード先のグローバル変数)と記述する。nullであるうちはこのif文が真になることはなく，ファイルロードが完了し何かのオブジェクトとなった後にif文内の処理が行われる。
- 3,で示したとおりデータが読み込まれたのを待って，次の処理に進む。
このようにupdate関数内では「1回しか実行しないロード処理」と「ロードが完了するまで待つ処理」が上手く実装されています。このあたりはループやフックで実装するプログラミング特有の書き方になるかと思います。なかなか面白いので，詳しく知りたい方は「ループ フック 処理」などのワードで検索してみるといいでしょう。
3. データ読み込みおよび通路の把握
テンプレマップの読み込みが完了すると，そのマップデータを走査して，「何も置かれていないタイルは0」「何か置かれているタイルは1」とする0/1の二次元配列を作成します。イメージは下図のとおりです。
これにより，通路の位置を2次元配列として一時保存します。
4. 角の判定・角の修正
3.で得た通路の2次元配列に対し，角を見つけ・角を丸く修正します。
角を丸く修正するのはダンジョンをより自然な感じに仕上げるためです。下図に角が直角のままのダンジョン，角が丸く修正されたダンジョンの差異を示します。
なんとなくですが，角が丸まっている方が自然な感じに見えませんか？
角を修正するにはまず角がどこに存在するか見つけなければなりません。今，通路の位置のデータは0/1の二次元配列となっているため，プラグイン内では下図のように管理されている状態です。
これに対し，さらに下図のような範囲について0/1が並んでいるか調査し，角の外側・角の内側を探索します。
（角の外側については3×3マス＋アルファを調査していますが，これは特に意味のない処理方法だったことに後で気づきました。）
上記方法にて，「ある地点が角である」と判定されると，次は角に対し2次元配列をマスクデータで上書きし，角の修正を行っていきます。この時，最終的に床タイルとなる予定地は-1，壁は-2，天井は-3の値を代入するようにしています（下図）。
判定用のデータ，マスク用のデータは定数として835行目から1036行目に記述しています。これらを変更することで，角の修正は自由に変更することができます。
5. 通路のガタガタ化
4.によって角が削れ丸くなったとして，通路がそのまま一直線上になっていては自然な感じがしません。ダンジョンをより自然な感じに近づけるためには，通路を幅の広い部分・狭い部分が入り乱れるようなガタガタした感じにした方が良いと考えました。通路のガタガタ化前後の比較を下図に示します。
通路のガタガタ化のためには二つの処理を行っています。
- ガタガタ化対象となる長い通路がどこに存在するか探索する。
- ガタガタ化させる。
前者の処理はマップデータの2次元配列上で0が連続して続く部分の探索により実現しました。例えば，ある角が修正された後の通路と何もない空間の境目は，以下のようなデータが並んでいます。
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 -3 -2 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2-2 -3 0 0 0 0
0 0 -2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -2 0 0 0 0
ここで重要なのは下線赤字で示した0の羅列です。ここが通路のガタガタ化の対象となる領域となります。これは「1と隣接し」かつ「0以外の数字で囲まれ」ているという条件で探索することができます。
探索した0の羅列は「開始点の座標」と「0の羅列の長さ」の情報をバッファに保存するようにしました。ここまでがプラグインのソースコード上における1136行目「MakeLineBuffer」の処理内容です。
続いて，後者の処理を行います。ガタガタ化は0の羅列の長さに依存します。すなわち，0の羅列が十分に長い場合は，複数回の広い通路・狭い通路の繰り返しが実現できますが，0の羅列が短い場合は多くはガタガタにできません。
さきほどの探索で「0の羅列の長さ」の情報があるので，これに合わせて適切な回数ガタガタの繰り返しが起きるようにプログラムを実装しました。
6. オブジェ等の配置
オブジェ等の配置はマップデータ上の床タイルとなる領域（壁の飾りは壁となる領域）にランダムに配置するように実装しました。ただし，完全にランダムにしてしまうと，配置に偏りがでて自然な感じがしません。そこで，マップ全体を小さなサブ領域にわけ，サブ領域内にいくつかのオブジェが配置されるように実装しました。サブ領域の概念図は下図のとおりです。
7. 影
影の付け方のアルゴリズムは単純です。マップデータに対し右側から走査し，壁にあたったら影をつける，という処理を実装しています。ちなみに，ツクールMVではMapXXX.jsonファイルのdataタグにマップタイル・影・リージョンのデータが格納されており，zのインデックスが4が影となっています。影のデータは影の形に対し数値が割り振られていて，下図のようになっています。
8. データの保存
マップデータが完成したらこれをjsonファイルに書き出します。ツクールMVが利用しているNW.jsはNode.jsというプログラムを利用していて，ファイルの書き出しを行う際にはFile System Moduleというものを利用する宣言をしなければなりません。まぁ，あまり難しく考えず
var fs = require('fs');
としたら使えます。このfsに対しwriteFileSyncというメソッドを呼び出し，書き出しファイル名と書き出すデータの内容を渡して上げればデータの保存ができます。
まとめ
ツイッターにて公開したダンジョンの半自動生成プラグインのアルゴリズムについて解説しました。わからないことがあったら私のツイッターまでご連絡いただければと思います。
このプラグインが皆さんのツクールライフの一助となれば幸いです。
