ドルアーガ風ダンジョンジェネレーター

結論

ドルアーガの塔のマップ生成アルゴリズムはすごくかっこいいです。

はじめに

ドルアーガの塔のマップ生成アルゴリズムがすごくかっこいいので、javascriptで再現してみました。

• druaga-like-dungeon-generator
• Demoページ

ページ下部のコントローラーで

• 乱数シード
• フロアサイズ（縦横）

を変更すると再現可能なフロアマップが生成されます。

本記事はドルアーガの塔のフロアマップ生成アルゴリズムについての解説となります。
マップ生成アルゴリズムは詳細な解説記事があります。

古くて新しい自動迷路生成アルゴリズム

本記事はこの解説をベースに再現と解説を行っています。

前提条件

ドルアーガの塔のフロアマップは、以下の前提条件を元に生成されています。

• 床、柱、壁のマップデータはROM上に保持しない。これらはフロア数を擬似乱数のシード値とし生成する。
• マトック（壁破壊アイテム）を使用しなくとも、必ずすべてのフロアを踏める。閉じた空間は存在しない。
• 広い部屋は存在しない。すべての床が通路になる。

実機では、フロアマップはなんと8ビットの整数値から生成されています。
各フロアの階数をシード値とするとフロアが生成されます。60階（最終フロア）のみ255をシードとして使用しています。同じフロアサイズとシード値を与えれば、必ず同じマップが生成されます。
生成されたフロア上にキャラクターを配置するとダンジョンが完成します。

広い部屋を許さないのは、当時はハードウェアの性能的にフロアの広さが制限されていたためです。
長い通路を作り出さないと、ユーザーがあっという間にフロアを横断できてしまいます。

擬似乱数

マップ生成アルゴリズムにはシード付き擬似乱数が必要となります。

シード付き擬似乱数 Xorshift

今回はこの記事を参考にXorshiftアルゴリズムで乱数を生成しています。

マップ生成アルゴリズム

ここからは、実際にどのような手順でマップが生成されているかの解説となります。

基本的な方針

ドルアーガの塔のフロアマップは、3つの要素から構成されています。

1. 外壁 ■️
2. 床
3. 柱 ●

外壁はフロア全体を囲んでいます。
床はキャラクターが自由に行き来できるマップです。
柱は等間隔に並び、ここから壁が生えています。

ドルアーガの塔のマップ生成アルゴリズムは、棒倒し法をベースにしています。
しかし、棒倒し法は単純な直線ルートが生成されやすいという問題があります。
そのため、以下のようにアレンジされています。

1. 左上から右下へ順に柱をピックアップする
2. まだ壁が生成されていない柱から、棒倒しを行い壁を伸ばす
3. 壁の先にある柱へ移動
4. 移動した先の柱で手順2の棒倒しを繰り返す。壁を伸ばす方向は後戻りしない3方向から選ぶ
5. 外壁、もしくはすでに壁が伸びている柱にたどり着いたら終了

この処理を以下では基本手順と呼びます。

この基本手順をひたすら繰り返すことで、柱から壁が伸びてマップが生成されます。
柱からスタートし、外壁に到達すると壁の生成が終了するため、フロアを縦横に分断してしまう壁は生成されません。
他の壁に合流して手順が終了した場合も、必ず外壁に届いて壁の生成が止まることになります。

閉じた空間の回避

基本手順に従い壁を作り続けると

1. 生成中のルートにぶつかる
2. 生成中のルートに四方を取り囲まれる

の2つの場合に閉じた空間が発生します。
この2つの問題を解決する必要があります。

生成中のルートにぶつかる

基本手順にしたがって壁を伸ばし続けた場合、生成中のルートに壁がぶつかると閉じた空間ができます。
数字の6のような形を想像してください。

● ← ●
↓
● ← ●
↓   ↑
● → ●

上記のような場合、生成中のルートにぶつかって円ができています。
この問題を回避するため、壁を伸ばす先が生成中のルート上でないかを確認します。
ぶつかっている場合は最後の一手の壁生成を取り消して再抽選を行います。

生成中のルートに四方を取り囲まれる

生成中のルートにぶつかる問題を解決しましたが、次のような場合の問題は回避できません。
渦巻きの形を想像してください。

● ← ● ← ●
↓
●   ● ← ●
↓       ↑
● → ● → ●

この場合、現在生成中のルートに四方を囲まれてしまっています。
最後の一手をいくら再抽選しても生成中のルートにぶつかることを回避できません。

このようなループが発生した場合は、生成中のルートの壁をすべて破棄して最初から再抽選を行います。
これで壁生成のアルゴリズムができました。

ソースとDemoページについて

GitHubに置いているソースは、マップ生成アルゴリズムがどのような挙動をしているかの確認用です。
javascriptのトランスパイルを行っても、基本的にはDemoページとまったく同じものが出力されます。

トランスパイルの手順は以下の通りです。

• GitHubからソースをクローンするかダウンロードする。
• npm installする。
• npm run publishする。
• distフォルダーにページ一式が出力され、ローカルサーバーが立ち上がる。

Demoページのデフォルトのマップサイズはドルアーガの塔のサイズを基準にしています。
フォームで入力するフロアサイズは柱の本数です。

マップ生成アルゴリズムはフロアサイズに影響されません。
サイズを拡大しても問題なく動作します。
レイアウトが破綻するためhtmlのinput側でフロアのWidthを40までに制限していますが、それ以上のサイズでも動作します。
（dungeonGenerator.jsのgenerate関数に1以上のサイズを与えれば動きます。）

文字列で出力を行っている関係上、スマホで表示するとレイアウトが崩れます。
マップチップを用意してcanvasに出力するとビジュアルの再現もできるはずです。

以上、ありがとうございました。かっこいいです。