Which procedural dungeon generation algorithm should I use?

Only 0.5% of 1,000 seeded 200x120 cellular automata caves were fully connected, against 100% for BSP rooms, random room placement and drunkard's walk, so pick BSP for rooms and cellular automata for caves, and always repair the caves with a flood-fill tunnel rather than a retry. The stray pockets were small: on average the largest cave region held 98.9% of the floor, and the median fix carved 16 cells. Discarding the map and trying again did not work. 78 of 100 seeds were still disconnected after 50 attempts.

Procedural dungeon generation tutorials present these four algorithms as a matter of taste. They are not. They differ in things that break a game: floor the player can never reach, dead ends, corridors one tile wide, and paths that wind. I generated every algorithm on the same seeds and counted.

Hardware: Apple M3, 8 cores, 16 GB, macOS 26.4.1. Node v23.5.0, no packages, every generator written by hand with a seeded mulberry32 PRNG. 1,000 seeds per algorithm at 80x50 and 200x120. Each algorithm ran in its own Node process, because a shared process biased JIT timings in an earlier benchmark of ours. Other benchmarks were running on this machine (load average 3.7 to 6.8), so timings are medians and the ratios matter more than the milliseconds. Every row except timing came out identical across two full runs. The two timing runs differed by at most 7.3% (calculated).

The short answer

• Cellular automata caves were almost never connected. 17.7% of 80x50 caves and 0.5% of 200x120 caves had a single region. The worst 200x120 cave had 19 separate regions.
• The disconnection was mostly cosmetic. The largest region averaged 96.2% of the floor at 80x50 and 98.9% at 200x120. Only 7 of 1,000 small caves had a main region under 60%. None of the large ones did.
• Retrying is the wrong repair. Discard-and-retry needed a median 3 discards at 80x50 and failed outright on 78% of 200x120 seeds within 50 tries. A flood-fill tunnel carved a median 16 cells in 3.5 ms.
• Drunkard's walk is connected by construction, and it leaves the most dead ends. 100.6 dead-end cells per 200x120 map, 4.6x the caves (calculated). Rooms-and-corridors generators had none.
• BSP was the fastest and random room placement had the longest walks. BSP took 0.039 ms at 200x120, 49x faster than cellular automata (calculated). A path between two random floor cells in placed rooms was 2.34x its straight Manhattan distance, the worst of the four.

What exactly was generated?

All four fill a grid where 1 is floor and 0 is wall, with a solid border.

• BSP: split the map recursively until a leaf would be under 10 cells on a side, put a random room of at least 4x4 in each leaf with a 1-cell margin, then join a random room from each pair of siblings with an L-shaped corridor.
• Room placement: try W*H/40 random rooms of 4 to 12 cells a side, reject any that touch an existing room, then join room centres with a minimum spanning tree (Prim) using L-shaped corridors.
• Cellular automata: 45% walls at random, then 5 iterations of the 4-5 rule. A wall stays a wall with 4 or more wall neighbours out of 8. A floor becomes a wall with 5 or more.
• Drunkard's walk: start in the centre, step in a random direction, and stop when 40% of all cells are floor.

The metrics, per map:

• Regions: 4-connected flood fill over floor cells.
• Dead end: a floor cell with exactly one floor neighbour out of four.
• 1-wide cell: a floor cell with walls on both sides along at least one axis. A corridor, or a pinch point.
• Open cell: a floor cell whose eight neighbours are all floor. Space with no wall to hide behind.
• Linked pair: the chance that two random floor cells are in the same region, calculated as the sum of squared region sizes over floor squared. If you drop a key and a door at random, this is how often the player can reach both.
• Playability proxy: eight random pairs of cells inside the largest region. BFS path length divided by W+H, and BFS path length divided by Manhattan distance, a detour ratio of at least 1.0.

How do the four algorithms compare?

200x120, 1,000 seeds, run 1. Timings are medians. Everything else is a mean unless labelled.

The same seeds at 80x50:

Run 2 put cellular automata at 1.911 ms and drunkard's walk at 0.754 ms at 200x120. The ranking did not change.

Why are cellular automata caves always disconnected?

The 4-5 rule is local. Each cell looks at its eight neighbours and nothing else, so nothing in it knows whether a floor pocket touches the rest of the cave. Random noise leaves small enclosed bubbles, and in these runs five smoothing passes did not open them up. A bigger map has more places for a bubble. The connected rate fell from 17.7% to 0.5% as the area went up 6x, and the mean region count went from 2.83 to 6.94.

