💩

The Binding of Isaac（アイザックの伝説）のダンジョン生成の仕組み

2024/12/31に公開

JavaScript

はじめに

ダンジョン探索ゲームを作ろうと思い至り（そして絶賛停滞中である）、その考えてるゲームにあってそうなダンジョン形態についてThe Binding of Isaac（アイザックの伝説）のものが良さそうだったので調べてみたら英語の解説記事があったので、こちらを大いに参考にしつつ、独自で補完し生成の仕組みを書き残そうと思います。

なお、このゲームのダンジョンは『ゼルダの伝説』を大変オマージュしているので同ゲームに近いダンジョン生成について知りたい人にも参考になると思われます。

説明のため、サンプルのリポジトリの用意したので参考に読むと理解が進むと思います。（※一部コードは記事内容との整合のため異なります）
コードの実際の実行結果はこちら

Isaacダンジョンの特徴

9x8のグリッドに縦一列を足して10列？
- このグリッド設定については元記事では文とサンプルコードが一致しておらず、いまいちハッキリしないが、とにかく列数が10であることが大事
- これを一次元の配列で表現している。つまり左右に進むときはインデックス値を-1あるいは+1、上下に進むときは-10あるいは+10する
フロア開始位置は真ん中のセル（セルNo.45が相当）
各フロアにはボス（出口）部屋、宝部屋、ショップ、秘密部屋がそれぞれ必ず１つずつある
- 秘密部屋以外は必ず袋小路に位置する
- 秘密部屋は3方向が部屋とつながっている位置に優先的に配置される
- ボス部屋は開始部屋から最も遠くにある袋小路部屋に位置するよう配慮
  - また万が一、ボス部屋と開始部屋が隣同士になってしまった場合は生成しなおす
その他、部屋が密集しずぎないように配慮

上記の特徴を再現したダンジョン配列を生成するよう、以下コードを組み立てていきます。

具体的手順

ポイントだけ抑えて手順を解説していきます。
※「インデックス値」は長いので以下"idx"と省略して書いてたりします。

フロア配列の作成

まず10x10 = 100要素の配列を作り、とりあえず0で埋めます。（floorplan変数）
そこから、部屋であれば1, ボス部屋（出口）であれば2という風に置換する形でダンジョン生成します。

フロア配列図

let floorplan = Array.from({ length: 100 }, () => 0)
const RoomEnum = {
  "EMPTY": 0, // 進入不可・壁
  "NORMAL": 1, // 通常の部屋
  "BOSS": 2, // ボス部屋
  "REWARD": 3, // 宝部屋
  "SHOP": 4, // ショップ部屋
  "SECRET": 5, // 隠し部屋
}

部屋の生成と条件

まず指定したidxに部屋を生成する関数visitについて。コメントにあるような条件に従って生成したり、しなかったりします。

const startRoomIdx = 45 // 開始部屋idx
const maxRoomNum = 15 // 最大部屋数
const minrooms = 7 // 最小部屋数

let floorplanCount =　0 // 現在生成した部屋の数
const ncount = ()=> {/*省略。セルの隣接数をカウントする関数*/}
const cellQueue = []; // 部屋生成を再帰的に行うための一時的な配列。 後述

const visit = (idx) => {
  // すでに部屋が存在する => スキップ
  if (isCellOccupied(floorplan, idx)) return 0;

  // すでに隣接している部屋がある => スキップ
  const neighbourRoomNum = ncount(floorplan, idx);
  if (1 < neighbourRoomNum) return 0;

  // すでに部屋数が最大 => スキップ
  if (maxRoomNum <= floorplanCount) return 0;

  // 50%の確率で諦める (ただしスタート部屋は例外) => スキップ
  if (random() < 0.5 && idx != startRoomIdx) return 0;

  // チェック通過：部屋を配置＆キューに追加＆部屋数増やす
  cellQueue.push(idx);
  floorplan[idx] = RoomEnum["NORMAL"];
  floorplanCount += 1;
  return 1;
};

※開発都合で1|0を返す関数になってますがtrue|falseで返すようにしても問題ありません。

