はじめに
ドルアーガの塔の迷路生成アルゴリズムを解説した記事を参考に、60フロア分の迷路を再現するジェネレータをJavaScriptで作りました。
「みんな出してるけど」の一つではありますが、実機の画面と全マス照合して一致を確認したので、その記録を残します。
リポジトリ: https://github.com/kumi0708/druaga-maze
デモ(ブラウザで動きます): https://kumi0708.github.io/druaga-maze/
画面にはフロア、アルゴリズム、乱数方式、シード値を表示します。上は1F(シード0)、下は6F(シード5)です。
使っているアルゴリズムとシード値
| 項目 | 内容 |
|---|---|
| アルゴリズム | 壁伸ばし法 |
| 乱数 | 8bit LFSR(XNOR帰還、tap は bit7 と bit4) |
| シード値 | フロア n は n-1、60F のみ 255 |
| 盤面 | 柱 17×8(壁込みで 37×19 マス) |
面のデータは持たず、シード値から毎回生成されます。
壁伸ばし法
柱を右の列から左へ、各列は上から下へ走査します。未訪問の柱から乱数で方向を決めて壁を伸ばし、既存の壁や外壁にぶつかったら止めます。
乱数
function makeRand(u) {
let seed = u & 0xff;
let prev = u & 1;
return function () {
const r2 = (((seed >> 7) ^ (seed >> 4)) & 1) ^ 1; // XNOR
seed = ((seed << 1) | r2) & 0xff;
const v = ((prev << 1) | r2) & 3; // 前回と今回の帰還ビットで2bit
prev = r2;
return v; // 0:上 1:右 2:下 3:左
};
}
実機画面との照合
6F・15F・16F・22F・30F・32F の画面画像を 37×19 に読み取り、生成結果と全703マスを比較しました。6面すべて差分 0 で一致しました。
ハマりどころ
元記事の本文とコードには食い違いがあります(方向の割り当て、2bit値の作り方)。実装はコードに従うと一致しました。
60F はシード 255 で LFSR が固定され、方向が常に「左」になるため、横一直線の通路が並ぶ形になります。こちらは実機との照合ができていません。
おわりに
照合できたのは6面だけです。他のフロアの画面をお持ちの方、ぜひ照合してみてください。
参考
『ドルアーガの塔』は株式会社バンダイナムコエンターテインメントの作品です。本記事は非公式のファンによるものです。