I expected the opposite failure. The usual warning about caves is a map split in half, which is why I measured how often the largest region fell under 60%. It was 0.7% of small caves and 0% of large ones. The worst 200x120 cave still kept 86.6% of its floor in one piece. The typical defect is not a split cave. It is a handful of sealed closets.

They still break games. At 80x50, two random floor cells were in different regions 6.5% of the time (calculated from the 93.5% row). Spawn a key at random on 1,000 maps and some will be unwinnable. The failed pathfinding query that follows is the most expensive search there is, as pathfinding with no path measured: A* visits every reachable cell before it gives up.

Should you repair the map or throw it away?

Repair it. Both options, cellular automata only, since the other three never needed either:

The tunnel repair labels regions, runs a multi-source BFS through walls from the largest region, carves the path to the first floor cell of another region, and repeats. At 200x120 it took 1.8x as long as generating the cave (calculated), and 16 carved cells is 0.1% of a cave's roughly 15,900 floor cells (calculated). The cheaper alternative is to fill every pocket with wall. That lost 1.1% of the floor on a large map and took no tunnels, but the worst small cave would lose 52.2% of its floor (calculated from its 47.8% largest region).

Discard-and-retry is what many tutorials suggest, and it was the worst option. At 80x50 a median 3 discards means about 4 generations, 1.24 ms against 0.56 ms for generate-plus-tunnel (both calculated from the medians). At 200x120, 78 seeds out of 100 gave no connected cave in 50 tries: 96 ms of generation (calculated) and still nothing to ship.

Is drunkard's walk the safe choice?

It is always connected, because a walker cannot teleport. It is not clean. 100.6 dead-end cells per 200x120 map is 4.6x the caves (calculated), and rooms and corridors had zero. The walk leaves spurs along the ragged edge of its blob, and every one is a spot a player walks into and has to back out of. I counted dead-end cells, not how long each spur is.

The shape result is the one I did not predict. I defined "unusable" as corridor cells one tile wide, and expected the walk to win that. It did not. BSP had the most, at 11.7% of its floor, because every link between rooms is a 1-wide L. The walk had 2.7% and caves 0.1%. By the open-space measure it was the reverse: 64.9% of cave floor and 60.3% of drunkard floor had no wall anywhere in reach. Caves and walks give you big open rooms. Rooms-and-corridors give you chokepoints, which is usually what a combat game wants.

Which one gives the best paths?

Cellular automata and drunkard's walk gave the straightest paths, both with a detour ratio of 1.14 on large maps. Placed rooms were worst, at 2.34 on large maps. A minimum spanning tree has exactly one route between any two rooms and no loops, so crossing the map often means walking the long way round. BSP sat at 1.74. If you use room placement, add a few extra corridors beyond the tree. I did not measure that variant.

For speed, generation is not your budget at these sizes. The slowest median was 1.925 ms for a 200x120 cave. That is a tenth of a 16.67 ms frame, for a level you build once. How you store it matters more, as covered in how to store a big tilemap. For worlds that stream in while the player moves, the constraints in what a terrain chunk costs apply instead.

Check it yourself

Node 18+, no dependencies, one CommonJS file. About a minute on the M3 above. Save it as dungeon-gen.cjs so it runs as CommonJS even inside a "type": "module" project, then run node dungeon-gen.cjs. It spawns one child process per algorithm and prints both tables, including the repair columns. The headline number is the 0.5% in the fully connected, no repair row under 200x120. Everything except the timing rows reproduces exactly from the seeds.

// dungeon-gen.cjs — node dungeon-gen.cjs [seeds]   (Node 18+, no dependencies)
'use strict';
const { execFileSync } = require('child_process');

// ---- seeded PRNG (mulberry32) ----------------------------------------------
const rng = s => () => { s |= 0; s = s + 0x6D2B79F5 | 0; let t = Math.imul(s ^ s >>> 15, 1 | s);
  t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; };
const ri = (r, a, b) => a + Math.floor(r() * (b - a + 1)); // inclusive

// ---- carving helpers: 1 = floor, 0 = wall ----------------------------------
const room = (g, W, x, y, w, h) => { for (let j = y; j < y + h; j++) for (let i = x; i < x + w; i++) g[j * W + i] = 1; };
function lCorridor(g, W, r, [x1, y1], [x2, y2]) {
  const hFirst = r() < 0.5, row = hFirst ? y1 : y2, col = hFirst ? x2 : x1; // bend at (col,row)
  for (let x = Math.min(x1, x2); x <= Math.max(x1, x2); x++) g[row * W + x] = 1;
  for (let y = Math.min(y1, y2); y <= Math.max(y1, y2); y++) g[y * W + col] = 1;
}
const centre = ([x, y, w, h]) => [x + (w >> 1), y + (h >> 1)];

// ---- (a) BSP: split to leaves >= 10 cells, one room per leaf, join siblings
function bsp(W, H, r) {
  const g = new Uint8Array(W * H), MIN = 10;
  function split(x, y, w, h) {
    let vert = w > h * 1.25 ? true : h > w * 1.25 ? false : r() < 0.5;
    if (vert && w < MIN * 2) vert = false; if (!vert && h < MIN * 2) vert = w >= MIN * 2;
    if ((vert && w < MIN * 2) || (!vert && h < MIN * 2)) { // leaf: a room with a 1-cell margin
      const rw = ri(r, 4, w - 2), rh = ri(r, 4, h - 2), rx = ri(r, x + 1, x + w - rw - 1), ry = ri(r, y + 1, y + h - rh - 1);
      room(g, W, rx, ry, rw, rh); return [[rx, ry, rw, rh]];
    }
    const at = vert ? ri(r, MIN, w - MIN) : ri(r, MIN, h - MIN);
    const a = vert ? split(x, y, at, h) : split(x, y, w, at);
    const b = vert ? split(x + at, y, w - at, h) : split(x, y + at, w, h - at);
    lCorridor(g, W, r, centre(a[Math.floor(r() * a.length)]), centre(b[Math.floor(r() * b.length)]));
    return a.concat(b);
  }
  split(0, 0, W, H); return g;
}
// ---- (b) random rooms with rejection, joined by a minimum spanning tree ----
function rooms(W, H, r) {
  const g = new Uint8Array(W * H), rs = [], tries = Math.round(W * H / 40);
  for (let t = 0; t < tries; t++) {
    const w = ri(r, 4, 12), h = ri(r, 4, 12), x = ri(r, 1, W - w - 1), y = ri(r, 1, H - h - 1);
    if (rs.some(([a, b, c, d]) => x <= a + c && a <= x + w && y <= b + d && b <= y + h)) continue; // 1-cell gap
    rs.push([x, y, w, h]); room(g, W, x, y, w, h);
  }
  const c = rs.map(centre), inT = new Uint8Array(rs.length), best = new Float64Array(rs.length).fill(Infinity), from = new Int32Array(rs.length);
  let cur = 0; inT[0] = 1; // Prim
  for (let k = 1; k < rs.length; k++) {
    let nxt = -1;
    for (let i = 0; i < rs.length; i++) if (!inT[i]) {
      const d = (c[i][0] - c[cur][0]) ** 2 + (c[i][1] - c[cur][1]) ** 2; if (d < best[i]) { best[i] = d; from[i] = cur; }
      if (nxt < 0 || best[i] < best[nxt]) nxt = i;
    }
    inT[nxt] = 1; lCorridor(g, W, r, c[from[nxt]], c[nxt]); cur = nxt;
  }
  return g;
}
// ---- (c) cellular automata: 45% walls, 4-5 rule, 5 iterations --------------
function cave(W, H, r) {
  let g = new Uint8Array(W * H), n = new Uint8Array(W * H);
  for (let y = 1; y < H - 1; y++) for (let x = 1; x < W - 1; x++) g[y * W + x] = r() < 0.45 ? 0 : 1;
  for (let it = 0; it < 5; it++) {
    for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) {
      if (x === 0 || y === 0 || x === W - 1 || y === H - 1) { n[y * W + x] = 0; continue; }
      let walls = 0;
      for (let dy = -1; dy <= 1; dy++) for (let dx = -1; dx <= 1; dx++) if ((dx || dy) && !g[(y + dy) * W + x + dx]) walls++;
      const wall = !g[y * W + x];
      n[y * W + x] = walls >= 5 || (wall && walls === 4) ? 0 : 1;
    }
    [g, n] = [n, g];
  }
  return g;
}
// ---- (d) drunkard's walk from the centre until 40% of all cells are floor --
function drunk(W, H, r) {
  const g = new Uint8Array(W * H), target = Math.round(W * H * 0.4);
  let x = W >> 1, y = H >> 1, floor = 0;
  while (floor < target) {
    if (!g[y * W + x]) { g[y * W + x] = 1; floor++; }
    const d = Math.floor(r() * 4);
    if (d === 0 && x > 1) x--; else if (d === 1 && x < W - 2) x++; else if (d === 2 && y > 1) y--; else if (d === 3 && y < H - 2) y++;
  }
  return g;
}
const ALGOS = { bsp, rooms, cave, drunk };

