Caves

Every floor so far has been rooms and corridors, carved out of solid rock by Chapter 2's generator. They're good floors to fight on, with doorways to hold and corners to wait behind, but they all have the same look: rectangles, joined by straight lines. This chapter adds a second kind of floor, a cave. It's grown rather than carved, with walls that wander, and open chambers joined by narrow throats.

The caves come from a cellular automaton. The map starts as random noise, about half wall and half floor. Then one simple rule is applied to every cell at once, a few times over.

On each pass, a cell looks at its neighbors, and becomes wall or floor by how many walls it sees. A few passes later, the noise has clumped into caves. The next image shows the fourth floor, which is a cave by the end of the chapter.

The cave's floor is earth, where a room's is laid stone. Its monsters are spread through it rather than shut in rooms. Floors 4 and 7 are caves, and the rest are rooms, as before. Along the way, a new debugging key, F6, shows a cave being made a step at a time, so you can watch the rule at work.

In this chapter, we will:

• Add a new kind of floor, a cave's earth, to the map and to both views
• Fill a map with random walls, and look at the noise on a new debugging key
• Smooth the noise into caves with the 4-5 rule, a pass at a time
• Keep the biggest cave, so that all of it can be reached, and find where the player starts and where the stairs go
• Make floors 4 and 7 caves, with their monsters, items and gold on the ground

There are four checkpoints along the way. Let's start with the plan.

Planning the Chapter

This chapter adds two files, and changes eight, along with the tile atlas:

The next image shows how the files fit together at the end of the chapter. The new CaveGen is a second generator, beside RoomGen. It fills a Map using the dice, just as RoomGen does. For each floor, Game asks one or the other. The dungeon's column is full, so the new generator sits below the views, beside DijkstraMap.

Both generators hand back the same thing: places to put monsters and items in. For RoomGen, they're rooms, rectangles of floor. A cave has no rooms, so CaveGen gives areas, the squares of a grid laid over the map that hold enough of the cave. The code that places monsters, items and gold works on areas, whichever kind of floor they're on.

How a Cave Grows

A cellular automaton is a grid of cells and a rule. Every cell follows the rule at once, looking only at the cells around it. Here, the cells are the map's, and each is wall or floor. The rule is simple enough to say in one sentence: a cell becomes wall if five or more of the nine cells in the 3 x 3 block around it, itself included, are walls, and floor if four or fewer are. The next image shows it at work on a few cells.

It's called the 4-5 rule because of what it means for the cell in the middle. A wall stays a wall if four or more of its eight neighbors are walls, since it makes five with itself. And a floor cell becomes a wall only if five of its neighbors are. Walls in a crowd stay, and stray walls in the open crumble, while gaps in the middle of a mass of rock fill in.

Run over random noise, the rule clumps it. Each pass, the crowded parts get more crowded and the open parts more open. After four passes, the map is caves: rounded chambers of floor, joined where the noise happened to leave a way through.

A New Kind of Floor

The first part of the chapter gets the map ready for caves, and shows the noise they grow from. A cave's floor is a terrain of its own. So every part of the game that asks about terrain has to know it: what can be walked on, how it's drawn, and what the look panel calls it. At its checkpoint, a new debugging key, F6, fills a map with noise and shows it.

Earth, Not Stone

A cave's floor is walked on just as a room's is, but it's earth rather than laid stone, and it looks different. Open Map.h, and replace the comment above enum class Terrain with this:

// What a cell of the map is made of. A cave's floor is earth, where a
// room's is laid stone, but they're walked on the same way

Then add the new terrain below StairsDown,:

CaveFloor,

The new terrain goes at the end, so the ones before it keep their numbers. A cave floor can be walked on, and isWalkable should say so. Replace the comment above bool isWalkable with this:

// True for terrain that can be walked on: floor, cave floor, and the
// stairs

Open Map.cpp, and in isWalkable, find this line:

return terrain == Terrain::Floor || terrain == Terrain::StairsDown;

Change it to these:

return terrain == Terrain::Floor || terrain == Terrain::CaveFloor ||
       terrain == Terrain::StairsDown;

Everything that asks isWalkable, from the player's steps to the monsters' Dijkstra maps, now treats a cave's floor as floor, with no other change.

The glyph view draws a cave floor as a dot, as it draws a room's, but in a brown, the color of earth. Open Common.h, and add the color to the palette, below FLOOR:

constexpr SDL_Color CAVE_FLOOR = { 125, 100, 70, 255 };

Open GlyphView.cpp, and in drawTerrain, add the cave floor's branch below the floor's:

else if (terrain == Terrain::CaveFloor)
{
    // Earth, in a brown that's dimmed to the same memory color
    SDL_Color color = lit ? Palette::CAVE_FLOOR : Palette::MEMORY_FLOOR;
    drawCell(cell, '.', color);
}

A cave floor out of sight is drawn in the same memory color as a room's floor. Remembered ground is all one dim blue, whatever it's made of, so the brown is a sign that the cell is in sight.

Dirt in the Tile View

The tile view needs a picture of dirt. From the book's repository, copy tiles.png and tiles.txt from the Chapter 18 folder's assets folder into your project's assets folder, in place of the old ones. They add a tile called dirt.

The dirt tile is bright and busy, which is fine for a tile on its own, but too loud for a whole floor of them. Monsters on it were hard to pick out, and the brown ones, such as the cave spider, nearly vanished. So the tile view draws it darker, with a tint, as it already tints what's remembered. Open TileView.cpp, and add these to the unnamed namespace, below NO_TINT:

// The dirt tile is bright and busy for a floor, so a cave's floor is
// drawn darker, and what stands on it stays easy to see
constexpr SDL_Color DIRT_TINT = { 150, 140, 130, 255 };

// A tint, with the memory's tint on top of it, for something
// remembered: the two are multiplied, as color mods multiply
SDL_Color remembered(SDL_Color tint)
{
    tint.r = static_cast<Uint8>(tint.r * Palette::MEMORY_TINT.r / 255);
    tint.g = static_cast<Uint8>(tint.g * Palette::MEMORY_TINT.g / 255);
    tint.b = static_cast<Uint8>(tint.b * Palette::MEMORY_TINT.b / 255);
    return tint;
}

The function remembered puts the memory's tint on top of another tint. It multiplies them, as SDL_SetTextureColorMod's tints multiply with a texture's own colors. The items' drawing did this already, with these same three lines. Now the dirt needs it too, so it's a function that both can call. Replace the whole of drawTerrain with this:

// Remembered cells are tinted, which darkens and cools them, as the glyph
// view's memory colors do. The stairs' tile is see-through around its
// edges, so a floor is drawn under it first
void TileView::drawTerrain(Point cell, Terrain terrain, bool lit) const
{
    const char* name = "wall";
    SDL_Color tint = NO_TINT;
    if (terrain == Terrain::Floor)
    {
        name = "floor";
    }
    else if (terrain == Terrain::CaveFloor)
    {
        name = "dirt";
        tint = DIRT_TINT;
    }
    else if (terrain == Terrain::StairsDown)
    {
        drawTile(cell, "floor", lit ? NO_TINT : remembered(NO_TINT));
        name = "stairs";
    }
    drawTile(cell, name, lit ? tint : remembered(tint));
}

In the preceding code, each kind of ground chooses a tile and a tint, and remembered darkens the tint for a cell out of sight. The stairs' floor is drawn the same way, so remembered stairs still sit on remembered floor. Now the items can use remembered too, and their comment gets shorter. Replace the whole of drawItem with this:

// An item's tile is tinted with its color, if it takes one
void TileView::drawItem(Point cell, const ItemLook& look, bool lit) const
{
    SDL_Color tint = look.tinted ? look.color : NO_TINT;
    drawTile(cell, look.tile, lit ? tint : remembered(tint));
}

Remembered items and remembered earth are darkened by the same function now, so the two can never drift apart.

What the Look Panel Calls It

The look panel names the ground under the mouse, and a cave floor would otherwise be called a wall, the panel's name for anything it doesn't know. Open Game.cpp, and in drawLookPanel, add this branch below the floor's:

else if (terrain == Terrain::CaveFloor)
{
    ground = "The cave floor";
}

Nothing in the game makes a cave floor yet, so none of this shows. That's next.

The Random Fill

A cave starts as noise. Every cell inside the map's edge is wall or floor at random, with a little under half of them wall. The edge itself is all wall, so nothing can walk off the map.

A Generator of Caves

The caves get a generator of their own, beside RoomGen. Add a Header File (.h) called CaveGen.h, and type it in:

#pragma once
#include "Map.h"
#include "Rng.h"

// Builds a floor of caves with a cellular automaton. The map starts as
// random wall and floor, and is then smoothed, again and again, by one rule
// that every cell follows at once, until it looks like caves
namespace CaveGen
{
    // How much of the map starts as wall, in percent (*tune*)
    constexpr int WALL_PERCENT = 48;

    // Makes each cell inside the map's edge a wall WALL_PERCENT of the
    // time, and cave floor the rest. The edge is all wall
    void fillRandomly(Map& map, Rng& rng);
}

The generator, CaveGen, is a namespace rather than a class, as RoomGen is. It keeps nothing between calls: each function takes the map it works on. The wall percentage, WALL_PERCENT, is 48. Its comment calls it *tune*, as the book marks every number that was chosen by trying it. Why 48 matters is clearer once the caves are smoothed, later in the chapter.

Add a C++ File (.cpp) called CaveGen.cpp, and type it in:

#include "CaveGen.h"

void CaveGen::fillRandomly(Map& map, Rng& rng)
{
    map.fill(Terrain::Wall);
    for (int y = 1; y < MAP_H - 1; ++y)
    {
        for (int x = 1; x < MAP_W - 1; ++x)
        {
            if (rng.roll(1, 100) > WALL_PERCENT)
            {
                map.set(x, y, Terrain::CaveFloor);
            }
        }
    }
}

The map is filled with wall first, and then each cell inside the edge rolls from 1 to 100. A roll over WALL_PERCENT makes the cell cave floor. So, on average, 52 cells in 100 become floor, and 48 stay wall. The loops start at 1 and stop one short of the edge, so the outermost ring of cells is never touched.

A Look on F6

A new debugging key, F6, will show a cave being made: the noise first, and later each smoothing pass. It's F6, not F5, because F5 is Visual Studio's key for starting the game. The cave it shows is made in a map of its own, with dice of its own, so looking at caves changes nothing in the run. Open Game.h, and add the key's function below switchView's declaration:

void stepCave();

Then add its drawing below drawMinds's declaration:

void drawCaveSteps() const;

The cave being shown, while it's showing, is kept in a member. Add it below showMinds_:

// The debugging aid on F6: a cave being made, while it's showing.
// cavesShown_ counts the caves, for their dice
struct CaveSteps
{
    Map map;
};
std::optional<CaveSteps> caveSteps_;
int cavesShown_ = 0;

A struct, CaveSteps, holds the cave's map, and will soon hold more about the cave as well. The struct is in a std::optional, so it's there only while F6's cave is showing, and empty the rest of the time. And cavesShown_ counts the caves shown, which the key's function needs for its dice.

Open Game.cpp, and add the generator's header below #include <sstream>:

#include "CaveGen.h"

Then add the key to handleKey, below F1's:

if (key.key == SDLK_F6)
{
    // A debugging aid: F6 shows a cave being made, a step at a time
    if (!key.repeat)
    {
        stepCave();
    }
    return;
}

The key's function makes a cave on its first press, and puts the game back on the next. Add it below handleKey:

// F6 shows a cave being made: the random fill, and then the game again.
// The cave has dice of its own, from the run's seed and how many caves
// have been shown, so looking changes nothing in the run, and the same
// seed shows the same caves
void Game::stepCave()
{
    if (!caveSteps_)
    {
        Rng dice(seed_ + cavesShown_);
        ++cavesShown_;
        caveSteps_ = CaveSteps();
        CaveGen::fillRandomly(caveSteps_->map, dice);
    }
    else
    {
        caveSteps_.reset();
    }
    redraw_ = true;
}

The cave's dice start from the run's seed plus the number of caves shown so far. So each press of F6 shows a new cave, and the same seed shows the same caves in the same order. They're dice of their own, not rng_, so the run's own rolls are untouched. The game plays on exactly as it would have. Assigning CaveSteps() to the optional makes a fresh one, with a map full of wall, and reset empties it again.

While a cave is showing, it takes the map view's place. In draw, find these lines:

drawMap();
if (showDistances_)
{
    drawDistances();
}
drawItems();
drawMonsters();
view_->drawPlayer(player_.pos);
if (showMinds_)
{
    drawMinds();
}
std::optional<Point> target = lookTarget();
if (target)
{
    drawHighlight(*target);
}

Change them to these:

if (caveSteps_)
{
    // The cave being made on F6 has the map view to itself
    drawCaveSteps();
}
else
{
    drawMap();
    if (showDistances_)
    {
        drawDistances();
    }
    drawItems();
    drawMonsters();
    view_->drawPlayer(player_.pos);
    if (showMinds_)
    {
        drawMinds();
    }
    std::optional<Point> target = lookTarget();
    if (target)
    {
        drawHighlight(*target);
    }
}

In the preceding code, the old lines go inside an else, one step further in. The cave being made takes their place while F6 is showing one. Add the cave's drawing below drawMap:

// The F6 debugging aid: the cave being made, every cell of it, lit, and
// every wall too, so the random fill can be seen for what it is
void Game::drawCaveSteps() const
{
    for (int y = 0; y < MAP_H; ++y)
    {
        for (int x = 0; x < MAP_W; ++x)
        {
            view_->drawTerrain({ x, y }, caveSteps_->map.at(x, y), true);
        }
    }
}

Every cell of the cave is drawn lit, walls and all, through whichever view is in use. So the noise can be seen for what it is. The side panel says what's showing, as it does for the other debugging aids. In drawSidePanel, add these lines below F3's reminder:

if (caveSteps_)
{
    std::string step = "the random fill";
    y += row;
    glyphs_.drawText("DEBUG: a cave (F6)", x, y, Palette::DEBUG);
    y += row;
    glyphs_.drawText(step, x, y, Palette::DEBUG);
}

Checkpoint: Press F5 to start the game, and press F6 in its window. The map view fills with noise, about half # and half brown dots, and the side panel says the random fill. The next image shows it.

Press F6 again, and the game is back, exactly as it was. One more press, and a different fill appears, since each cave's dice start one further on. Try the tile view too, with F2: the dirt is darker than a room's floor, but the noise is just as noisy.

Smoothing

The noise becomes caves by the 4-5 rule, applied to every cell, four times over. This part writes the rule, and lets F6 show each pass.

The 4-5 Rule

Open CaveGen.h. The number of passes is the second number that's chosen by trying it. Replace the comment above constexpr int WALL_PERCENT = 48; with this:

// How much of the map starts as wall, in percent, and how many times
// it's smoothed (both *tune*)

Then add the number of passes below WALL_PERCENT:

constexpr int SMOOTHING_PASSES = 4;

And add the smoothing's declaration below fillRandomly's:

// One smoothing pass, by the 4-5 rule: a cell becomes wall if 5 or
// more of the 9 cells in the 3 x 3 block around it, itself included,
// are walls, and floor if 4 or fewer are. Every cell is decided from
// the map as it was before the pass, never from one half changed
void smooth(Map& map);

Open CaveGen.cpp, and add the smoothing below fillRandomly:

// Counting the cell itself is what makes this the 4-5 rule: a wall stays a
// wall with 4 walls around it (5 in the block), and a floor cell becomes a
// wall with 5 around it. The edge isn't changed, so it stays wall
void CaveGen::smooth(Map& map)
{
    Map before = map;
    for (int y = 1; y < MAP_H - 1; ++y)
    {
        for (int x = 1; x < MAP_W - 1; ++x)
        {
            int walls = 0;
            for (int dy = -1; dy <= 1; ++dy)
            {
                for (int dx = -1; dx <= 1; ++dx)
                {
                    if (before.at(x + dx, y + dy) == Terrain::Wall)
                    {
                        ++walls;
                    }
                }
            }
            map.set(x, y, walls >= 5 ? Terrain::Wall : Terrain::CaveFloor);
        }
    }
}

In the preceding code, the two inner loops count the walls in the 3 x 3 block around each cell, the cell itself included. The edge is skipped, as in the fill, so it stays wall. And every cell the loops look at has eight neighbors on the map.

Design note: the 4-5 rule. The rule comes from a RogueBasin article on making cave-like levels with cellular automata, whose C code is credited to Jim Babcock. It puts the rule both ways, as above. Starting from 45% walls, the article found the plain rule could leave one huge open space, or caves cut off from each other.

The article's own answer is a second rule for the first few passes. Ours keeps the plain rule, but starts from 48% walls, which is enough to leave chambers and throats rather than one open hall. The next part of the chapter deals with the caves cut off from each other.

Every Cell at Once

The smoothing begins with a copy, Map before = map;, and every count is taken from the copy, never from the map being changed. That's what "every cell at once" means. Without the copy, the loops would count walls that this very pass had just made, a row above or a cell to the left. So the walls would spread across and down the map in the order the loops happen to visit it. The next image shows the difference, on the same fill.

The map is 64 cells by 36, so the copy is just over two thousand cells, made four times for a cave. That's nothing to a computer, and it's the price of a rule that treats every cell alike.

A Pass at a Time on F6

F6 can show each pass in turn, if it knows which step it's at. Open Game.h, and replace the comment above struct CaveSteps with this:

// The debugging aid on F6: a cave being made, while it's showing, and
// the step it's at: 0 for the random fill, then each smoothing pass.
// cavesShown_ counts the caves, for their dice

Then add the step below Map map;:

int step = 0;

Open Game.cpp, and replace the comment above stepCave with this:

// F6 shows a cave being made, a step at a time: the random fill, then
// each smoothing pass in turn, and then the game again. The cave has dice
// of its own, from the run's seed and how many caves have been shown, so
// looking changes nothing in the run, and the same seed shows the same
// caves

Then, in stepCave, find these lines:

    CaveGen::fillRandomly(caveSteps_->map, dice);
}
else

Change them to these:

    CaveGen::fillRandomly(caveSteps_->map, dice);
}
else if (caveSteps_->step < CaveGen::SMOOTHING_PASSES)
{
    CaveGen::smooth(caveSteps_->map);
    ++caveSteps_->step;
}
else

Each press after the fill runs one smoothing pass and counts it, until all four have run. The next press puts the game back. The side panel should say which step it's at. In drawSidePanel, add this below std::string step = "the random fill";:

if (caveSteps_->step > 0)
{
    step = "smoothing pass " + std::to_string(caveSteps_->step) +
           " of " + std::to_string(CaveGen::SMOOTHING_PASSES);
}

Checkpoint: Press F5 to start the game, and press F6 in its window, five times, slowly. The first press shows the noise, and each press after it smooths it, smoothing pass 1 of 4 to smoothing pass 4 of 4. The next image shows the noise and three of the passes.

The first pass does most of the work. It changes over a third of the map's cells, and the noise becomes blobs. Each pass after it rounds the blobs off, and changes fewer cells. On average, that's nearly 300 on the second, over 100 on the third, and under 60 on the fourth. Press F6 once more for the game, and again for a new cave.

One Cave

The smoothed map is caves, plural. Some of them are cut off from the rest, by walls that the rule closed. A player who starts in one couldn't reach another, nor the stairs, if they're there. This part keeps only the biggest cave, divides it into areas for monsters and items, and finds where the player starts and where the stairs go.

Keeping the Biggest Cave

The way to find the caves is a flood fill, the paint bucket of a drawing program. It starts at one floor cell, and spreads to every floor cell next to it, and to every one next to those, until it can spread no further. Everything it reached is one cave. Start another fill from a floor cell that isn't in a cave yet, and it finds the next one, and so on, until every floor cell is in a cave.

Open CaveGen.h, and add these below #pragma once:

#include <SDL3/SDL.h>
#include <vector>   // std::vector, for the areas

Then add the new numbers below SMOOTHING_PASSES:

// The fewest cells the biggest cave may have. A floor whose biggest
// cave is smaller is made again (*tune*)
constexpr int MIN_CAVE_CELLS = 600;

// Monsters and items are placed in areas, as they are in rooms: the
// squares of an AREA_W by AREA_H grid over the map that hold at least
// MIN_AREA_CELLS of the cave
constexpr int AREA_W = 16;
constexpr int AREA_H = 12;
constexpr int MIN_AREA_CELLS = 40;

And add the new functions' declarations below smooth's:

// Keeps the biggest cave: the floor cells that can all be walked to
// from one another. Every other floor cell becomes wall. Returns how
// many cells it kept
int keepBiggestCave(Map& map);

// The areas that hold enough of the cave, from the top left, row by
// row, as RoomGen gives its rooms
std::vector<SDL_Rect> areasOf(const Map& map);

// A whole floor of caves: filled, smoothed, and its biggest cave kept.
// It's made again if that cave is too small, or too squeezed to give
// two areas, one for the player to start in and one for monsters.
// Returns the areas; the player starts in the first
std::vector<SDL_Rect> generate(Map& map, Rng& rng);

Open CaveGen.cpp, and add the first part of the flood fill below smooth:

// A flood fill from each floor cell that isn't in a cave yet finds the
// cave it's in: the fill spreads to every walkable neighbor, the diagonals
// too, since a step can go that way, and every cell it reaches is in the
// same cave. Then every cell outside the biggest cave becomes wall
int CaveGen::keepBiggestCave(Map& map)
{
    // Each cell's cave, numbered from 0, or -1 for none yet, and each
    // cave's size
    std::vector<int> caveOf(MAP_W * MAP_H, -1);
    std::vector<int> sizes;
    for (int y = 0; y < MAP_H; ++y)
    {
        for (int x = 0; x < MAP_W; ++x)
        {
            if (!map.isWalkable(x, y) || caveOf[y * MAP_W + x] != -1)
            {
                continue;
            }
            int cave = static_cast<int>(sizes.size());
            int size = 0;
            caveOf[y * MAP_W + x] = cave;
            std::vector<Point> toVisit = { { x, y } };

In the preceding code, caveOf holds a number for every cell of the map: the number of its cave, or -1 while it hasn't been reached. The map is a grid, but the vector is a single row of cells. So a cell's place in it is y * MAP_W + x, row by row. Each floor cell that isn't in a cave yet starts a new one, numbered by how many caves there are so far, with the cell itself as the first to visit.

Add the fill itself below it:

        while (!toVisit.empty())
        {
            Point cell = toVisit.back();
            toVisit.pop_back();
            ++size;
            for (Point step : DIRECTIONS)
            {
                Point next = { cell.x + step.x, cell.y + step.y };
                if (map.isWalkable(next.x, next.y) &&
                    caveOf[next.y * MAP_W + next.x] == -1)
                {
                    caveOf[next.y * MAP_W + next.x] = cave;
                    toVisit.push_back(next);
                }
            }
        }
        sizes.push_back(size);
    }
}

The vector toVisit holds the cells the fill has reached but not yet spread from. Each time around, one comes off the end, is counted, and spreads the fill to its walkable neighbors that aren't in a cave yet. It marks them as it goes, so no cell is visited twice.

The fill spreads in all eight directions, from DIRECTIONS, since a step can go diagonally. So two chambers that touch only at a corner are one cave. When nothing is left to visit, the cave's size is kept.

Add the rest of the function below:

    if (sizes.empty())
    {
        return 0;
    }

    int biggest = 0;
    for (int cave = 1; cave < static_cast<int>(sizes.size()); ++cave)
    {
        if (sizes[cave] > sizes[biggest])
        {
            biggest = cave;
        }
    }
    for (int y = 0; y < MAP_H; ++y)
    {
        for (int x = 0; x < MAP_W; ++x)
        {
            if (map.isWalkable(x, y) && caveOf[y * MAP_W + x] != biggest)
            {
                map.set(x, y, Terrain::Wall);
            }
        }
    }
    return sizes[biggest];
}

In the preceding code, the biggest cave is the one with the most cells, and every floor cell in any other cave becomes wall. A map with no floor at all keeps nothing, and says so with 0.

Design note: Angband's caverns. Angband makes cavern levels with a cellular automaton too, in its gen-cave.c. It opens only a quarter to two fifths of the level at first, and smooths it three to six times. Its rule has a gap in its middle: a square with more than five rock neighbors becomes rock, one with fewer than four becomes floor, and one with four or five stays as it was. Every square is decided from a copy, as ours is. Pockets of fewer than nine squares are filled in, and the rest are joined by tunnels, rather than thrown away.

Joining keeps every pocket for the player to explore, at the cost of tunnels cut through the rock, which a cave wouldn't have. Keeping the biggest cave costs some floor, and the cave that's left is all of a piece.

Areas to Put Things In

Monsters and items go in rooms, and a cave has none. So the cave is divided into areas, the squares of a grid laid over the map, 16 cells by 12. A square that holds at least 40 cells of the cave is an area, and one that's mostly rock isn't. The next image shows the areas of a cave.

The areas come as a vector of SDL_Rects, as RoomGen's rooms do. They're in order from the top left, row by row. The player starts in the first, as in the first room. Add the first part of areasOf below keepBiggestCave:

