## 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:

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).

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;
continue;
}

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;
break;
default:
break;
}
}

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.

image.save("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);
image.save("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 image.save 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:

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):

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:

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.