// ---- measurement --------------------------------------------------------------
function label(g, W, H) { // 4-connected regions; returns {lab, sizes}
  const lab = new Int32Array(W * H).fill(-1), sizes = [], st = new Int32Array(W * H);
  for (let s = 0; s < g.length; s++) if (g[s] && lab[s] < 0) {
    const id = sizes.length; let sp = 0, cnt = 0; st[sp++] = s; lab[s] = id;
    while (sp) { const p = st[--sp]; cnt++; const x = p % W;
      for (const q of [p - 1, p + 1, p - W, p + W]) if (q >= 0 && q < g.length && g[q] && lab[q] < 0 && (q === p - 1 ? x > 0 : q === p + 1 ? x < W - 1 : true)) { lab[q] = id; st[sp++] = q; } }
    sizes.push(cnt);
  }
  return { lab, sizes };
}
function bfs(g, W, H, src) {
  const dist = new Int32Array(W * H).fill(-1), q = new Int32Array(W * H); let h = 0, t = 0; q[t++] = src; dist[src] = 0;
  while (h < t) { const p = q[h++], x = p % W;
    if (x > 0 && g[p - 1] && dist[p - 1] < 0) { dist[p - 1] = dist[p] + 1; q[t++] = p - 1; }
    if (x < W - 1 && g[p + 1] && dist[p + 1] < 0) { dist[p + 1] = dist[p] + 1; q[t++] = p + 1; }
    if (p >= W && g[p - W] && dist[p - W] < 0) { dist[p - W] = dist[p] + 1; q[t++] = p - W; }
    if (p < W * (H - 1) && g[p + W] && dist[p + W] < 0) { dist[p + W] = dist[p] + 1; q[t++] = p + W; } }
  return dist;
}
function measure(g, W, H, r) {
  let floor = 0, dead = 0, narrow = 0, open = 0;
  for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) { const p = y * W + x; if (!g[p]) continue; floor++;
    const L = x > 0 && g[p - 1], R = x < W - 1 && g[p + 1], U = y > 0 && g[p - W], D = y < H - 1 && g[p + W];
    if (L + R + U + D === 1) dead++;
    if ((!L && !R) || (!U && !D)) narrow++;              // a 1-wide cell on at least one axis
    if (x > 0 && y > 0 && x < W - 1 && y < H - 1 && L && R && U && D && g[p - W - 1] && g[p - W + 1] && g[p + W - 1] && g[p + W + 1]) open++; }
  const { lab, sizes } = label(g, W, H), big = Math.max(...sizes), bigId = sizes.indexOf(big);
  let pairOK = 0; for (const s of sizes) pairOK += s * s;      // P(two random floor cells are connected)
  const cells = []; for (let p = 0; p < g.length; p++) if (lab[p] === bigId) cells.push(p);
  let pathSum = 0, detour = 0, n = 0;                           // playability: 8 random pairs in the main region
  for (let k = 0; k < 8; k++) { const a = cells[Math.floor(r() * cells.length)], b = cells[Math.floor(r() * cells.length)];
    const man = Math.abs(a % W - b % W) + Math.abs((a / W | 0) - (b / W | 0)); if (!man) continue;
    const d = bfs(g, W, H, a)[b]; pathSum += d / (W + H); detour += d / man; n++; }
  return { floor: floor / (W * H), regions: sizes.length, bigShare: big / floor, dead, narrow: narrow / floor, open: open / floor,
    pairOK: pairOK / (floor * floor), path: pathSum / n, detour: detour / n };
}
function connect(g, W, H) { // repair: tunnel from the main region to the nearest other region, repeat
  let carved = 0;
  for (;;) {
    const { lab, sizes } = label(g, W, H); if (sizes.length < 2) return carved;
    const main = sizes.indexOf(Math.max(...sizes)), prev = new Int32Array(W * H).fill(-2), q = new Int32Array(W * H); let h = 0, t = 0;
    for (let p = 0; p < g.length; p++) if (lab[p] === main) { prev[p] = -1; q[t++] = p; }
    let hit = -1;
    while (h < t && hit < 0) { const p = q[h++], x = p % W;
      for (const nb of [x > 1 ? p - 1 : -1, x < W - 2 ? p + 1 : -1, p >= 2 * W ? p - W : -1, p < W * (H - 2) ? p + W : -1]) {
        if (nb < 0 || prev[nb] !== -2) continue; prev[nb] = p;
        if (g[nb] && lab[nb] !== main) { hit = nb; break; } q[t++] = nb; } }
    for (let p = prev[hit]; p >= 0 && lab[p] !== main; p = prev[p]) if (!g[p]) { g[p] = 1; carved++; }
  }
}