std::vector<SDL_Rect> CaveGen::areasOf(const Map& map)
{
    std::vector<SDL_Rect> areas;
    for (int top = 0; top < MAP_H; top += AREA_H)
    {
        for (int left = 0; left < MAP_W; left += AREA_W)
        {
            SDL_Rect area = { left, top, SDL_min(AREA_W, MAP_W - left),
                              SDL_min(AREA_H, MAP_H - top) };
            int cells = 0;
            for (int y = area.y; y < area.y + area.h; ++y)
            {
                for (int x = area.x; x < area.x + area.w; ++x)
                {
                    if (map.isWalkable(x, y))
                    {
                        ++cells;
                    }
                }
            }

In the preceding code, each square of the grid is an SDL_Rect, like a room, and its cave cells are counted. Squares of 16 by 12 fit the map exactly, four across and three down. If their size were changed to one that doesn't fit, SDL_min would cut the last square of a row or a column short at the map's edge. Add the rest below it:

            if (cells >= MIN_AREA_CELLS)
            {
                areas.push_back(area);
            }
        }
    }
    return areas;
}

A square with 40 cells of the cave or more is kept as an area. The rest are left out, so nothing is placed in a square that's mostly rock.

A Whole Floor

Now the steps can be put together. Add generate below areasOf:

std::vector<SDL_Rect> CaveGen::generate(Map& map, Rng& rng)
{
    std::vector<SDL_Rect> areas;
    while (areas.size() < 2)
    {
        fillRandomly(map, rng);
        for (int pass = 0; pass < SMOOTHING_PASSES; ++pass)
        {
            smooth(map);
        }
        if (keepBiggestCave(map) >= MIN_CAVE_CELLS)
        {
            areas = areasOf(map);
        }
    }
    return areas;
}

A cave is made over and over until it's good enough to play: a biggest cave of at least 600 cells, and at least two areas. One area is for the player to start in, and one for the monsters, who never start in the player's area. Nearly one cave in four is too small, and is made again. Each try rolls the same rng, so a seed makes the same cave, tries and all.

Where to Start, and Where the Stairs Go

On a floor of rooms, the player starts in the middle of the first room. A cave's area can have rock in its middle, so the player starts on the floor cell nearest the middle instead. Open Game.cpp, and add this to the unnamed namespace, below isNextTo:

// Where the player starts in an area: the walkable cell nearest its
// middle. In a room, that's the middle itself
Point startIn(const Map& map, const SDL_Rect& area)
{
    Point middle = RoomGen::centerOf(area);
    Point best = middle;
    int bestDistance = -1;   // none found yet
    for (int y = area.y; y < area.y + area.h; ++y)
    {
        for (int x = area.x; x < area.x + area.w; ++x)
        {
            int distance = distanceSquared({ x, y }, middle);
            bool nearer = bestDistance < 0 || distance < bestDistance;
            if (map.isWalkable(x, y) && nearer)
            {
                best = { x, y };
                bestDistance = distance;
            }
        }
    }
    return best;
}

In the preceding code, every floor cell in the area is measured from the middle, by its squared distance, and the nearest wins. A room's middle is always floor, so there it's still the middle.

The stairs go on the cell farthest from the start by walking, as they have since Chapter 15. F6 will want that cell too, so the search moves out of placeStairs into a function that both can call. Add it below startIn:

// The walkable cell farthest from start by walking, where the stairs
// down go
Point farthestFrom(const Map& map, Point start)
{
    DijkstraMap distances;
    distances.compute(map, { start });
    Point farthest = start;
    int farthestDistance = 0;
    for (int y = 0; y < MAP_H; ++y)
    {
        for (int x = 0; x < MAP_W; ++x)
        {
            int distance = distances.at({ x, y });
            if (distance != DijkstraMap::UNREACHED &&
                distance > farthestDistance)
            {
                farthest = { x, y };
                farthestDistance = distance;
            }
        }
    }
    return farthest;
}

In the preceding code, the lines are placeStairs' own, with the map and the start passed in. Replace the whole of placeStairs with this:

// The stairs down go on the cell farthest from the player by walking, so
// every floor has to be crossed to find the way down
void Game::placeStairs()
{
    Point farthest = farthestFrom(level_.map, player_.pos);
    level_.stairs = farthest;
    level_.map.set(farthest.x, farthest.y, Terrain::StairsDown);
}

The stairs go just where they did, on the cell farthest from the player by walking. Only the search has moved, into a function of its own.

The Last Step on F6

F6's last step keeps the biggest cave, and shows where a player would start in it, and where its stairs would go. Open Game.h, and replace the comment above struct CaveSteps with this:

// The debugging aid on F6: a cave being made, while it's showing, and
// the step it's at: 0 for the random fill, then each smoothing pass,
// then the biggest cave kept, with its size, and where a player would
// start in it. cavesShown_ counts the caves, for their dice

Then add the cave's size and its start below int step = 0;:

int cells = 0;
std::optional<Point> start;

Open Game.cpp, and replace the comment above stepCave with this:

// F6 shows a cave being made, a step at a time: the random fill, each
// smoothing pass in turn, the biggest cave kept, and then the game again.
// The cave has dice of its own, from the run's seed and how many caves
// have been shown, so looking changes nothing in the run, and the same
// seed shows the same caves

Then, in stepCave, find these lines:

    ++caveSteps_->step;
}
else

Change them to these:

    ++caveSteps_->step;
}
else if (caveSteps_->step == CaveGen::SMOOTHING_PASSES)
{
    // The last step keeps the biggest cave, and shows where a player
    // would start in it, and where its stairs would go
    CaveSteps& steps = *caveSteps_;
    steps.cells = CaveGen::keepBiggestCave(steps.map);
    std::vector<SDL_Rect> areas = CaveGen::areasOf(steps.map);
    if (!areas.empty())
    {
        steps.start = startIn(steps.map, areas.front());
        Point stairs = farthestFrom(steps.map, *steps.start);
        steps.map.set(stairs.x, stairs.y, Terrain::StairsDown);
    }
    ++steps.step;
}
else

The step after the last pass keeps the biggest cave. Then it works out its areas, its start and its stairs, just as a real floor will. The reference steps is only a shorter name for the struct inside the optional. Add the start's drawing at the end of drawCaveSteps, below its loops:

if (caveSteps_->start)
{
    view_->drawPlayer(*caveSteps_->start);
}

The side panel says how big the cave is, and whether it's too small to be kept. In drawSidePanel, find this line:

if (caveSteps_->step > 0)

Change it to these:

if (caveSteps_->step > CaveGen::SMOOTHING_PASSES)
{
    step = "the biggest cave: " + std::to_string(caveSteps_->cells) +
           " cells";
}
else if (caveSteps_->step > 0)

Then add this below glyphs_.drawText(step, x, y, Palette::DEBUG);:

bool tooSmall = caveSteps_->step > CaveGen::SMOOTHING_PASSES &&
                caveSteps_->cells < CaveGen::MIN_CAVE_CELLS;
