Cellular Automata Cave Generation

Every floor so far has been the same kind of place — tidy BSP rooms joined by straight corridors. Act 3 opens by adding a second, completely different dungeon style: organic, twisting caverns, grown with a cellular automaton. And the satisfying part is how little of the game has to know: caves drop into the exact Level from Part 11, and the player, monsters, items and stairs carry on as if nothing changed.

How a Cellular Automaton Grows a Cave

The technique is almost magically simple. Start with random static, then repeatedly let each cell "vote" with its neighbours until the noise organises itself into blobs:

1. Seed with noise. Make each interior tile a wall about 45% of the time, floor otherwise. The border is always wall.
2. Smooth. Several times over, replace every tile using one rule: if 5 or more of its 8 neighbours are wall, it becomes wall; otherwise floor. Walls clump to walls, floors to floors, and the random fuzz coalesces into smooth caverns.
3. Connect. Smoothing can leave separate caverns, so flood-fill to find the largest connected region and turn everything else back to rock.

Noise, then the 4–5 rule

// 1. random noise
std::uniform_int_distribution<int> pct(0, 99);
for (int y = 0; y < MAP_HEIGHT; ++y)
    for (int x = 0; x < MAP_WIDTH; ++x)
    {
        bool border = (x == 0 || y == 0 || x == MAP_WIDTH - 1 || y == MAP_HEIGHT - 1);
        tiles[y][x].type = (border || pct(m_rng) < 45) ? TileType::Wall : TileType::Floor;
    }

// 2. smooth with the 4-5 rule, five passes
for (int iter = 0; iter < 5; ++iter)
{
    TileType next[MAP_HEIGHT][MAP_WIDTH];
    for (int y = 0; y < MAP_HEIGHT; ++y)
        for (int x = 0; x < MAP_WIDTH; ++x)
        {
            if (/* border */) { next[y][x] = TileType::Wall; continue; }
            int walls = 0;
            for (int dy = -1; dy <= 1; ++dy)
                for (int dx = -1; dx <= 1; ++dx)
                    if (!(dx == 0 && dy == 0) && tiles[y+dy][x+dx].type == TileType::Wall)
                        ++walls;
            next[y][x] = (walls >= 5) ? TileType::Wall : TileType::Floor;
        }
    // copy next back into tiles
}

Computing into a separate next grid and copying back at the end of each pass is essential: every cell must vote on the same snapshot. Update in place and tiles you've already changed would pollute their neighbours' counts, and you'd get mush instead of caves. Five passes is the sweet spot — fewer leaves it noisy, more rounds the caverns off into blobs.

Keeping the biggest cavern

A breadth-first flood from each unvisited floor tile collects connected regions; we keep the largest and wall off the rest, so the player can never spawn in a sealed pocket:

// ...BFS each region into `region`, track the biggest in `best`...
if (region.size() > best.size()) best.swap(region);
// ...then: every floor tile -> wall, and re-floor only the tiles in `best`.

The Trick That Makes It Drop In

Here's the bit worth stealing for your own projects. The entire rest of the game — player spawn, monster and item placement, the down-stairs — is written in terms of map.rooms. Caves don't have rooms. So rather than special-case caves everywhere, we make the cave generator fabricate a rooms list out of scattered floor tiles, each a 1×1 room:

auto mk = [](int x, int y) { Room r; r.x = x; r.y = y; r.w = 1; r.h = 1; return r; };

int spawnX = best[0].first, spawnY = best[0].second;
rooms.push_back(mk(spawnX, spawnY));                 // rooms[0] = spawn

for (int i = 1; i <= extra; ++i)                      // scattered points for monsters/items
    rooms.push_back(mk(best[i].first, best[i].second));

// the floor tile farthest from spawn becomes the down-stairs (rooms.back())
// ...find max Manhattan distance...
rooms.push_back(mk(fx, fy));

A 1×1 room reports its own tile as its centre and its only floor cell, so every line of placement code from earlier parts works verbatim — rooms[0] is still the spawn, rooms.back() is still the stairs, the middle entries still seed monsters and loot. This is the payoff of a stable interface: by conforming the new generator to the contract the old code already expected, caves cost zero changes anywhere else.

Choosing a Generator per Floor

With both generators conforming to the same contract, Level::generate picks between them on a whim — here, by parity of depth, so the dungeon alternates between built rooms and natural caves as you descend:

if (depth % 2 == 1) map.generateCaves();   // odd floors: caves
else                map.generate();         // even floors: BSP rooms
// ...the monster, item and stairs placement that follows is unchanged...

Try It

Build and run, then descend (>) past the first BSP floor. Floor 2 is a cavern — no straight walls, no rectangular rooms, just winding open rock that feels excavated rather than built. Field of view, the Dijkstra chase, fog of war and everything else behave exactly as before, because to the rest of the game a floor is just floor tiles and walls. Keep descending to feel the two styles trade off.

Notes on the Code

This part adds Map::generateCaves (declared in Map.h, implemented in Map.cpp) and the one-line generator choice in Level.cpp. Nothing else changes — that's the whole point. The full Map.cpp is in the repo.

Common Errors

What's Next

The series continues into the rest of Act 3 — ranged combat & magic, character classes, a save/load system, and finally UI polish & sound — before the win-condition finale. You now have two dungeon generators, deep scaling floors, items, equipment, status effects and a clean Game/Level architecture to hang all of it on. From here, the engine is ready for you to make it your own.