const SIZES = [[80, 50], [200, 120]], med = a => { const s = [...a].sort((x, y) => x - y); return s[s.length >> 1]; };
const now = () => Number(process.hrtime.bigint()) / 1e6;

if (process.argv[2] === 'child') { // one algorithm, one fresh process
  const [, , , name, seeds] = process.argv, gen = ALGOS[name], N = +seeds, out = {};
  for (const [W, H] of SIZES) {
    for (let s = 0; s < 200; s++) gen(W, H, rng(1e6 + s)); // warm-up, untimed
    const ms = [], rows = [], repMs = [], carved = [], retries = []; let lt60 = 0, cull = 0;
    for (let s = 1; s <= N; s++) {
      const t0 = now(), g = gen(W, H, rng(s)); ms.push(now() - t0);
      const m = measure(g, W, H, rng(s ^ 0x5bd1e995)); rows.push(m); if (m.bigShare < 0.6) lt60++; cull += 1 - m.bigShare;
      if (m.regions > 1) { const t1 = now(); carved.push(connect(g, W, H)); repMs.push(now() - t1); }
    }
    for (let s = 1; s <= Math.min(N, 100); s++) { // discard-and-retry until one region, capped at 50 attempts
      let k = 0; while (k < 50 && label(gen(W, H, rng(s * 1000 + k)), W, H).sizes.length > 1) k++; retries.push(k);
    }
    const avg = f => rows.reduce((a, m) => a + m[f], 0) / rows.length;
    out[`${W}x${H}`] = { ms: med(ms), floor: avg('floor'), regions: avg('regions'), maxRegions: Math.max(...rows.map(m => m.regions)),
      bigShare: avg('bigShare'), minBig: Math.min(...rows.map(m => m.bigShare)), lt60: lt60 / N, dead: avg('dead'), narrow: avg('narrow'), open: avg('open'),
      pairOK: avg('pairOK'), path: avg('path'), detour: avg('detour'), connected: rows.filter(m => m.regions === 1).length / N,
      repairMs: repMs.length ? med(repMs) : 0, carved: carved.length ? med(carved) : 0, cullLost: cull / N,
      retryOK: retries.filter(k => k < 50).length / retries.length, retryMed: med(retries) };
  }
  console.log(JSON.stringify(out)); return;
}

const N = +(process.argv[2] || 1000), pct = x => (100 * x).toFixed(1) + '%';
console.log(`node ${process.version}, ${N} seeds per algorithm and size, each algorithm in its own process`);
const res = {};
for (const name of Object.keys(ALGOS)) {
  process.stdout.write(`running ${name}... `);
  res[name] = JSON.parse(execFileSync(process.execPath, [__filename, 'child', name, String(N)], { encoding: 'utf8' }));
  console.log('done');
}
for (const [W, H] of SIZES) {
  const k = `${W}x${H}`; console.log(`\n## ${k}`);
  const rows = [['', ...Object.keys(ALGOS)],
    ['gen ms (median)', ...Object.values(res).map(r => r[k].ms.toFixed(3))],
    ['floor %', ...Object.values(res).map(r => pct(r[k].floor))],
    ['regions (mean / max)', ...Object.values(res).map(r => `${r[k].regions.toFixed(2)} / ${r[k].maxRegions}`)],
    ['largest region % of floor', ...Object.values(res).map(r => pct(r[k].bigShare))],
    ['worst largest region', ...Object.values(res).map(r => pct(r[k].minBig))],
    ['maps with largest < 60%', ...Object.values(res).map(r => pct(r[k].lt60))],
    ['fully connected, no repair', ...Object.values(res).map(r => pct(r[k].connected))],
    ['P(2 random floor cells linked)', ...Object.values(res).map(r => pct(r[k].pairOK))],
    ['dead-end cells (mean)', ...Object.values(res).map(r => r[k].dead.toFixed(1))],
    ['1-wide cells % of floor', ...Object.values(res).map(r => pct(r[k].narrow))],
    ['open cells (8 floor nbrs) %', ...Object.values(res).map(r => pct(r[k].open))],
    ['path / (W+H) (mean)', ...Object.values(res).map(r => r[k].path.toFixed(3))],
    ['path / manhattan (mean)', ...Object.values(res).map(r => r[k].detour.toFixed(2))],
    ['repair: ms (median)', ...Object.values(res).map(r => r[k].repairMs.toFixed(3))],
    ['repair: cells carved (median)', ...Object.values(res).map(r => r[k].carved)],
    ['cull instead: floor lost', ...Object.values(res).map(r => pct(r[k].cullLost))],
    ['retry: connected in 50 tries', ...Object.values(res).map(r => pct(r[k].retryOK))],
    ['retry: median discards', ...Object.values(res).map(r => r[k].retryMed)]];
  for (const r of rows) console.log(r[0].padEnd(32) + r.slice(1).map(c => String(c).padStart(14)).join(''));
}

