three ways to dig a cave
I like a cave with an awkward bend in it. Somewhere to lose sight of a monster, or retreat into a narrow passage and regret it a turn later. Rounded walls help, but the interesting part is what happens between them.
There are a few fairly small algorithms that can produce that sort of place. Each has a habit you start to recognise after looking at enough maps.
The examples below are generated on a 28 by 15 grid. A # is rock and a
. is floor. The outer wall stays solid, and movement is north, south,
east or west. Keeping the maps small makes the rough edges rather obvious.
Let something wander
The drunkard’s walk starts with solid rock. Put a digger somewhere inside it, choose a random direction, move one tile, and carve out the new position. Repeat until there is enough floor.
Here is one walk after it has opened 50 distinct tiles:
############################
######.....#################
#..###...#...###############
#..#...#####..##############
##....####.....#############
###..#####..#...############
###.#########..#############
##############..############
##############...###########
##############...###########
##############..############
##############.#############
############################
############################
############################
And the same walk, allowed to continue to 140:
############################
#..........#################
#........#...###############
#........###..##############
#.....####.....#############
#....#.###..#...############
#......######..#############
#......#######..############
#.......######...###########
#.......####.....###########
#....#.####......###########
#.......###......###########
#.......##......############
#..............#############
############################
The nice property is that every new bit of floor touches the route that made it. With a single digger taking cardinal steps, the cave is connected from the beginning. There is no separate room stranded in the rock.
It also spends a lot of time walking over its own footprints. Count new floor tiles if you want a particular amount of open space. Counting steps gives you a much less predictable result.
This example uses seed 19 and refuses moves into the border. You can see the cost: the left edge has become a suspiciously straight wall. A bigger working area, or a slight bias away from the edges, can help. A little directional persistence can make longer passages, though too much starts to look like a worm tunnel.
RogueBasin’s random-walk notes
Let the walls vote
Cellular automata begin with a mess and repeatedly tidy it. Here each interior tile has a 45 percent chance of starting as a wall. Seed 13 gives this scatter:
############################
##...####.#.###..###.......#
##....#####......#.###.#..##
##.#####..#..##...##...#.#.#
##...#...#.###.###...#####.#
####.#.#.##.....##...#..#.##
########..#.#..####.#.######
###..#.#.#..###.#.##.#.....#
##....##...#.####.#....#...#
##.##..#..####.#..#...#...##
##.#.#.##.#....#..#.#.#.##.#
#.#..#.##.###.#..#........##
##..#.....#...#.#.#...##.#.#
#..##..#####.#.##.########.#
############################
The rule is short. Look at a three-by-three square centred on a tile, including the tile itself. If at least five of those nine cells are walls, make it a wall in the next map. Otherwise, make it floor.
Read from the old map and write into a fresh one. Changing tiles in place would let earlier edits affect later decisions in the same pass.
After five passes:
############################
############################
############.....###########
##########..........########
#########.............######
########.......##......#####
########......####.......###
########....######........##
########...######.........##
###...#########...........##
###....#######............##
###....#######...........###
####..########........######
############################
############################
The little specks have mostly disappeared. There is a broad chamber, a thick lump of rock, and a smaller pocket down on the left. This is closer to the sort of cave I want to put a lantern in.
That pocket is a problem, though. It looks perfectly usable on the map, but nobody can walk into it. Smoothing has no notion of a route between the entrance and the stairs. More passes can also close a narrow neck or erase a room you liked. Five is a starting point, not a magic number.
RogueBasin’s cellular-automata cave article
Cut through a field of noise
Another approach gives each tile a number, with nearby numbers changing gradually. Choose a cutoff: values below it become floor, everything else becomes rock.
For this example, random values sit on a lattice five tiles apart. Smooth interpolation fills the gaps. This is value noise, which is simple enough to write in a few lines. Perlin and simplex noise are other ways of making coherent fields; the example here uses neither.
With seed 13 and floor below 0.45:
############################
#..###############.........#
#..###############.........#
#..######....#####.........#
#..#####......###..........#
#..#####......###..........#
#..#####......###..........#
########................####
#######................#####
#######................#####
#######................#####
#######................#####
########......####....######
############################
############################
Keep the same field, but raise the cutoff to 0.60:
############################
#...#############..........#
#...####.....####..........#
#...###.......##...........#
#...###....................#
#...###....................#
#...###....................#
#..####....................#
######..................####
######..................####
######.................#####
######..................####
#######.................####
########.....######........#
############################
Now the floor pushes further into the rock. Some constrictions have opened up, while the passage on the left is still cut off. The cutoff is a useful density control. It doesn’t promise a particular percentage of floor, or a connected cave.
The spacing of the underlying lattice changes the scale of the shapes. Closer samples give smaller features. Combining a broad field with a weaker, finer one adds roughness, although a one-tile fleck of rock can matter rather more to a character than to a terrain picture.
Amit Patel’s explanation of maps made from noise
Before adding the goblins
I would check the floor with a flood fill before placing anything. Start on one floor tile and visit everything reachable under the game’s movement rules. If your game allows diagonals, its corner rules belong in this check too.
The smoothed cave above contains two regions: 120 floor tiles in the large one and 13 in the little pocket. Filling the pocket back in leaves this:
############################
############################
############.....###########
##########..........########
#########.............######
########.......##......#####
########......####.......###
########....######........##
########>..######.........##
###############...........##
##############...........<##
##############...........###
##############........######
############################
############################
The < and > are stairs, placed within the surviving region. In this
example they are far apart by walking distance, even though they don’t
look especially far apart on the screen. The central rock makes a
difference.
Keeping the largest region is a cheap repair. It also throws away space. Digging a connection would preserve the smaller chamber, at the cost of adding a passage whose shape you now have to choose. Either way, check reachability again after the last wall edit. A final smoothing pass can quietly undo the repair.
Then there are the questions a flood fill cannot answer. Is the entrance exposed? Is every fight going to happen in the same bottleneck? Does the long way round lead anywhere worth visiting?
I’d happily use a lopsided cave if it gave me a reason to take the long way round. A very handsome one can still be tedious to walk through.
The small script
The Python file below prints all seven maps exactly as shown. It uses only the standard library. The digger uses seed 19; the other two examples use seed 13. Change a seed or a parameter and see where the passage ends up.