if (tooSmall)
{
    y += row;
    glyphs_.drawText("too few, so it's made again", x, y,
                     Palette::DEBUG);
}

Checkpoint: Press F5 to start the game, and press F6 in its window six times. The sixth press keeps the biggest cave: every pocket cut off from it turns to rock, an @ marks where a player would start, and a > marks the stairs at the far end. The side panel gives the cave's size: with seed 42, the biggest cave: 684 cells. The next image shows the fourth pass, and the same cave after the sixth press.

Keep pressing F6, through more caves. Now and then the side panel says too few, so it's made again, for a cave of fewer than 600 cells, which a real floor would throw away and make again. The game itself is still just as it was, since nothing in it uses a cave yet.

Caves in the Game

The last part puts caves into the dungeon, on floors 4 and 7. The code that places monsters, items and gold learns that an area isn't all floor. A cave holds fewer monsters than a floor of rooms, and the save learns the cave floor's letter.

Which Floors Are Caves

Floors 4 and 7 are caves, one in the middle band and one in the deep. Open Game.cpp, and add these to the unnamed namespace, below ITEMS_BASE:

// The floors that are caves. The rest are rooms
constexpr int CAVE_FLOORS[] = { 4, 7 };

// A cave holds CAVE_MONSTERS_PERCENT of the monsters a floor of rooms
// would: in the open, every one of them can see the player from afar
// (*tune*)
constexpr int CAVE_MONSTERS_PERCENT = 75;

Changing which floors are caves is a matter of changing a list, CAVE_FLOORS. The second number comes into play below, with the monsters. Add a function to ask about the list below startIn:

bool isCaveFloor(int depth)
{
    for (int floor : CAVE_FLOORS)
    {
        if (floor == depth)
        {
            return true;
        }
    }
    return false;
}

The function looks through the list for the floor it's asked about. The list is two numbers long, so nothing quicker is needed.

A Floor of Either Kind

Now newLevel makes a cave or rooms, by the floor. Replace the comment above newLevel with this:

// Makes the floor at a depth, in place of the one before: rooms, or a
// cave, the player in the middle of the first area, its monsters, items
// and gold, and its stairs down, unless it's the last floor. Both
// generators give areas to put things in: rooms, or the squares of a grid
// over the cave, which can have walls in them

Then, in newLevel, find these lines:

std::vector<SDL_Rect> rooms = RoomGen::generate(level_.map, rng_);
player_.pos = RoomGen::centerOf(rooms.front());
placeMonsters(rooms);
placeItems(rooms);
placeGold(rooms);

Change them to these:

std::vector<SDL_Rect> areas;
if (isCaveFloor(depth))
{
    areas = CaveGen::generate(level_.map, rng_);
}
else
{
    areas = RoomGen::generate(level_.map, rng_);
}
player_.pos = startIn(level_.map, areas.front());
placeMonsters(areas);
placeItems(areas);
placeGold(areas);

Either generator fills the map and hands back its areas, and everything after that is the same for both. The player starts on the cell startIn gives, which in a room is its middle, as before.

The vector was called rooms, and now it's areas, since a cave's areas aren't rooms. The functions that place things take it, so their parameters are renamed to match, starting with the declarations. Open Game.h, and find these lines:

void placeMonsters(const std::vector<SDL_Rect>& rooms);
const MonsterDef* chooseMonsterKind();
std::optional<Point> freeCellIn(const SDL_Rect& room);
void addMonster(const MonsterDef& kind, Point cell, int packId,
                bool awake);
const ItemDef* chooseItemKind();
void placeItems(const std::vector<SDL_Rect>& rooms);
void placeStairs();
void placeGold(const std::vector<SDL_Rect>& rooms);

Change them to these:

void placeMonsters(const std::vector<SDL_Rect>& areas);
const MonsterDef* chooseMonsterKind();
std::optional<Point> freeCellIn(const SDL_Rect& area);
void addMonster(const MonsterDef& kind, Point cell, int packId,
                bool awake);
const ItemDef* chooseItemKind();
void placeItems(const std::vector<SDL_Rect>& areas);
void placeStairs();
void placeGold(const std::vector<SDL_Rect>& areas);

The comment on the include of <vector> names the rooms too. In Game.h, change for the rooms to for the areas.

On the Ground

A cave's areas have rock in them, so a cell chosen at random in an area may be a wall. Each of the three functions that place things must check that its cell is ground, with isWalkable. The names inside them change as well, so each is replaced whole, comment and all.

A monster's cell comes from freeCellIn. Back in Game.cpp, replace the whole of freeCellIn with this:

// A cell of ground in the area with no monster on it, chosen at random,
// or nothing if a few tries find none
std::optional<Point> Game::freeCellIn(const SDL_Rect& area)
{
    for (int tries = 0; tries < 20; ++tries)
    {
        Point cell = { area.x + rng_.roll(0, area.w - 1),
                       area.y + rng_.roll(0, area.h - 1) };
        if (level_.map.isWalkable(cell.x, cell.y) && monsterAt(cell) == nullptr)
        {
            return cell;
        }
    }
    return std::nullopt;
}

A cell of rock now fails the test, just as a cell with a monster on it does, and the next try is taken.

The gold needs more than a check. A pile has had one try at a cell, and was dropped if the cell was taken, by an item or by the player. That was rare in a room, but in a cave most cells are rock, so most piles would be dropped. Each pile gets 20 tries now, as each item does. Replace the whole of placeGold with this:

// Puts GOLD_PILES_MIN to GOLD_PILES_MAX piles of gold in the areas, the
// deeper the bigger, one to a cell, on the ground, never on the player or
// another item. Each pile has a few tries to find a cell, as items do
void Game::placeGold(const std::vector<SDL_Rect>& areas)
{
    int lastArea = static_cast<int>(areas.size()) - 1;
    int piles = rng_.roll(GOLD_PILES_MIN, GOLD_PILES_MAX);
    for (int i = 0; i < piles; ++i)
    {
        for (int tries = 0; tries < 20; ++tries)
        {
            const SDL_Rect& area = areas[rng_.roll(0, lastArea)];
            Point pos = { area.x + rng_.roll(0, area.w - 1),
                          area.y + rng_.roll(0, area.h - 1) };
            bool free = level_.map.isWalkable(pos.x, pos.y) &&
                        pos != player_.pos && floorItemAt(pos) == nullptr;
            if (free)
            {
                FloorItem pile;
                pile.pos = pos;
                pile.item.def = data_.findItem("gold");
                pile.item.count = rng_.roll(GOLD_MIN, GOLD_MAX) *
                                  level_.depth;
                level_.items.push_back(pile);
                break;
            }
        }
    }
}