On the machine above, node dungeon-gen.cjs:

node v23.5.0, 1000 seeds per algorithm and size, each algorithm in its own process
running bsp... done
running rooms... done
running cave... done
running drunk... done

## 80x50
                                           bsp         rooms          cave         drunk
gen ms (median)                          0.009         0.020         0.494         0.150
floor %                                  38.2%         32.7%         59.9%         40.0%
regions (mean / max)                  1.00 / 1      1.00 / 1     2.83 / 10      1.00 / 1
largest region % of floor               100.0%        100.0%         96.2%        100.0%
worst largest region                    100.0%        100.0%         47.8%        100.0%
maps with largest < 60%                   0.0%          0.0%          0.7%          0.0%
fully connected, no repair              100.0%        100.0%         17.7%        100.0%
P(2 random floor cells linked)          100.0%        100.0%         93.5%        100.0%
dead-end cells (mean)                      0.0           0.0           4.9          21.7
1-wide cells % of floor                  10.3%          6.9%          0.2%          3.3%
open cells (8 floor nbrs) %              47.3%         49.3%         61.6%         52.8%
path / (W+H) (mean)                      0.483         0.492         0.351         0.282
path / manhattan (mean)                   1.58          1.71          1.19          1.12
repair: ms (median)                      0.000         0.000         0.415         0.000
repair: cells carved (median)                0             0             6             0
cull instead: floor lost                  0.0%          0.0%          3.8%          0.0%
retry: connected in 50 tries            100.0%        100.0%        100.0%        100.0%
retry: median discards                       0             0             3             0

## 200x120
                                           bsp         rooms          cave         drunk
gen ms (median)                          0.052         0.290         2.568         1.027
floor %                                  39.5%         34.5%         66.3%         40.0%
regions (mean / max)                  1.00 / 1      1.00 / 1     6.94 / 19      1.00 / 1
largest region % of floor               100.0%        100.0%         98.9%        100.0%
worst largest region                    100.0%        100.0%         86.6%        100.0%
maps with largest < 60%                   0.0%          0.0%          0.0%          0.0%
fully connected, no repair              100.0%        100.0%          0.5%        100.0%
P(2 random floor cells linked)          100.0%        100.0%         97.8%        100.0%
dead-end cells (mean)                      0.0           0.0          21.8         100.6
1-wide cells % of floor                  11.7%          7.0%          0.1%          2.7%
open cells (8 floor nbrs) %              46.3%         49.4%         64.9%         60.3%
path / (W+H) (mean)                      0.524         0.687         0.357         0.298
path / manhattan (mean)                   1.74          2.34          1.14          1.14
repair: ms (median)                      0.000         0.000         5.318         0.000
repair: cells carved (median)                0             0            16             0
cull instead: floor lost                  0.0%          0.0%          1.1%          0.0%
retry: connected in 50 tries            100.0%        100.0%         22.0%        100.0%
retry: median discards                       0             0            50             0

This run was taken while the load average was between 12.6 and 16.0, so its timing rows are about 30% slower than the tables above. Every other row matches them exactly, including the 0.5%.

What this does not cover

One set of parameters per algorithm. A 40% fill for caves, more iterations, or a walker that restarts from random floor cells will all move these numbers. 8-way movement would merge some cave pockets that 4-way flood fill counts as separate. Nothing here measures whether a map is fun. It measures the defects that make it unplayable, and how much each costs to remove.