Simple 2D Cave-like Generation using a Cellular Automaton Method.

The other week whilst having a break with my girlfriend’s family I came upon this blog post, which discusses the use of something called “Cellular Automaton” for Cave Generation. I was immediately intrigued by the title because it kind of fits in with my Final Year Project (Procedural Generation of Planets). In preparation for my project I’ve been doing a bit of research into PG (Procedural Generation) but hadn’t, until now, implemented anything. So, after reading the aforementioned blog post, I decided to actually create some code!

A Brief Intro. to Cellular Automaton int his Context… by a Noob

I really can’t compete with this, so for a decent understanding of CA you should really have a read of that post. However, I will give a quick overview of how it works in the context of this post.

Basically, say we have a 2D grid of cells (each being represented by a single pixel) all with only two states: Dead or Alive. An alive cell will be black, and a dead cell will be white. Now, in a pass of Cellular Automaton there is a rule for the conditions needed for a cell to be “Born” or to “Survive”. This rule is often given in the following format: Bx/Sy where x and y represent the number of alive neighbours around this current cell. When we talk about neighbours we refer to the eight neighbours of a cell:

Image showing the 8 neighbours of a cell.

As an example: B23/S45 would mean a dead cell is born (becomes alive) if there are 2 or 3 alive cells out of it’s eight neighbours (counting diagonals), and an alive cell survives the generation if there are 4 or 5 neighbours alive. Simples.

So, it turns out this method is a great way to make procedural rogue-like 2D caves.

My Implementation

For my implementation I used C++ with The CImg Library which I had never used before (turns out it’s really simple to use).

So let’s start with the function that does the good stuff.

void cellularAuto_B678_S345678(CImg<unsigned char> &image)

I’ve called the function after the rule I’ve used just so I can recognise it a bit better. What I want to talk about here is the CImg<unsigned char> &image part. In the CImg library an image can be represented by many different types such as longs, chars, ints, but char seems to be the most commonly used so that’s what I went for. So here we’re just passing a reference in to the image we want to perform the algorithm on.

for(int x = 0; x < image.width(); x++)
		for(int y = 0; y < image.height(); y++)
			if (x==0 || x==image.width()-1
				|| y==0 || y==image.height()-1)
			{ //set-up border up
				for(int c = 0; c < 3; c++)
						image(x,y,c) = 0;

The first thing we do is set up a one pixel border around the image so our cave is closed around all edges. If you look at the for(int c =0; c< 3…) loop what’s happening here is we’re looping through each channel of the pixel at (x,y) and setting it to be 0 so the final pixel colour will be black and thus an Alive cell. Once we’ve done this we continue on to the next iteration of the loop, we needn’t do any of the actual algorithm on this cell because it’s just a border.

			if (image(x, y, 0) == 255)
			{//if this pixel is currently dead...
				switch(countNeighbours(image, x, y))
				{ //get number of neigbours
				case 6: case 7: case 8: //BORN!
					for(int c = 0; c < 3; c++)
						image(x,y,c) = 0;

If the pixel wasn’t a border pixel we come onto this part. Here we check if the pixel is currently dead, if it is we check if it can be born using B678 (B678/S345678 is a great rule for cave generation). If it can, then it is! Note I’ve created a separate function for counting the neighbours of a pixel, I’ll post this later on.

			else //pixel must be alive...
				if (countNeighbours(image, x, y) < 3){ //DIED!
					for(int c = 0; c < 3; c++)
						image(x,y,c) = 255;

And finally, if the pixel is not dead it must be alive, so checks if it survives using S345678.

And that’s it really, that’s the algorithm that makes a simple cave. All that’s left is to set up an image to pass into this function:

int main(int argc, char **argv)
	srand( time(NULL));

	CImg<unsigned char> image(200, 20, 1, 3, 255); //Create blank image (w, h, d, ch, col)
	CImgDisplay main_display(image); //Create the display window

Here we’re just setting up the random number generator so it’s always random. Then we create an image using the constructor: CImg<T>(width, height, depth, channels, initialColour);
Then to create a display in CImg so we can see the image is as simple as above.

for(int x = 0; x < image.width(); x++)
		for(int y = 0; y <image.height(); y++)
		{ //Loop through image pixels, randomly assigning dead or alive
			if (getRandInt(0, 100) < 45){ //~45% tiles "ALIVE" 0 = alive 255 = dead
				image(x, y, 0) = 0;
				image(x, y, 1) = 0;
				image(x, y, 2) = 0;

This is the setup of the image. We go through the pixels and randomly assign them to be Dead or Alive. It turns out that starting with around 45% of the pixels alive gives the best results, changing this value by just 5% either way can make a big difference in the final “cave”. Again, we have to go through the channels(RGB) and set them accordingly.
And Finally…

	main_display.display(image); // display the updated image."cave.bmp", 0); //Save original image

	int count = 0;

	for (int i = 0; i < 5; i++)
	{ //Perform algorithm on image 5 times.
		cellularAuto_B678_S345678(image);"cave.bmp", i + 1); //Save each progression

Here we’ve updated the display with the newer random image and then we save this image. The second parameter in adds a number onto the file name, and so cave.bmp becomes cave000000.bmp. The next bit is pretty self explanatory I think.

And voila! That’s it! Here’s an example of the progression of a 60×60 cave after 5 iterations:

A Gif of the progression of a 60x60 cave

Obviously this algorithm isn’t perfect, in the above example all areas are not connected and I’ve not looked into a way around this yet. The caves generated in smaller resolutions such as 30×30 are much more rogue-like and more likely to be mostly joined together. Here’s an example (sorry for the blurryness):

30x30 Cave

I also realized this method can be used (and maybe was used, I’ve not checked) for the generation of Worms-like levels like this one I generated:

A 200x20 Cave resembling a Worms level.

I’m thinking such images could also be used for procedural texture generation, I’m sure you could get a nice camouflage effect out of it if you experiment a bit with colours. This method is also expandable into a 3D world to create Minecraft like worlds, but first I think it needs some tweaking to make the caves flow a bit better and be more connected. Watch this space… I might just give it a go.

Tagged , , , , , , ,

6 thoughts on “Simple 2D Cave-like Generation using a Cellular Automaton Method.

  1. MerQuick says:

    I used a combination of several in my approach, notably B345678/S0 followed by B678/S345678. It looks great.

  2. lloyd says:

    Do you have the code for the countNeighbours() function? I can’t see it on the page, thanks!

  3. Great post, nicely broken down and explained. Did you do more investigation into whether it would work well for worm-like levels?

    Also I found that I got better connectivity starting with a “worm” or digger which dug out the initial layout of the cave and then ran the automata, than starting with random points.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: