After a several month absence from work on my Wa, my personal roguelike project, I decided to get back into it. One of the hard parts of picking up a dusty project is re-familarizing yourself with the code. So, I decided to write an article about my cave generator since it would force me to read, think about and understand my code. I may later add a basic (and most likely incorrect) algorithm analysis.

I was tipped off to the idea of using cellular automata rules to generate a cave by links from the Roguelike Development site. I didn't find any code to use, so I read a bit about how the rules work and from that whipped up this method fairly quickly. I previously had a cave generator using a fractal method, but although I found an algorithm I was able to port to Python, I frankly didn't understand it and I feel much more comfortable with code that I 'get'. The CA method seems to be a fair bit faster as well.

The algorithm has three phases:

- Create the initial map
- Run a cycle of CA rules through the map
- Join the seperate caves together so that any square on the map is reachable by any other

**1. Create the initial map**

I start off with a rectangle, add a border of permanent (in the game they'll be non-diggable, meltable, etc.) and randomly
place a number of empty floor squares on the map. After some experimentation, I decided that starting with around 40% of your
squares as floors yields a nice looking cave system.

Note that in theory, this could take a long, long time. I'm selecting random points on the map to add floors to, so if I
randomly get many collisions (picking a square that is already a floor), it could take a fairly long time. In most cases, though, it
shouldn't be too bad. Even when I am adding the last square, the probability of collision is about 0.4. Even if it were
0.5 everytime I was laying a floor square, on average setting up the initial map would take 2N operations (where N is the number of squares
on the map) on average. There will be few collisions while there aren't many floor squares, so it will require far fewer operations in most cases.

In any case, I haven't run into any issues during testing.

From one sample run, I got this for my starting conditions:

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . . . . # # # . # # # . # . # # . # # . # . # . . # # # # # . # # . # . . # . . . . # . # # # # # # . . . . . # # # . # # . # # # . . # # . # # # . . # . . # . . . # . . # # # # # . . . # . . . # # . # # . . # # . # # . . # # # # # # # . # # # # . # # # . # . # # # # # # . . # # . # . # # # # . . # # # # # . # # # # # # . # # # . . # . # . . . # . # # # # # # . . # . # # . . # . . # # # # . # . # # # . # . # # . # # # # # . . # . # # . . . # # # . # . . # # # . . # # # # . # . . # # # # . . # # # # # . . # # . . # . . . # # # # . . # # # # . . . . # . # # . . # . . # . # # # . # . . # # . . . . . # . . # # # . # # . . # . # . . . . # . . # # # # . # . . . . . # . # # . # # # # . . # . . . # . . # . . # # . . . . . # . . . . # . # . . . # . # # # . # # # . # # # # # # # # . # # # . . # # # # # . . . . # # . # # . . . . # # . . # # # # # # # # . # . # . # # . # . # . . . # . . . # # # # # . # . . . . # # . # . # . # # . . # . # # # . . . # # . # # . # # # # . # . . . # # . . # . # . # # # . # # . # # # . # . # . . . . . # # . # . . . . . # # . . # # . . # # # # . # . # . # . . # # . # . # # . . # # # # . . # # . # # # # # . # # # # . . # . . . # . . # # . # # . . # # . # . # # # . # # . . # . . # . . # # # # # . . . . # . # . # # # # # # . # # # . # # . . # . # . . # # . . # # # . # . . . # # # . . . . # # # # . . . # # . # # # . # # . # . . . # # # # # # . . # # # # . . . # . . . # . . . # # # # . # . # . . # # # # # . # . # . # # . . . # # . # # . # # . . # # . . . # # # . # # # . # . . # . . # . . # . # # # . # # . . # . # # # # # # # # . # # # . . # # # . . . . . . # . . # # # # # # # # # # # . . . # # . # . # # # . # # # . . # . . # # # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Here is the Cellular Automata part. I use the 4-5 rule for adjusting squares. This means that for any given square, if it has 3 or fewer adjacent wall squares (counting all 8 cardinal compass points), the square 'starves' and becomes a floor. If it has greater than 5 adjacent wall squares, the square becomes a wall. Otherwise, leave it as is.

CA systems usually run through many cycles and interesting structures can emerge from this. As I understand it, you can build all of the basic boolean gates using Cellular Automata systems, so you could in theory implement an entire working computer with the same power (in a Turing sense) as any other computer. For my purposes, though, one cycle was enough to generate an interesting set of caverns. Other CA rules, of course, may produce different cave patterns.

Here is the map from my sample run after one pass using the 4-5 rule:

We get one large cave area, with six small areas which are cut off from the main room. Joining them together turns out to be the trickiest part of the algorithm.# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # # # . . # # # # # # # # # # # # # . . . . . # # # # # # . # # # . . # # # # # # . # # # # # . . . . . . # # # # # # # # # . . . # # # # # # # # # # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # . . # . . . . . # # # # # # # # # # # # # # # # # # # # # . . . . . . . . . . # # # # # # # # # # # # # # # . . # # # # . . . . # . . . . # # # # # # # # # # # # # # # . . # # # # # . . . . . . . # # # # # # # # # # # # . . # # # # # . . # # . . . . . . . # # # . . # # # # . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # # . . . . # # # . . . . # # # . . . . . . . . . . . . . # # # # # # # # # # # . . . . # . # . . . . . . . . . . . . # # # # # # # # # # # # . . . . # . . . . . . . # # . . . . # # # # # # # # # # . . . . . . . . . . . . . . # # . . . . # # # # # # # # . . . . . . . . . . . . . # # . . # # . . # # # # # # # # # # . . . . . . . . . . . # # # . . . # # . # # # # # # # # # # . . . . . . . . . . . . # # . . . # # # # # # # # # # # # # . . . . . . . . . . . . . # # . . . # # # # # # . # # # # # # . . . . . . . # . . . # # # . . . . # # # # . . . # # # # # . . . . . . . . . . # # # # . . . . # # # # # . . # # # # . . . . . . . . . . . # # # # . . . . . . # # # # # # # # # . . . . . . . . . . . # # # . . . . . . . # # # # # # # # # . . . . . . . . . . . . # . . . . . . . # # # # # # # # . # # . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # . . . # # # . # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

The trick here is to first divide the map into seperate caves. Think of each cave being a set of floor squares. There are

To do store this, I use a data structure known as a Disjoint Set, which provides two primary functions -

Note that I'm letting the player move diagonally so caves like these will be considered connected:

############ # #2 # # 1# # ############This means the player from move from 1 to 2. (I may do it Nethack-style where a burdened player can't move that way)

My solution to joining the caves is this: I take a point in each distinct cave, and draw a meandering live from that point towards the centre of the map. Stop drawing the line when one of two conditions is met: (1) The next square you are about to draw (turn into a floor) is in the same cave as the center of the map or (2) The next square you are about to draw upon is already a floor and

If the center square happens to a wall, the line will draw until it reaches the centre, or crosses into the cave that probably surrounds the middle. (Note the second rule where if the line crosses into a cave that is not already part of its own set, it stops drawing)

Drawing towards the center avoids a number of issues - which point should be start and which should be the end. How do I draw a random line and avoid drawing towards the outside. In a number of test runs I ended up with lines that meandered and backtracked all over the places resulting in some very silly looking maps.

I believe this is actually a Monte Carlo algorithm - a randomized algorithm which is

Once this is performed on the map from step 2, we have:

A nice-looking, fully connected cave area! A 30X30 cave typcially takes .3 - .4 seconds to generate on PIII-500Mhz desktop at work, which isn't too bad. If performance proved unacceptable for larger maps on slower machines I would consider porting the cave generator to C. Python makes it fairly easy to compartmentalize parts of your code this way.# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . . . . # # # # # # # # # # . . # # # # # # # # # # # # # . . . . . # # # # # # . # # # . . . # # # # # . # # # # # . . . . . . # # # # # # # . # . . . # . # # . . # # # # # # . . . . . # # # # # # # # . # # # # # # . . . # # # # . . # . . . . . # # # # # # # # # . # # # # # # . . # # # . . . . . . . . . . # # # # # # # # . . # # # # # . . # # # # . . . . # . . . . # # # # # # # # # # . # # # # . . # # # # # . . . . . . . # # # # # # # # # # # . . . # # # . # . . # # . . . . . . . # # # . . # # # # . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # . . . . . . . . . . . . # # . . . . . . . . . . . . . # # # # . . . . # # # . . . . # # # . . . . . . . . . . . . . # # # # # # # # # # # . . . . # . # . . . . . . . . . . . . # # # # # # # # # # # # . . . . # . . . . . . . # # . . . . # # # # # # # # # # . . . . . . . . . . . . . . # # . . . . # # # # # # # # . . . . . . . . . . . . . # # . . # # . . # # # # # # # # # # . . . . . . . . . . . # # # . . . # # . # # # # # # # # . . . . . . . . . . . . . . # # . . . # # # # # # # # # # . # # . . . . . . . . . . . . . # # . . . # # # # # # . # . # # # # . . . . . . . # . . . # # # . . . . # # # # . . . . # # # # . . . . . . . . . . # # # # . . . . # # # # # . . # # # # . . . . . . . . . . . # # # # . . . . . . # # # # # # # . . . . . . . . . . . . . # # # . . . . . . . # # # # # # # . # . . . . . . . . . . . . # . . . . . . . # # # # # # # # . # # . . . . . . . . . . . . . . . . . # # # # # # # # # # # # # # . . . # # # . # # # . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

The python files used are:

ca_cave_demo.py.txt

DisjointSet.py.txt

If you have any questions, feel free to email me at