Dan Henry - Hobby Computer Scientist

PCG has always been fascinating to me. The obsession started in high school while playing Diablo 2 and being absolutely blown away by the idea that the world is randomly generated and is unique every time. Of course, PCG has come a long way since then when we look at games like Minecraft or Terraria. At any rate, it's something I have toyed with in the past and in an effort to get a handle on SDL2 a little better, I decided to create a cave generator using cellular automata.

Cellular Automata: Simple Rules, Complex Results

Cellular automata are a class of mathematical models that consist of a grid of cells, each in one of a finite number of states. The grid evolves in discrete time steps according to a set of rules based on the states of neighboring cells. They were first studied extensively by John von Neumann and Stanislaw Ulam in the 1940s, but gained popularity with John Conway's "Game of Life" in the 1970s.

What makes cellular automata fascinating is that despite having incredibly simple rules, they can produce remarkably complex patterns and behaviors. This emergent complexity makes them perfect for procedural generation in games.

The beauty of these systems is that you can create natural-looking structures without having to explicitly design them. Instead, you design rules that lead to the emergence of the structures you want.

Cave Generation Algorithm

The algorithm I'm implementing is basically just Conway's Game of Life modified slightly for cave generation:

Start with a 2D grid, randomly filled with walls and empty spaces
Apply a set of rules for several iterations:
- If a wall cell has too few neighboring walls, it becomes an empty space (simulating erosion)
- If an empty cell has too many neighboring walls, it becomes a wall (simulating formation)
After several iterations, cave-like structures naturally emerge

This creates a remarkably organic-looking cave system with chambers, tunnels, and interesting topography.

The Theory Behind It

Let's dig a bit deeper into why this works. In nature, caves form through complex processes involving water erosion, pressure, and geological movement. While we can't simulate all these physical processes efficiently, cellular automata provide a shortcut by creating similar patterns through simple neighbor-based rules.

Think of it as a simplified version of erosion and accretion:

Areas with few walls (isolated wall cells) tend to erode away
Empty spaces surrounded by walls tend to fill in
The process creates a balance of open chambers and connecting passages

The "magic" of cellular automata is that they create order from chaos through repeated application of local rules. Each cell only "knows" about its immediate neighbors, yet global patterns emerge.

The Implementation

I've implemented this in a single C file using SDL2 for rendering. Let's dive into the important parts of the code:

Data Structure

First, we need a 2D grid to represent our cave:

#define CAVE_WIDTH 100
#define CAVE_HEIGHT 75
 
typedef enum {
    CELL_EMPTY = 0,
    CELL_WALL = 1
} CellType;
 
CellType cave[CAVE_HEIGHT][CAVE_WIDTH];
CellType new_cave[CAVE_HEIGHT][CAVE_WIDTH];

Note that I'm using two grids here - cave and new_cave. This is because cellular automata rules should be applied to all cells simultaneously. If we updated cells in place, early changes would affect the neighborhood calculations for later cells. This technique is called "double buffering" and is common in games in general, but particularly in procedural generation.

Initialization

The cave starts with a random distribution of walls and empty spaces:

void initialize_cave() {
    // Reset step count
    step_count = 0;
 
    // Fill cave with random walls
    for (int y = 0; y < CAVE_HEIGHT; y++) {
        for (int x = 0; x < CAVE_WIDTH; x++) {
            // More walls around the edges
            if (x == 0 || y == 0 || x == CAVE_WIDTH-1 || y == CAVE_HEIGHT-1) {
                cave[y][x] = CELL_WALL;
            } else {
                // Random walls elsewhere
                cave[y][x] = (rand() % 100 < wall_chance) ? CELL_WALL : CELL_EMPTY;
            }
        }
    }
}

There are two important details here:

The edges of the cave are always walls. This boundary condition ensures that our cave doesn't "leak" into the void and provides a clean outer border.
The wall_chance parameter (default 45%) determines the initial density of walls. This is crucial because it affects the final cave structure dramatically. Too high (>60%), and you'll get mostly solid with small, disconnected chambers. Too low (< 30%), and you'll get mostly open space with few walls.

The initial state is crucial. Different starting configurations will evolve into different cave systems, even with the same rules. This is similar to how minor geological differences can lead to vastly different cave formations in the real world.

Counting Neighbors

The core of any cellular automaton is counting the neighbors. In this implementation, I'm using the Moore neighborhood (all 8 surrounding cells):

int count_wall_neighbors(int x, int y) {
    int count = 0;
 
    // Check all 8 surrounding cells
    for (int dy = -1; dy <= 1; dy++) {
        for (int dx = -1; dx <= 1; dx++) {
            // Skip the cell itself
            if (dx == 0 && dy == 0) continue;
 
            // Calculate neighbor coordinates
            int nx = x + dx;
            int ny = y + dy;
 
            // Check if neighbor is within bounds
            if (nx >= 0 && nx < CAVE_WIDTH && ny >= 0 && ny < CAVE_HEIGHT) {
                // Count if neighbor is a wall
                if (cave[ny][nx] == CELL_WALL) {
                    count++;
                }
            } else {
                // Treat out-of-bounds as walls
                count++;
            }
        }
    }
 
    return count;
}

