Using A Cellular Automata Style Rule To Create A Cave System

|| Home ||

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:

  1. Create the initial map
  2. Run a cycle of CA rules through the map
  3. 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: 

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# . . . . . . . # # # . # # # . # . # # . # # . # . # . . #
# # # # . # # . # . . # . . . . # . # # # # # # . . . . . #
# # . # # . # # # . . # # . # # # . . # . . # . . . # . . #
# # # # . . . # . . . # # . # # . . # # . # # . . # # # # #
# # . # # # # . # # # . # . # # # # # # . . # # . # . # # #
# . . # # # # # . # # # # # # . # # # . . # . # . . . # . #
# # # # # . . # . # # . . # . . # # # # . # . # # # . # . #
# . # # # # # . . # . # # . . . # # # . # . . # # # . . # #
# # . # . . # # # # . . # # # # # . . # # . . # . . . # # #
# . . # # # # . . . . # . # # . . # . . # . # # # . # . . #
# . . . . . # . . # # # . # # . . # . # . . . . # . . # # #
# . # . . . . . # . # # . # # # # . . # . . . # . . # . . #
# . . . . . # . . . . # . # . . . # . # # # . # # # . # # #
# # # # # . # # # . . # # # # # . . . . # # . # # . . . . #
# . . # # # # # # # # . # . # . # # . # . # . . . # . . . #
# # # # . # . . . . # # . # . # . # # . . # . # # # . . . #
# . # # . # # # # . # . . . # # . . # . # . # # # . # # . #
# # . # . # . . . . . # # . # . . . . . # # . . # # . . # #
# # . # . # . # . . # # . # . # # . . # # # # . . # # . # #
# # # . # # # # . . # . . . # . . # # . # # . . # # . # . #
# # . # # . . # . . # . . # # # # # . . . . # . # . # # # #
# # . # # # . # # . . # . # . . # # . . # # # . # . . . # #
# . . . . # # # # . . . # # . # # # . # # . # . . . # # # #
# # . . # # # # . . . # . . . # . . . # # # # . # . # . . #
# # # # . # . # . # # . . . # # . # # . # # . . # # . . . #
# # . # # # . # . . # . . # . . # . # # # . # # . . # . # #
# # # # # # . # # # . . # # # . . . . . . # . . # # # # # #
# # # # # . . . # # . # . # # # . # # # . . # . . # # # . #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
2. Run a cycle of CA rules through the map

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.

3. Join the caverns together

The trick here is to first divide the map into seperate caves. Think of each cave being a set of floor squares. There are 7 disjoint sets one map after step 2. What I need to do is draw lines of floor squares between the caves. For each square on that line, I union it with one of the sets, stopping when the two sets are unioned into one (the caves will be joined). Sort of, I'll go into more detail about joining caves in a bit. I repeat this until there is only one set left.

To do store this, I use a data structure known as a Disjoint Set, which provides two primary functions - union and find. union takes two items and unions the sets they are part of into one. find returns the 'name' of the set. If two items have the same name, they belong to the same set. The Disjoint Set is a neat datastructure, fairly efficient, and well suited for this problem. I wrote up a page with details about the disjoint set here.

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 not in the same square as your starting point.

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 not guaranteed to find the perfect solution, but is guaranteed to finish in finite time. (The opposite is a Las Vegas algorithm - one in which a solution is guaranteed, but running time isn't) I suspect that my method won't completely join all the caves together in all cases, but in several dozen runs, I haven't yet seen it leave disjoint caves (I've tested from 30X30 maps to 50X50 maps). The rare time that two areas don't get joined will just make things interesting for the player :)

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 dana@pixelenvy.ca