In the preceding code, the test is long, so it's worked out first, as free. The pile is made on the first cell that's ground, and free, and break stops the tries there. On a floor of rooms, the tries change something only where a pile would have been dropped. So most floors come out just as they were: seed 42's first floor, for one, is the same, pixel for pixel.

The items already have their tries, and need only the check. Replace the whole of placeItems with this:

// Puts the floor's items in its areas, any of them: ITEMS_BASE, and one
// more for every two floors down. One to a cell, on the ground, never on
// the player
void Game::placeItems(const std::vector<SDL_Rect>& areas)
{
    int lastArea = static_cast<int>(areas.size()) - 1;
    int wanted = ITEMS_BASE + level_.depth / 2;
    for (int i = 0; i < wanted; ++i)
    {
        for (int tries = 0; tries < 20; ++tries)
        {
            const SDL_Rect& area = areas[rng_.roll(0, lastArea)];
            Point pos = { area.x + rng_.roll(0, area.w - 1),
                          area.y + rng_.roll(0, area.h - 1) };
            bool free = level_.map.isWalkable(pos.x, pos.y) &&
                        pos != player_.pos && floorItemAt(pos) == nullptr;
            if (free)
            {
                FloorItem floorItem;
                floorItem.pos = pos;
                floorItem.item.def = chooseItemKind();
                level_.items.push_back(floorItem);
                break;
            }
        }
    }
}

The same test, ground and free, now guards the monsters, the items and the gold, so nothing is placed inside the rock.

Fewer Monsters in a Cave

A floor of rooms wants 16 monsters, and one more for each floor of depth: 17 on the first floor, and 20 on the fourth. Caves hold only three quarters of that, because of how open they are. In a cave, every monster can see the player from across a chamber, and they come all together. Behind a room's walls, they come a room at a time.

Testing showed the difference, with a bot that plays the game by itself, of the kind Chapter 27 builds. With as many monsters as a floor of rooms, more than half of the Fighters the bot played who reached floor 7 died there, as the deep band met them in the open. At three quarters, about a third did.

The cut goes in placeMonsters, which gets its new names at the same time. Replace the whole of placeMonsters with this:

// Puts the floor's monsters in its areas: MONSTERS_BASE, and
// MONSTERS_PER_FLOOR more for each floor down, or CAVE_MONSTERS_PERCENT
// of that in a cave, while there's room. A pack comes all together, in one
// area, asleep or awake together. The first area is the player's, so it's
// left empty
void Game::placeMonsters(const std::vector<SDL_Rect>& areas)
{
    int lastArea = static_cast<int>(areas.size()) - 1;
    if (lastArea < 1)
    {
        return;
    }

    int wanted = MONSTERS_BASE + MONSTERS_PER_FLOOR * level_.depth;
    if (isCaveFloor(level_.depth))
    {
        wanted = wanted * CAVE_MONSTERS_PERCENT / 100;
    }
    int packsSoFar = 0;
    for (int tries = 0; tries < 100; ++tries)
    {
        if (static_cast<int>(level_.monsters.size()) >= wanted)
        {
            return;
        }

        const MonsterDef* kind = chooseMonsterKind();
        const SDL_Rect& area = areas[rng_.roll(1, lastArea)];
        int packId = 0;
        if (kind->pack > 1)
        {
            ++packsSoFar;
            packId = packsSoFar;
        }

        // Most start asleep, and the rest wandering
        bool awake = kind->has(Trait::NEVER_SLEEPS) ||
                     rng_.roll(1, AWAKE_ONE_IN) == 1;
        for (int i = 0; i < kind->pack; ++i)
        {
            std::optional<Point> cell = freeCellIn(area);
            if (cell)
            {
                addMonster(*kind, *cell, packId, awake);
            }
        }
    }
}

In the preceding code, the if below wanted is new. On a cave floor, it cuts the count to CAVE_MONSTERS_PERCENT of itself. The rest is as it was, with areas where it had rooms.

The count is multiplied first and divided after. Done the other way around, CAVE_MONSTERS_PERCENT / 100 would come first, and in ints that's 0. So a cave would have no monsters at all. On floor 4, a cave gets fifteen monsters where a floor of rooms gets twenty, and a pack can add one or two more to either.

The Save's Version 2

A save writes each cell's terrain as a letter, and the cave floor needs one. Chapter 17's game, version 1, couldn't read it, so the save's version goes up to 2. Open SaveGame.cpp, and replace the comment above constexpr int SAVE_VERSION with this:

// The version of the save's format. Whatever changes what's saved
// changes the version, so an old save is never misread. Version 2
// added the caves' floor (Chapter 18)

In SaveGame.cpp, change SAVE_VERSION = 1; to SAVE_VERSION = 2;. Then add the cave floor's letter below { Terrain::StairsDown, '>' },:

{ Terrain::CaveFloor, ':' },

A colon is a pair of dots, earth among stone. Chapter 17's work pays off here. A save from Chapter 17 is now from another version. So the game turns it away by its version, and keeps it, rather than calling it damaged or reading it wrong.

Checkpoint: Press F5. If you have a save from Chapter 17, the title screen offers it as before, and C now says it's from another version of the game: save.txt: it's version 1, and this game reads version 2. Press N for a new run. The first floor is rooms, as it was.

To see a cave without the walk down, close the game, and set the constructor's newLevel(1) to newLevel(4) for a moment. Type 42 into Command Arguments, and press F5. Closing the game saved the run, so the title screen comes first, where C would carry on from floor 1. Press N there, for a new run on floor 4.

The player stands in a chamber of the fourth floor's cave, on brown earth. Press F1 to see it all, with its fifteen monsters spread through it. Then press F2 for the tile view, which is what Figure 18.1 shows. Put newLevel(1) back when you're done.

Playing the Game

The dungeon now has two kinds of floor, and they play differently. In a cave, there are no doorways to hold. The monsters see you from across a chamber and come together, which is why there are fewer of them. A cave's throats are its doorways: pull back into one, and the monsters have to come at you one or two at a time.

Floor 4 is the middle band's cave, and floor 7 the deep band's. A player who has learned to fight room by room has to learn again, and that's the point of a second generator.

Understanding the Code

A cave is made by CaveGen. First the map is filled at random, 48 cells in 100 wall, with an edge of wall. Then it's smoothed four times by the 4-5 rule, every cell decided from a copy of the map as it was before the pass.

Next, a flood fill finds every cave. Every cell outside the biggest becomes rock, so all of the cave can be reached. The squares of a grid over the map, 16 cells by 12, that hold enough of it are its areas. The cave is made again if it's too small, or has fewer than two areas.

The cave floor is a terrain of its own, walkable, brown in the glyph view and dirt in the tile view. On floors 4 and 7, newLevel makes a cave, and starts the player on the floor cell nearest the first area's middle. It places three quarters of the usual monsters, and the usual items and gold, all on cells that are ground. F6 shows a cave being made, a step at a time, with dice of its own. The save writes a cave floor as :, in version 2.

Experimenting

Try each of these with F6, and put each back afterward:

• Fewer walls. Set WALL_PERCENT to 45. After smoothing, the caves run together into one wide hall, with pillars of rock standing in it. The biggest cave holds nearly all the floor.
• More walls. Set WALL_PERCENT to 52. The caves break into pockets, and the side panel says too few, so it's made again far more often: about nine caves in ten.
• One pass, or ten. Set SMOOTHING_PASSES to 1, and the caves are rough, with ragged walls and specks of rock. Set it to 10, and the passes after the fourth change fewer and fewer cells, a few dozen and then a handful. The rule settles quickly, which is why four is enough.
• Caves everywhere. Add 1 to CAVE_FLOORS, as in { 1, 4, 7 }, and play. The first floor is a cave, and you can see how the game feels with no rooms at all.

The first three show the 4-5 rule's character. Between too open and too closed is a narrow band, and 48% sits in it: most of the floor ends up in the biggest cave, and three caves in four are kept.

Common Errors and Fixes

If the game didn't build, or doesn't behave as described, the problem is probably one of these.

C2838: 'CaveFloor': illegal qualified name in member declaration, followed by C2065: 'CaveFloor': undeclared identifier, in several files. The new terrain is missing from the enum. Add CaveFloor, to Terrain, in Map.h, below StairsDown,.

C2653: 'CaveGen': is not a class or namespace name, in Game.cpp, followed by C3861 for fillRandomly, and more for every name of the generator's. The include for CaveGen.h is missing from the top of Game.cpp.

F6's noise is all #, with no floor in it at all. The glyph view draws anything it doesn't know as wall, and it doesn't know the cave floor. Add the cave floor's branch to drawTerrain, in GlyphView.cpp.

LNK2019: unresolved external symbol "void __cdecl CaveGen::smooth(class Map &)", referenced in function Game::stepCave, followed by LNK1120. The function was typed as void smooth(Map& map), without CaveGen::, so it's a function of its own. The one that CaveGen.h promises is never written. Its first line should be void CaveGen::smooth(Map& map).

C2039: 'step': is not a member of 'std::optional<Game::CaveSteps>', in stepCave. The code says caveSteps_.step, with a dot, which asks the optional for a member it doesn't have. The struct is inside the optional, and -> reaches it, as it would through a pointer: caveSteps_->step.

The game freezes when it starts on floor 4, or as you go down to it. The function Map::isWalkable doesn't count the cave floor, so the flood fill finds no cave at all. Then generate makes cave after cave, waiting for one that's big enough, which never comes. Add terrain == Terrain::CaveFloor to isWalkable, in Map.cpp, and stop the frozen game with Shift+F5.

In a cave, some monsters stand in solid rock, and never move. freeCellIn doesn't check that its cell is ground, so a monster can be put anywhere in its area, rock and all. Its test should ask level_.map.isWalkable(cell.x, cell.y) as well.

A run saved in a cave comes back damaged, with no terrain is called '?' for every row with cave floor in it. The save has no letter for the cave floor, so letterFor wrote ?, just as Chapter 17 said it would. Then the save is set aside as save.bad. Add { Terrain::CaveFloor, ':' }, to TERRAIN_LETTERS, in SaveGame.cpp.

FAQ

Q) Why keep only the biggest cave, and not join the others to it with tunnels?

A) Joining keeps more floor, but a tunnel cut straight through rock looks like what it is, a corridor in a cave. Keeping the biggest cave throws some floor away. In return, there's nothing to join: the cave that's left is all of a piece, and every cell of it can be reached. Angband joins its caverns, as the Design note says, and both are fair answers.

Q) Why does F6 have dice of its own?

A) If F6 rolled the run's own dice, looking at a cave would change everything that came after it: the next monster's step, the next fight. A debugging aid shouldn't change what it's helping you look at. With dice of its own, from the seed and a count, F6 shows the same caves for the same seed. And the run doesn't know it was ever pressed.

Q) Why are the areas squares of a grid, rather than the cave's own chambers?

A) Finding chambers in a cave means deciding where one ends and the next begins, which is hard to do well. A grid is simple, and it spreads the monsters and items over the whole cave, which is what the areas are for. Squares that are mostly rock don't count, so things aren't crowded into the scraps of floor at a cave's edges.

AI Exercise (Optional)

The RogueBasin article in this chapter's first Design note answers its own problems with a second rule. If you'd like to try it, with an AI's help, open your AI chatbot of choice, and try a prompt like this:

"I'm writing a roguelike in C++ with SDL 3. Caves are made by a cellular automaton in a namespace, CaveGen: fillRandomly makes 48% of the cells inside the map's edge walls, and smooth runs one pass of the 4-5 rule, making a cell a wall if 5 or more of the 9 cells in its 3 x 3 block are walls, deciding every cell from a copy of the map. I'd like to try the RogueBasin article's second rule for the first passes: a cell is also a wall if there are 2 or fewer walls within two cells of it, in the 5 x 5 block. Show me every change, keeping the plain rule for the last passes, with each curly brace on its own line, and explain it."

Notice what the preceding prompt does. It names exactly the rule the game has, and the one to add, with the block sizes. So the answer can't drift into some other rule. And it keeps the plain rule for the last passes, as the article does, which you can compare with F6.

When the answer comes back, check that the 5 x 5 block stays on the map at the edges, since a cell next to the edge has neighbors two cells out that aren't there. Then watch the passes on F6, and compare the caves with the plain rule's.

Summary

A cave grows from noise: a random fill, four passes of the 4-5 rule from a copy, and a flood fill that keeps the biggest cave. The cave is divided into areas, so the placing code works as it does on rooms. Floors 4 and 7 are caves, with fewer monsters, and everything is placed on the ground. In Chapter 19, the rooms get doors, which block sight while they're shut, and some of them are hidden in the walls. Every floor gets traps too, found by searching, or the hard way.