An important subtlety here: I'm treating out-of-bounds cells as walls. This ensures that the cave doesn't grow outward indefinitely and maintains a solid boundary. It's similar to how Conway's Game of Life traditionally treats the universe as infinite but empty beyond the visible grid.

The Cellular Automata Rules

Now we come to the heart of the algorithm, where the actual rules are applied:

void update_cave() {
    // Apply cellular automata rules
 
    // Copy current state to new_cave
    for (int y = 0; y < CAVE_HEIGHT; y++) {
        for (int x = 0; x < CAVE_WIDTH; x++) {
            // First, make sure the edges stay as walls
            if (x == 0 || y == 0 || x == CAVE_WIDTH-1 || y == CAVE_HEIGHT-1) {
                new_cave[y][x] = CELL_WALL;
                continue;
            }
 
            // Count wall neighbors
            int wall_neighbors = count_wall_neighbors(x, y);
 
            // Apply rules
            if (cave[y][x] == CELL_WALL) {
                // Cell is currently a wall
                new_cave[y][x] = (wall_neighbors >= death_limit) ? CELL_WALL : CELL_EMPTY;
            } else {
                // Cell is currently empty
                new_cave[y][x] = (wall_neighbors > birth_limit) ? CELL_WALL : CELL_EMPTY;
            }
        }
    }
 
    // Swap caves
    for (int y = 0; y < CAVE_HEIGHT; y++) {
        for (int x = 0; x < CAVE_WIDTH; x++) {
            cave[y][x] = new_cave[y][x];
        }
    }
}

The core rules are these two lines:

// Cell is currently a wall
new_cave[y][x] = (wall_neighbors >= death_limit) ? CELL_WALL : CELL_EMPTY;
 
// Cell is currently empty
new_cave[y][x] = (wall_neighbors > birth_limit) ? CELL_WALL : CELL_EMPTY;

Let's break down what these mean:

Birth Rule: An empty cell becomes a wall if it has more than birth_limit wall neighbors. This simulates the formation of walls and growth in areas that are already surrounded by walls.
Death Rule: A wall cell remains a wall only if it has at least death_limit wall neighbors (default: 3). Otherwise, it becomes an empty space. This is pretty much erosion of walls that are standing by themselves.

These parameters can be adjusted to make sorts of consistent outcomes:

High birth limit with a low death limit ends up with more open space, smaller walls
Low birth limit with a high death limit ends up with more walls, smaller chambers
Equal birth and death limits ends up with stable, well-defined boundaries

After applying the rules to all cells, we swap the buffers to prepare for the next iteration. This is a critical step in cellular automata to ensure all cells are updated based on the same initial state.

The Evolution of the Cave

What's fascinating is how the cave evolves over time. Let me walk through what typically happens:

Iteration 0: Random noise (45% walls by default)
Iteration 1: Small clusters begin to form, isolated walls start to disappear
Iteration 2: Distinct chambers begin to take shape
Iteration 3: Chambers connect via tunnels, structure becomes clearer
Iteration 4-5: Fine details emerge, cave stabilizes

The algorithm exhibits a property called "convergence" - after a certain number of steps (usually 4-7), the cave structure mostly stabilizes. Additional iterations cause only minor changes. This is useful because it means we don't need to run the simulation indefinitely to get good results.

Parameter Exploration

One of the most interesting aspects of this algorithm is how dramatically the three main parameters affect the final cave structure:

1. Initial Wall Chance

This controls the density of walls in the initial random state:

30%: Creates very open caves with thin, wispy walls and large chambers
45% (default): Balanced caves with medium chambers and tunnels
60%: Mostly solid with small chambers and narrow tunnels

In code, this is controlled by the wall_chance variable:

cave[y][x] = (rand() % 100 < wall_chance) ? CELL_WALL : CELL_EMPTY;

2. Birth Limit

This controls how easily new walls form:

Low (3): Walls grow aggressively, creating more solid caves
Medium (4) (default): Balanced wall growth
High (5): Walls grow slowly, creating more open caves

3. Death Limit

This controls how easily existing walls erode:

Low (2): Walls erode easily, creating more open caves
Medium (3) (default): Balanced wall erosion
High (4): Walls persist more, creating denser caves

The interaction between these parameters creates a vast space of possible cave types. I've spent hours just tweaking parameters and watching the different structures emerge.

The Mathematics Behind It

For those interested in the mathematical properties, cellular automata like this one are examples of discrete dynamical systems. They exhibit several interesting properties:

Emergent complexity: Simple rules create complex structures
Self-organization: Ordered patterns emerge from random initial states
Phase transitions: Small parameter changes can dramatically alter the final structure
Attractor states: The system tends to converge toward stable configurations

These properties are shared with many natural systems, which is why cellular automata can create surprisingly natural-looking caves despite their simplicity.

Rendering with SDL2

The rendering part is straightforward - each cell is drawn as a filled rectangle with a color based on its type:

void render_cave(SDL_Renderer *renderer) {
    // Render cave cells
    for (int y = 0; y < CAVE_HEIGHT; y++) {
        for (int x = 0; x < CAVE_WIDTH; x++) {
            // Calculate cell position
            SDL_Rect cell_rect = {
                x * CELL_SIZE,
                y * CELL_SIZE,
                CELL_SIZE,
                CELL_SIZE
            };
 
            // Set cell color based on type
            if (cave[y][x] == CELL_WALL) {
                // Wall cells are gray
                SDL_SetRenderDrawColor(renderer, 100, 100, 100, 255);
            } else {
                // Empty cells are dark blue
                SDL_SetRenderDrawColor(renderer, 10, 10, 40, 255);
            }
 
            // Draw cell
            SDL_RenderFillRect(renderer, &cell_rect);
        }
    }
}

I chose a simple grayscale for walls and a dark blue for empty spaces to create a cave-like atmosphere. In a real game, you'd probably want to add more visual detail, like different wall types, water, stalactites, etc.

Interactive Controls

One of the best ways to understand how the algorithm works is to play with it interactively. I've added keyboard controls to adjust parameters on the fly:

case SDL_KEYDOWN:
    switch (event.key.keysym.sym) {
        case SDLK_SPACE:
            update_cave();
            step_count++;
            break;
        case SDLK_r:
            initialize_cave();
            break;
        case SDLK_a:
            auto_update = !auto_update;
            break;
        case SDLK_UP:
            wall_chance = (wall_chance < 90) ? wall_chance + 5 : 90;
            break;
        case SDLK_DOWN:
            wall_chance = (wall_chance > 10) ? wall_chance - 5 : 10;
            break;
        // ...more controls
    }

This lets you see in real-time how changing parameters affects the cave generation.

Limitations and Potential Improvements

While this algorithm creates nice-looking caves, it has some limitations:

Disconnected chambers: The basic algorithm doesn't guarantee that all chambers are connected. In a real game, you'd want to use a flood fill algorithm to ensure all areas are reachable.
Uniform distribution: The caves don't have large-scale features like major chamber clusters or long winding tunnels. This could be improved by adding biases to the initial distribution.
No variation in cave types: All caves look similar in character. A more sophisticated system might use different parameter sets for different regions.

Here's how you might implement a flood fill to identify and potentially connect disconnected chambers:

// Pseudocode for flood fill
void flood_fill(int start_x, int start_y) {
    if (cave[start_y][start_x] == CELL_WALL) return;
    if (visited[start_y][start_x]) return;
 
    visited[start_y][start_x] = true;
    connected_cells++;
 
    // Recurse for all four adjacent cells
    flood_fill(start_x+1, start_y);
    flood_fill(start_x-1, start_y);
    flood_fill(start_x, start_y+1);
    flood_fill(start_x, start_y-1);
}

After running the cellular automata, you would run this flood fill from a starting point, then check if connected_cells equals the total number of empty cells. If not, you'd need to create connections between disconnected regions.

Compilation and Running on macOS (ARM)

To compile this on macOS with an ARM chip (like M1/M2), you'll need to install SDL2 using Homebrew:

bash

# Install Homebrew if you don't have it
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"
 
# Install SDL2
brew install sdl2
 
# Compile
clang -o cave_generator cave_generator.c -I/opt/homebrew/include -L/opt/homebrew/lib -lSDL2
 
# Run
./cave_generator

Note that on ARM Macs, Homebrew installs packages to /opt/homebrew instead of the Intel Mac location of /usr/local.

Real-World Applications

This is pretty widely used, and is a well known algorithm. A search on YouTube would yield a shitload of results going far more in-depth than this post does. Some 'famous' examples would be:

Dwarf Fortress: Makes extensive use of more complex versions of cellular automata (and several other PCG algorithms) for generating diverse underground structures and a rich world.
Terraria: Uses of cellular automata for the cave systems, just like we did here.
Minecraft uses a combination of noise functions and cellular automata-like processes

The same principles can be applied to other procedural generation tasks:

Island and coastline generation
Forest and vegetation distribution
Urban layout planning

Final Thoughts

I've always found procedural generation fascinating because it's the perfect intersection of randomness and structure. With just a few simple rules, we can create complex, natural-looking environments that are different every time.

What's particularly interesting about cellular automata is how they parallel natural processes. In nature, complex structures emerge from simple, local interactions following basic physical laws. Our cave generator mimics this with simple neighbor-based rules, creating emergent complexity from simplicity.

This project was a nice way to get back into C programming and learn a bit about cellular automata in the process. The code is quite simple - under 400 lines - but creates surprisingly complex and interesting caves.

When I get the itch again, I might try extending this a little bit further. Here are some of the things I wish I would have had time to try:

multiple cave layers with connecting staircases
Multiple "biomes" with different parameters or settings in each biome.
Adding in some actual game elements. Sprites, characters, pickups, whatever.

For anyone interested, the code is here:[https://github.com/danhenrydev/cellular-automata].

Procedural Cave Generation with C and SDL2