ダンジョンを掘る

開始点（idx:45）を開始部屋とし、上下左右に条件を満たす限り掘り進めていきます。制限に達するなどして掘り進められなくなった段階で処理は止まります。
部屋を生成できなかった場合、そこは袋小路になるので、後の特殊部屋生成のためにendRooms配列に突っ込みます。

部屋生成に成功した際は当該idxをcellQueue配列に加えられ、それが続く限り、延々と"掘る"作業が進められます（いわゆる再帰的処理；掘る際にcellQueueからshiftで抜き出す処理があること、そして生成を行わなければ追加しないので永遠には続かない）

const endrooms = []; // 袋小路部屋を配列

// 最初の部屋を配置 -> キューが続く限り隣接セルを次々visit
visit(startRoomIdx);
while (cellQueue.length > 0) {
  const i = cellQueue.shift();
  const x = i % 10; // x軸値（＝列の値）
  let created = 0;
  if (x > 1) created = created | visit(i - 1); // Left
  if (x < 9) created = created | visit(i + 1); // Right
  if (i > 20) created = created | visit(i - 10); // Up
  if (i < 70) created = created | visit(i + 10); // Down

  // 部屋を生成しなかった -> 袋小路リストに追加
  if (created === 0) endrooms.push(i);
}

特殊部屋を配置する

ボス部屋、宝部屋、ショップ部屋を配置していきます。
これらは基本的には袋小路（endRooms）配列からランダムで抜き出すだけです。
ボス部屋のidxだけ後々の検証用に変数で保存しておきます。

const popRandomEndroom = () => {
	const index = Math.floor(Math.random() * endrooms.length);
	const i = endrooms[index];
	endrooms.splice(index, 1);
	return i;
}
let bossRoomCellIdx; // あとに検証用に保存

// ボス部屋配置
bossRoomCellIdx = endrooms.splice(endrooms.length - 1, 1)[0];
floorplan[bossRoomCellIdx] = RoomEnum["BOSS"]

// ランダムで宝部屋配置
floorplan[popRandomEndroom()] = RoomEnum["REWARD"]

// ショップ配置
floorplan[popRandomEndroom()] = RoomEnum["SHOP"]

秘密部屋の配置

最後に秘密の部屋（入り口がなく、爆弾によって開けることのできる隠し部屋）を配置。
前述の通り、壁部分から部屋が密集した位置に優先配置されます。
またボス部屋に隣接するセルも候補から外れます。

function pickSecretRoom(floorplanRef, bossl, rng) {
  for (let e = 0; e < 900; e++) {
    const x = Math.floor(rng() * 9) + 1;
    const y = Math.floor(rng() * 8) + 2;
    const i = y * Y_UNIT + x;

    // 生成済みの部屋は避ける
    if (floorplanRef[i]) continue;

    // ボス部屋隣接は避ける
    if (
      bossl === i - DIR_LEFT ||
      bossl === i + DIR_RIGHT ||
      bossl === i + DIR_DOWN ||
      bossl === i - DIR_UP
    )
      continue;

    // 3+ roomsである
    const neigborCnt = ncount(floorplanRef, i);
    if (neigborCnt >= 3) return i; // 隣接セルが3以上
    if (e > 300 && neigborCnt >= 2) return i;
    if (e > 600 && neigborCnt >= 1) return i;
  }
}

ちなみに900回ループなのは元記事からそのまま引用してるだけで、理由は不
明…（10*9=90部屋を基準にしてるから？）

ダンジョンを検証

部屋の数が最低値以下でないこと
ボス部屋と開始部屋が隣接してない

以上を確認し、もしダメだったら生成をやり直す。

const validate = () => {
  if (floorplanCount < minrooms) return false;
  if (isNeighborOfStartRoom(bossRoomCellIdx)) return false;
  return true;
};
do {
  /* …ダンジョン生成処理コード… */
} while (validate() === false);

OKだったら無事ダンジョン配列を返して終了となります。

参考

元記事：https://www.boristhebrave.com/2020/09/12/dungeon-generation-in-binding-of-isaac/