Tag Archives: c++

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.

	image.save("cave.bmp", 0); //Save original image

	int count = 0;

	for (int i = 0; i < 5; i++)
	{ //Perform algorithm on image 5 times.
		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:

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 , , , , , , ,

Getting back into the swing of things.

So I haven’t blogged for quite some time, a really long time in fact. This is because of a few of reasons: (1) I wasn’t up to much and then (2) I went on holiday with my parents and girlfriend for a couple of weeks. Oh and now I’m enjoying another two week break with my girlfriend’s family. This hasn’t left much time for doing much programming or work towards my Final Year Project, so whilst on this current break I’ve started doing a bit of programming again!

I hadn’t touched C++ since finishing my 2nd year and so thought I best freshen up on what I know and even perhaps learn a bit more. At the moment my sole resources for this are cplusplus.com and r/dailyprogrammer. I’m pretty certain almost every C++ programmer will already know about cpp.com, I’ve found that whenever I google something about the language it’s often one of the first results.

screen cap of r/dailyprogrammer

r/dailyprogrammer is a subreddit where any programmer, no matter what language he/she uses, can get involved. Every day a mod will submit three challenges: easy, intermediate and difficult. These challenges are submitted by followers of the subreddit and can be completed by anybody feeling up to it. It’s a great way to keep your programming in shape as well as learning new things, not just by looking at other people’s solutions but also by the challenges themselves. You may find yourself learning new algorithms for many different things such as encoding/decoding. You may even learn things not related to programming; some challenges will be based around a subject you don’t know much/anything about so will need to go off and find the information you need. It seems like a really friendly community and I plan to take part more by posting my own solutions.

So to finish off, I’ve learnt quite a bit in the last few days from just looking at solutions on r/dailyprogrammer and looking up the things I didn’t know on cplusplus.com. As of now I’ve only completed one challenge myself, and it was an easy one. But I’m out of practice and I don’t want to throw myself back in the deep end, I’m happy enough working myself up learning new things on the way. I might start doing posts of new things I learn actually, I suppose it would help embed the knowledge in my head a little better by trying to describe it myself. I think it was Albert Einstein who said: “If you can’t explain it simply, you don’t understand it well enough.”.

Tagged , , , , , , , ,