Procedural Level Generation: 2D Cellular Automata, Perlin Noise & Tilemap Baking

Cellular Automata: Simulating Organic Caverns

While dungeon crawlers often employ Binary Space Partitioning (BSP) to carve rectangular rooms connected by straight corridors, organic environments—such as limestone caves, alien hives, and volcanic caverns—require non-Euclidean geometries. The gold standard methodology is Cellular Automata, originally inspired by Conway's Game of Life.

The classic cave generation algorithm operates through a 4-5 Rule evaluated over a discrete 2D grid:

1. Initial Random Seeding: Allocate a grid of dimensions $W imes H$. Each tile is populated as a solid rock wall with an initial fill probability (typically between 42% and 48%). Border tiles are permanently flagged as impassable walls.
2. Neighborhood Evaluation: For each cell $(x, y)$, query its 8 surrounding neighbors in the Moore neighborhood.
3. State Transition:
   • If a cell has $ge 5$ wall neighbors, it becomes (or remains) a solid wall.
   • If a cell has $le 3$ wall neighbors, it dissolves into open floor.
   • If a cell has exactly 4 wall neighbors, it maintains its previous state.
4. Iterative Smoothing: Executing this rule across 4 to 6 sequential generations converts noisy static into sweeping, natural subterranean chambers with smooth cavern walls.

export class CaveGenerator {
  public static generate(width: number, height: number, fillProb: number = 0.45, steps: number = 5): Uint8Array {
    let map = new Uint8Array(width * height);

    // Initial random distribution
    for (let i = 0; i < map.length; i++) {
      const x = i % width;
      const y = Math.floor(i / width);
      if (x === 0 || x === width - 1 || y === 0 || y === height - 1) {
        map[i] = 1; // Immutable border walls
      } else {
        map[i] = Math.random() < fillProb ? 1 : 0;
      }
    }

    // Iterative 4-5 cellular automata simulation
    for (let s = 0; s < steps; s++) {
      const nextMap = new Uint8Array(map);
      for (let y = 1; y < height - 1; y++) {
        for (let x = 1; x < width - 1; x++) {
          let wallCount = 0;
          for (let dy = -1; dy <= 1; dy++) {
            for (let dx = -1; dx <= 1; dx++) {
              if (dx === 0 && dy === 0) continue;
              if (map[(y + dy) * width + (x + dx)] === 1) wallCount++;
            }
          }

          const idx = y * width + x;
          if (wallCount > 4) nextMap[idx] = 1;
          else if (wallCount < 4) nextMap[idx] = 0;
        }
      }
      map = nextMap;
    }

    return map;
  }
}

Guaranteeing Playability: Flood-Fill Connectivity & Corridor Carving

A major challenge with Cellular Automata is that it frequently generates closed pockets—inaccessible sub-chambers separated by thick rock formations. If player spawn points or critical quest items generate inside disconnected chambers, the level becomes mathematically unplayable.

To guarantee 100% navigability, the engine executes a Flood-Fill Graph Traversal:

1. The flood-fill algorithm scans the grid, grouping contiguous open floor tiles into indexed region lists: Room 1, Room 2, ... Room N.
2. The largest single room is designated as the primary play space. Small pocket rooms below a minimum threshold (e.g. < 20 tiles) are filled back in with solid rock to eliminate useless clutter.
3. For any remaining valid rooms, the engine calculates the closest pair of floor coordinates between room boundaries and runs a tunnel borer algorithm (a 2-tile wide Bresenham line or random walk corridor), punching through rock until all rooms coalesce into a single unified topological graph.

Surface Topography: Perlin Noise & Fractal Brownian Motion

For exterior wilderness maps, islands, and planetary surfaces, cellular automata is replaced with coherent gradient noise: Perlin Noise or Simplex Noise.

A single octave of noise produces smooth, predictable elevation curves. To simulate natural mountains, coastlines, and craggy cliffs, the engine sums multiple noise layers using Fractal Brownian Motion (fBm):

elevation = sum_{i=0}^{ ext{octaves}-1} ext{amplitude}_i cdot ext{noise}( ext{frequency}_i cdot x, ext{frequency}_i cdot y)

Each successive octave doubles the frequency (increasing detail frequency) while halving the amplitude (decreasing structural influence). By generating two decoupled fBm noise maps—one for Elevation and one for Moisture—the engine constructs a Whittaker Biome Diagram in code, procedurally painting deserts, rainforests, tundra, and temperate grasslands onto the tile grid.

Autotiling Bitmasking: From Binary Grids to Rich Visuals

A raw procedural generator yields a flat binary array: 0 for floor, 1 for wall. Manually selecting which corner, wall face, or edge sprite to render would require hundreds of tedious conditional checks.

Autotiling Bitmasking automates this completely. The engine evaluates neighboring cells and constructs an integer bitmask. In the canonical 4-bit Cardinal Bitmask:

• North neighbor = $1$ ($2^0$)
• West neighbor = $2$ ($2^1$)
• East neighbor = $4$ ($2^2$)
• South neighbor = $8$ ($2^3$)

Summing the active neighbor values produces an index from $0$ to $15$. This integer maps directly to a 16-tile sprite sheet (e.g., $15$ represents an isolated wall pillar with neighbors on all four sides, while $0$ represents a free-standing single block). For advanced visuals with inner and outer corners, an 8-bit / 47-tile bitmask evaluates diagonal corners, ensuring seamless transition aesthetics.

Performance Optimization: Offscreen Tilemap Baking

In a large 2D world (e.g. 512x512 tiles = 262,144 tiles), rendering every tile individually inside the requestAnimationFrame loop issues hundreds of thousands of draw operations, collapsing browser performance.

Production web game engines resolve this by Chunk Baking:

• The world is divided into $32 imes 32$ tile chunks.
• Static layers (ground terrain, wall facades) are pre-rendered once onto an offscreen HTMLCanvasElement or an allocated GPU frame buffer.
• During active gameplay, the renderer simply draws the few baked chunk textures currently intersecting the camera viewport, reducing draw calls from 250,000+ down to under 10 draw calls per frame.

Comparative Architectural Matrix: 2D Procedural Generation

Comparing procedural generation algorithms for 2D game development:

Conclusion

Procedural content generation empowers web game developers to build infinitely expandable worlds with compact file downloads. By mastering Cellular Automata for subterranean caverns, Fractal Brownian Motion for rich surface biomes, and Autotile Bitmasking for automated rendering, engineers create dynamic, captivating interactive environments that run smoothly at 60 FPS in modern browsers.