Cellular Automata in Game Development — Cave Generation, Living Worlds & Falling Sand

/*
  Step 3: Carve tunnels between caves
  -----------------------------------
  Option B: keep every cave and connect them. Start from the biggest cave, then repeatedly
  find the closest unconnected cave and dig a tunnel to it, like growing a tree of caves.
*/

// An edge cell is a floor cell touching rock. Tunnels only need to start and end on edges,
// which shrinks the search from thousands of cells to a few hundred.
// (Safe to index cell +/- 1 and +/- width: the border is always rock, so floor never touches it.)
function isRoomEdge(grid, width, cell) {
  return grid[cell - 1] === WALL || grid[cell + 1] === WALL ||
    grid[cell - width] === WALL || grid[cell + width] === WALL;
}

// Squared distance is enough for comparisons, and it skips a slow square root.
function distanceSquared(a, b, width) {
  const dx = (a % width) - (b % width);
  const dy = Math.floor(a / width) - Math.floor(b / width);
  return dx * dx + dy * dy;
}

// Stamp a round brush of floor, never touching the outer border.
function carveCircle(grid, width, height, cx, cy, radius) {
  for (let y = cy - radius; y <= cy + radius; y++) {
    for (let x = cx - radius; x <= cx + radius; x++) {
      const inside = x > 0 && y > 0 && x < width - 1 && y < height - 1;
      if (inside && (x - cx) * (x - cx) + (y - cy) * (y - cy) <= radius * radius) {
        grid[y * width + x] = FLOOR;
      }
    }
  }
}

// Walk a straight line from cell `from` to cell `to` (Bresenham's line algorithm),
// stamping the brush at every step. On a diagonal step we also stamp after the x move,
// so the tunnel stays 4-connected: walkable without squeezing between two corners.
function carveTunnel(grid, width, height, from, to, radius) {
  let x = from % width;
  let y = Math.floor(from / width);
  const tx = to % width;
  const ty = Math.floor(to / width);
  const dx = Math.abs(tx - x);
  const dy = -Math.abs(ty - y);
  const sx = x < tx ? 1 : -1;
  const sy = y < ty ? 1 : -1;
  let err = dx + dy;
  while (true) {
    carveCircle(grid, width, height, x, y, radius);
    if (x === tx && y === ty) break;
    const e2 = 2 * err;
    if (e2 >= dy) { err += dy; x += sx; carveCircle(grid, width, height, x, y, radius); }
    if (e2 <= dx) { err += dx; y += sy; }
  }
}

function connectRooms(grid, width, height, rooms, radius = 1) {
  if (rooms.length < 2) return 0;
  const edges = rooms.map(room => room.filter(cell => isRoomEdge(grid, width, cell)));
  // Biggest cave first: it becomes the "mainland" every other cave joins.
  // (JavaScript's sort is stable, so equal sizes keep their order. That matters for determinism.)
  const order = rooms.map((room, i) => i).sort((a, b) => rooms[b].length - rooms[a].length);
  const connected = [order[0]];
  const pending = order.slice(1);
  let tunnels = 0;
  while (pending.length > 0) {
    // Find the closest pair of edge cells between ANY pending cave and ANY connected cave.
    let best = null;
    for (let p = 0; p < pending.length; p++) {
      for (const a of edges[pending[p]]) {
        for (const c of connected) {
          for (const b of edges[c]) {
            const d = distanceSquared(a, b, width);
            if (best === null || d < best.d) best = { d, a, b, p };
          }
        }
      }
    }
    // Dig it, then move that cave into the connected set.
    carveTunnel(grid, width, height, best.a, best.b, radius);
    connected.push(pending[best.p]);
    pending.splice(best.p, 1);
    tunnels++;
  }
  return tunnels;
}
/*
  Explanation:
  - Always connecting to the NEAREST cave keeps tunnels short and natural-looking.
  - This is Prim's minimum spanning tree in disguise: every cave ends up reachable.
  - radius 1 gives 3-wide tunnels; radius 0 gives 1-wide corridors.
  Next step: give the starting noise some structure with Perlin noise.
*/