ダンジョン自動生成の作り方｜部屋と通路をつなぐコードと、つなぎ方3つの比較

ローグライクのダンジョンは、部屋をでたらめに置いて、通路でつなぐ手順で自動生成できます。部屋のつなぎ方で、通路の長さと、スタートから奥までの歩く距離が大きく変わります。この記事のコードは、部屋を置いて、3通りのつなぎ方で通路を掘り、できたダンジョンの数字を出す形です。

ここでの自動生成は、乱数と決まった手順（アルゴリズム）で作る方法です。コードはNodeで実行し、ダンジョンを1,000個ずつ作って、平均を出しました。乱数のシードは固定しています。

迷路を追いかける敵の動きは、ゲームの敵AIの作り方で扱っています。作ったダンジョンで遊べるようにするには、ブラウザゲームの作り方の画面の作り方も使えます。

この記事の目次

1. 01ダンジョン生成の3段
2. 02コード全体
3. 03部屋は、何回試せば何部屋置けるか
4. 04つなぎ方3つを比べる
5. 05確かめられていないこと
6. 06うまくいかないとき
7. 07よくある疑問
8. 08この記事のまとめ

ダンジョン生成の3段

手順は、次の3つです。

1. 部屋を置く大きさと位置をでたらめに決めて、すでにある部屋と（まわり1マスの余白も含めて）重なったら、やり直します。決めた回数だけ試して、置けた部屋が、できた部屋です
2. つなぎ方を決めるどの2部屋を通路で結ぶかを決めます。この記事では、3つの方法を比べます
3. 通路を掘る部屋の中心から中心へ、横に掘って、縦に掘る、L字の通路にします

最後に、スタートの部屋から、すべての床にたどり着けるかを、幅優先探索で数えて確かめます。

コード全体

次のコードを、dungeon.jsという名前で保存して、「node dungeon.js」で実行します。ブラウザでの実行は、確かめていません。

// ローグライク風のダンジョンを作る。部屋をでたらめに置いて、通路でつなぐ
// 実行: node dungeon.js

function makeRng(seed) { let a = seed >>> 0; return () => { a = (a + 0x6D2B79F5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }

const W = 60, H = 30;

// 1. 部屋を置く。重なったら（まわり1マスの余白も含めて）やり直す
function placeRooms(rnd, attempts) {
  const rooms = [];
  for (let i = 0; i < attempts; i++) {
    const w = 4 + Math.floor(rnd() * 6), h = 3 + Math.floor(rnd() * 4);
    const x = 1 + Math.floor(rnd() * (W - w - 2)), y = 1 + Math.floor(rnd() * (H - h - 2));
    const r = { x, y, w, h, cx: x + (w >> 1), cy: y + (h >> 1) };
    if (rooms.every((o) => r.x > o.x + o.w + 1 || o.x > r.x + r.w + 1 || r.y > o.y + o.h + 1 || o.y > r.y + r.h + 1)) rooms.push(r);
  }
  return rooms;
}

// 2. 部屋のつなぎ方（どの2部屋を通路で結ぶか）を決める
function pairsInOrder(rooms) { return rooms.slice(1).map((r, i) => [i, i + 1]); }          // 置いた順につなぐ
function pairsNearestChain(rooms) {                                                       // いちばん近い、まだ訪ねていない部屋へ進む
  const left = new Set(rooms.map((_, i) => i)); let cur = 0; left.delete(0); const out = [];
  while (left.size) { let best = null, bd = Infinity; for (const j of left) { const d = Math.abs(rooms[cur].cx - rooms[j].cx) + Math.abs(rooms[cur].cy - rooms[j].cy); if (d < bd) { bd = d; best = j; } } out.push([cur, best]); left.delete(best); cur = best; }
  return out;
}
function pairsMst(rooms) {                                                                // 最小全域木（Prim法）: 全部をつなぐ、通路の合計が最も短い組み合わせ
  const inT = new Set([0]); const out = [];
  while (inT.size < rooms.length) { let best = null, bd = Infinity; for (const i of inT) for (let j = 0; j < rooms.length; j++) { if (inT.has(j)) continue; const d = Math.abs(rooms[i].cx - rooms[j].cx) + Math.abs(rooms[i].cy - rooms[j].cy); if (d < bd) { bd = d; best = [i, j]; } } out.push(best); inT.add(best[1]); }
  return out;
}

// 3. 部屋を掘って、通路をL字に掘る
function carve(rooms, pairs) {
  const g = Array.from({ length: H }, () => Array(W).fill(1));
  for (const r of rooms) for (let y = r.y; y < r.y + r.h; y++) for (let x = r.x; x < r.x + r.w; x++) g[y][x] = 0;
  const roomTiles = g.reduce((s, row) => s + row.filter((v) => v === 0).length, 0);
  for (const [i, j] of pairs) {
    const a = rooms[i], b = rooms[j];
    for (let x = Math.min(a.cx, b.cx); x <= Math.max(a.cx, b.cx); x++) g[a.cy][x] = 0;   // 横に掘る
    for (let y = Math.min(a.cy, b.cy); y <= Math.max(a.cy, b.cy); y++) g[y][b.cx] = 0;   // 縦に掘る
  }
  const floor = g.reduce((s, row) => s + row.filter((v) => v === 0).length, 0);
  return { g, corridorTiles: floor - roomTiles, floor };
}

// 4. 検査: すべての床がつながっているか。スタート（最初の部屋）から最も遠い床までの歩数
function check(g, start) {
  const d = Array.from({ length: H }, () => Array(W).fill(-1)); d[start[1]][start[0]] = 0;
  const q = [start]; let far = 0, reached = 0;
  while (q.length) { const [x, y] = q.shift(); reached++; far = Math.max(far, d[y][x]); for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nx = x + dx, ny = y + dy; if (g[ny]?.[nx] === 0 && d[ny][nx] < 0) { d[ny][nx] = d[y][x] + 1; q.push([nx, ny]); } } }
  const floor = g.reduce((s, row) => s + row.filter((v) => v === 0).length, 0);
  let dead = 0;
  for (let y = 1; y < H - 1; y++) for (let x = 1; x < W - 1; x++) if (g[y][x] === 0) { const n = [[1, 0], [-1, 0], [0, 1], [0, -1]].filter(([dx, dy]) => g[y + dy][x + dx] === 0).length; if (n === 1) dead++; }
  return { connected: reached === floor, far, dead };
}

function generate(rnd, attempts, method) {
  const rooms = placeRooms(rnd, attempts);
  const pairs = { order: pairsInOrder, nearest: pairsNearestChain, mst: pairsMst }[method](rooms);
  const c = carve(rooms, pairs);
  return { rooms, ...c, ...check(c.g, [rooms[0].cx, rooms[0].cy]) };
}

if (typeof module !== 'undefined') module.exports = { makeRng, generate, placeRooms, pairsInOrder, pairsNearestChain, pairsMst, carve, check, W, H };

if (typeof require !== 'undefined' && require.main === module) {
  console.log('試行回数ごとの、置けた部屋の数（1,000回の平均・最小・最大）');
  for (const attempts of [10, 20, 40, 80, 160]) {
    const r = makeRng(3); const v = []; for (let i = 0; i < 1000; i++) v.push(placeRooms(r, attempts).length);
    console.log(attempts + '回', (v.reduce((a, b) => a + b, 0) / v.length).toFixed(1), Math.min(...v), Math.max(...v));
  }
  console.log('つなぎ方ごとの結果（部屋の置き方は同じ。ダンジョン1,000個の平均。試行80回）');
  for (const [name, m] of [['置いた順につなぐ', 'order'], ['近い部屋へつなぐ', 'nearest'], ['最小全域木', 'mst']]) {
    const r = makeRng(3); let rooms = 0, cor = 0, floor = 0, far = 0, dead = 0, ok = 0; const t0 = performance.now();
    for (let i = 0; i < 1000; i++) { const d = generate(r, 80, m); rooms += d.rooms.length; cor += d.corridorTiles; floor += d.floor; far += d.far; dead += d.dead; if (d.connected) ok++; }
    console.log(name, '部屋', (rooms / 1000).toFixed(1), '通路のマス', (cor / 1000).toFixed(1), '床の割合', (floor / 1000 / (W * H) * 100).toFixed(1) + '%', 'スタートから最遠', (far / 1000).toFixed(1), '袋小路', (dead / 1000).toFixed(1), 'つながっていた', ok + '/1000', '時間', ((performance.now() - t0) / 1000).toFixed(2) + 'ms/個');
  }
}

部屋は、何回試せば何部屋置けるか

部屋は、重なると置けないので、試す回数を増やしても、部屋の数は倍々にはなりません。60×30のマスで、試行回数ごとに、置けた部屋の数を、1,000回の平均で数えました。

10回で平均6.3部屋、80回で14.2部屋、160回で16.3部屋でした。80回から160回に倍にしても、増えたのは約2部屋です。部屋の数を増やしたいときは、試行回数だけでなく、部屋の大きさを小さくする必要があります。

つなぎ方3つを比べる

同じ部屋の置き方に対して、つなぎ方だけを変えました。

• 置いた順につなぐ：1番目と2番目、2番目と3番目、と順に結ぶ
• 近い部屋へつなぐ：いまの部屋から、まだ行っていない最も近い部屋へ進んでいく
• 最小全域木：全部の部屋がつながり、通路の合計がいちばん短くなる組み合わせ（Prim法）

図は、1つの例です。置いた順につなぐと、遠い部屋どうしを結ぶので、通路が長く、交差も増えます。ダンジョン1,000個の平均は、次のとおりです。

通路のマス数は、置いた順で217.3、近い部屋で91.0、最小全域木で66.6でした。床の割合（マップ全体のうち、歩ける場所）は、33.3%、26.3%、25.0%です。スタートから最も遠い所までの歩数は、置いた順で58.5歩、近い部屋で108.7歩、最小全域木で79.1歩でした。

この結果から、次のことが言えます。通路を短くして、部屋を中心に見せたいなら、最小全域木です。長い一本道で、奥まで歩かせたいなら、近い部屋へつなぐ方法が向いています。置いた順につなぐ方法は、歩数は短くなりますが、通路が交差して、床の割合も大きくなります。どれがよいかは、ゲームの狙い次第です。

1,000個とも、すべての床がつながっていました。この3つの方法は、部屋をすべて通路でつなぐ手順なので、つながるのは自然な結果です。生成にかかった時間は、1個あたり約0.1ミリ秒でした。

確かめられていないこと

• 実際に遊んだときの面白さ歩数や通路の長さは測りましたが、遊んだ感じは確かめていません。
• 通路に輪（回り道）を足す方法（この記事の3つは、どれも輪のない木の形です）
• 敵・アイテム・階段の置き方
• 部屋の形を変える方法（円形や、くぼみのある形）
• 60×30より大きなマップでの結果
• ブラウザでの実行

確かめていないものは、動かして確かめてから、別の記事で扱います。

うまくいかないとき

症状	確認すること
部屋が少ない	試行回数を増やすか、部屋の大きさを小さくします。この記事の測定では、試行80回で平均14.2部屋でした
部屋どうしがくっつく	重なりの判定に、まわり1マスの余白を入れているかを確かめます
通路が交差して見づらい	置いた順につなぐ方法になっていないかを確かめます。最小全域木にすると、通路が短くなります
行けない場所がある	checkの結果の、connectedがfalseになっていないかを確かめます。部屋をつなぐ組み合わせが、全部の部屋に届いているかを見ます

関連記事ゲームの敵AIの作り方｜迷路で相手を追いかける3つの動きと、捕まえた割合の実測

よくある疑問

この記事のまとめ