Categories
personal blog procedural generation series tutorial

Procedural Generation in GMS #3: Creating Sweet Maps with Cellular Automata

In this entry, we dive into the fascinating world of map generation using Cellular Automata.


THE ENTIRE SERIES

More to come…


Note: None of the code for any of these proc-gen tutorials is highly optimised. My goal was to get the concepts across as simply as possible, rather than to make them run as fast as possible. Use the following as a springboard for further learning and experimentation, rather than as the best solution possible.

Also, if you are a complete beginner, it’s probably best to start at the first entry and work your way through, as further into the series we get, the more knowledge from previous entries is assumed.

23/01/2021 UPDATE: I’ve altered some of the code in this tutorial and added some new explanations to cover the keyword static, which adds a small bit of optimisation to the overall functionality. Thanks to SamSpade for pointing this out.

In my last post, I had a poll to determine what to cover next. Cellular Automata and Bresenham’s line algorithm tied for first place. I chose to do Cellular Automata because I think it is a bit easier to understand than Bresenham’s for beginners. I also think that it’ll give me a good chance to do some in-depth explanations of some common coding practices (such as loops) for beginners without having to try to tackle more complicated maths/algorithms at the same time. I’m going to try to go very beginner friendly on each coding pattern as we first touch on them, and then we can continue quicker for the following tutorials when they touch on the same patterns without having to do the explanations again.

If you really wanted Bresenham’s though, don’t worry. I will be covering it next.


Contents

WHEN CELLS AUTOMATE

MAKING OF A MAP

EVERYBODY NEEDS GOOD NEIGHBOURS

TO BE EMPTY, OR NOT TO BE EMPTY, THAT IS THE QUESTION

RINSE AND REPEAT

THE BIG PICTURE

CLOSING NOTES

THE NEXT STEP


WHEN CELLS AUTOMATE

So what exactly is cellular automata? If you’ve literally never heard the term before, the gif at the top of the page is an example of cellular automata (which I will now refer to as CA, my fingers type enough crap every day as it is). A while back, a dude named Conway invented a neat little game called Conway’s Game of Life.

An example of one of the creations possible in Conway’s Game of Life. Credit Wikipedia.

The basic premise is that you start with a blank grid. Before the game starts, you choose which grid cells in the grid to turn on or leave blank. The cells that are turned on are considered “alive” and they react to the cells immediately around them. Too many neighbours and a cell will die from “overpopulation”, too few neighbours and a cell will die from “underpopulation”, the right number of neighbours and a cell will “live” on to the next generation and, finally, if a blank cell has a certain number of neighbours, it will become alive through “birth”. Using just these simple rules, some very complex behaviour sprung up (such as the Gosper’s Glider in the gif above).

Well, being an enterprising lot, game developers decided that this was too cool to just leave as a curiosity and they decided that it might be useful for proc-gen.

So instead of letting the simulation run for extended periods of time and watching it unfold, people figured out that if you set the rules right and iterated the living/death/birth cycle for a limited number of steps, it would generate a map that looked pretty cave-like. And thus CA was born as a map generation technique in proc-gen.

That’s what we’re going to be building today. However, for our version, we’ll change the rules a little. Our rules will be:

  1. Any live cell with less than X neighbours will die.
  2. Otherwise, the live cell will live to the next generation.
  3. Any dead cells with more than X neighbours will become alive (“birth”).
  4. Otherwise, the dead cell stays dead.

You can definitely play around with these rules (I will point out in the tutorial where it might be appropriate) and the maps that will be created will change pretty drastically depending on what rules you apply.

So we’ll set up the functions to generate a CA map, then we can run it whenever we need to create a map and use the output to figure out where to place things, like walls/ground or water/land, etc, by using the living/dead cells as markers. Let’s get on with it.


MAKING OF A MAP

First things first, create a new script and call it something (I’ve called mine cell_auto_funcs), almost everything we’re going to do will be done inside of this script.

Now what we need to do is initialise a map (we’ll be using a 2D array to simulate a grid for this). We’ll be doing each of these sections piecemeal and then putting them all together properly at the very end of the tutorial. As a note, I have three macros created, CELLSIZE (which is equal to 4), EMPTY (which is equal to 0) and SOLID (which is equal to 1). We’ll initialise them later on in the tutorial, but just be aware that that is what EMPTY relates to in the code below. So let’s create a method variable called CreateMap inside the script and assign it a function:

Beginners Note: If you don't know how to use arrays, read the previous entry in this series.We'll be using a neat little trick called a double for() loop to initialise the correct number of slots for the width and height of the 2D array. A for() loop takes 3 arguments: the start of the count, what value the count needs to get to before the loop ends, and how much the count should increase by each loop. The format is like this:

for (count=0;count<5;count+=1) { // Code goes here }

In the above example, the // Code goes here comment will be run 5 times and each time it runs, count will be increased by 1. The loop will end when count hits 5 and then any code that exists after the loop will execute. This means that an improperly used loop will completely freeze your game. You might also notice that I sometimes use my_var++ instead of my_var += 1. In this case, my_var++ and my_var += 1 do exactly the same thing, I just use ++ because it is quicker to type.
CreateMap = function() {
	///@func	CreateMap();
		
	var _map; // Create a temporary variable to hold our 2D array
	for (var xx=0;xx<map_width;xx++) { // Loop through the width/columns we want
		for (var yy=0;yy<map_height;yy++) { // Loop through the height/rows we want
			_map[xx][yy] = EMPTY; // Set the 2D array to EMPTY at cell xx,yy
		}
	}
		
	return _map; // Return the 2D array
}

This is relatively simple. We’re assigning a function to the method variable CreateMap. In that function we create a temporary variable to hold the 2D array called _map. We then do a double for() loop. The first for() loop relates to the column position of the 2D array (we use xx as a temp variable for the column/width). The second for() loop relates to the rows of the 2D array (here we use yy as a temp variable for the rows/height).

In the first execution of the loop, xx = 0 and yy = 0, if you remember how spreadsheets work, the cell at column 0 and row 0 is the very first cell. So we’re setting the first cell to EMPTY. Then the yy for() loop executes again, so xx = 0 and yy = 1, and that relates to the second cell heading directly downwards on a spreadsheet (column 0 and row 1). yy will continue to loop (xx = 0, yy = 2; xx = 0, yy = 3; etc) and increase until it hits whatever value map_height-1 is. Then xx will increase by 1 and yy will loop again from 0 to height (so now xx = 1, yy = 0; xx = 1, yy = 1, etc). This pattern continues until xx = map_width-1 and yy = map_height-1. Why map_width-1 and map_height-1? As I explained in the last post, computers generally count from 0, so from 0 to map_width-1 is the same as a human counting from 1 to map_width (and the same goes for height).

This is the most common way of looping through every cell of a grid-like structure (and loops are very common when programming). There are other loop structures we could use, but for() is fine to use for this.

So we’ve initialised our 2D array and set every cell in it to the macro EMPTY. Now we have to randomly turn some cells SOLID. We’ll use the same for() loop structure to do this, along with a random number.

RandomiseMap = function(_map,_spawn_chance) { // We supply the map we want to randomise, along with the chance each cell has of being turned SOLID (between 0 and 100, think of it as a percentage)
	///@func	RandomiseMap(_map,_spawn_chance);
	///@param	_map			The current map
	///@param	_spawn_chance	The chance that each cell is turned SOLID
		
	for (var xx=0;xx<map_width;xx++) {
		for (var yy=0;yy<map_height;yy++) {
			var _roll = random(100); // Choose a random number between 0 and 100
			if (_roll <= _spawn_chance) { // If the roll is less than or equal to the spawn chance we supplied
				_map[xx][yy] = SOLID; // We set the current cell to SOLID
			}
		}
	}
	return _map; // Return the map when we are done
}
Beginners Note: You might have seen the comments ///@func and ///@param in the previous two code blocks. These are JSDoc style comments, and they let us tell GMS what the function is called and what arguments it takes, which adds proper syntax highlighting and also lets us view the arguments the function should take in the little info bar at the bottom of the code window. There are three I use commonly, ///@func, ///@desc and ///@param.

Additionally, you might notice that I preface a lot of variables with an underscore: _my_var. I do this to make a distinction between local variables (that only exist for the scope of the current Event/function) and instance variables (which are accessible from anywhere inside the instance they were created in). An underscore denotes a local (or temporary, as they are sometimes referred to as) variable, a lack of an underscore denotes an instance variable.

This is pretty similar to what we did before, we loop through each cell of the map, but instead of just setting them to EMPTY, we get a random number and compare that to _spawn_chance, and set the cell to SOLID if the random number is less than or equal to _spawn_chance.

We could combine the two functions above into one function easily (and it would optimise the code, as we would only have to loop through the whole map once). But I wanted to separate them to better explain what was happening. That’s the end of us creating our map. Now let’s move on to the automata section of CA.

Beginner Challenge: See if you can take the important parts of the RandomiseMap function and insert them into the CreateMap function so that we only have to loop through the map once. Hint - An else conditional might be involved.

EVERYBODY NEEDS GOOD NEIGHBOURS

If you recall from the start of the tutorial, the cells react to other cells around them. So we need some way of detecting the neighbours for each cell. We’ll use a “true” function for this, not a method variable and we’ll call it CountNeighbours().

function CountNeighbours(x,y,_map) { // We input the x (or column) and y (or row) of the cell we want to access, as well as the map we are using
	///@func	CountNeighbours(x,y,_map);
	///@param	x				The current cell's x position
	///@param	y				The current cell's y position
	///@param	_map			The current map
		
	var _count = 0; // This will keep track of how many neighbours are solid
	for (var dx=-1;dx<2;dx++) { 
		for (var dy=-1;dy<2;dy++) { // Double for loop again, but this time a variant explained below
			var xx = x+dx; // Get the x position of the neighbour cell
			var yy = y+dy; // Get the y position of the neighbour cell
			if (xx < 0 || yy < 0 || xx >= map_width || yy >= map_height) { // If the neighbour cell we are trying to check is out of bounds
					
				/* We have two choices here: either act as though any neighbours outside of the
				grid are SOLID or act as though they are EMPTY. The cellular automata will behave
				differently depending on which we choose. I've chosen to act as though they are
				SOLID */
					
				_count++; // Add to count because we decided to act as though out of bounds cells are SOLID
			}
			else if (dx == 0 && dy == 0) {
				continue; // If dx and dy equal 0, then we are checking the supplied cell, not it's neighbours, so skip it with a continue
			}
			else {
				var _neighbour = _map[xx][yy]; // Get the value of the neighbour cell
				if (_neighbour == SOLID) { // If the value of the neighbour is SOLID
					_count++; // Add to the solid count
				}
			}
		}
	}
	return _count; // Finally, return the SOLID count
}

This code block is a little more complicated than what we’ve dealt with so far. The basic premise is that we supply the coordinates of a cell, and then we check each cell from the top-left to the bottom-right around the supplied cell, adding to _count for each neighbour that is SOLID.

But let’s break the code down a little bit. What in dear god is this black magic?

for (var dx=-1;dx<2;dx++) { 
	for (var dy=-1;dy<2;dy++) {

Well, if you imagine dx = 0 and dy = 0 as the “center”, then dx = -1 and dy = -1 is the top-left and dx = 1 and dy = 1 is the bottom right. So this loop is giving us the relative coordinates for cells around our supplied cell (in fact, dx = 0 and dy = 0 IS our supplied cell, which is why we have an if conditional checking for that and continue if the conditional is true).

Beginners Note: continue is a key word forces a loop structure to "skip" the rest of one of it's loops. break; is another key word that exits the loop entirely.

After that we have var xx = x+dx; and var yy = y+dy;. Remember that x and y refer to the absolute coordinates of the cell we want to check the neighbours of. If we supply x = 5 and y = 5, and the loop has just started so dx = -1 and dy = -1, then xx = 4 and yy = 4. If we think back to spreadsheets again, the cell to the top-left of column 5, row 5 will be column 4, row 4. All of this is a long-winded way of saying that as this loop executes, xx and yy will end up pointing to each neighbouring cell around our supplied cell (as well as our supplied cell itself when dx = 0 and dy = 0). Knowing that, it’s a simple matter of checking if _map[xx][yy] == SOLID and adding to _count if it is.

However, there is one more thing in there I haven’t touched on yet:

if (xx < 0 || yy < 0 || xx >= map_width || yy >= map_height) {

Our map has bounds. Those bounds start at 0 and go to map_width-1 and map_height-1. Those are the “borders”, so to speak. What we are doing here is checking to see if the neighbour we are trying to look at is outside of our map. || is a fancy way of saying “or” (the same way as && is a fancy way of saying “and”) in coding. So we are essentially saying if xx is less than 0 or yy is less than 0 or xx is greater than our map width or yy is greater than our map height then do “something”. If any of those are true, we know that we are trying to access an out of bounds area. We can treat out of bounds as either SOLID or EMPTY. Both work fine (they will result in different looking maps though, depending on which you pick). But if we decide to ignore this completely, the game will crash! This is because we are not allowed to access map[-1][yy] (if xx = -1, in this case) or map[xx][-1] (if yy = -1), the same goes for trying to access greater than the map width or map height. Trying to access a part of an array that hasn’t been assigned a value (such as an out of bounds part) will result in the game crashing. So we have to handle it using the if...else if...else conditionals that you can see in the code block.

I’ve decided to treat the out of bounds areas as though they are SOLID in this case, so I add 1 to _count (if I wanted to treat it as EMPTY, I simply wouldn’t have any code in the else if conditional.

Beginners Note: If you check the code block, you will see that sometimes I use = and sometimes I use ==. A single equals = is used to assign a value, whereas a double equals == is used to compare values. So if I want to make a variable called my_var equal 5, I will use my_var = 5. However, if I want check if my_var equals 5, I will use if (my_var == 5) { }. GMS will let you get away with doing a single equals for everything, but it's a bad habit to get into as other languages do not let you do this, so develop good habits early by using = for assignment and == for comparison.

Finally, we return _count. And we have a nice little function that we can call to check how many solid neighbours a specific cell has.

The reason this has to be a function and not a method is because we want to be using the static keyword for the method variables later on (and I will explain what that is when we get to it), and with the way scoping works, this won’t work as a static method and instead needs to be a function on it’s own.


TO BE EMPTY, OR NOT TO BE EMPTY, THAT IS THE QUESTION

The second last function that we need to write for the CA is the function that evolves the cells over time. We’ll store it in a method variable called Iterations.

Iterations = function(_old_map,_create_limit,_destroy_limit) { // Pass in the currently existing map and the create and destroy limits
	///@func Iterations(_old_map,_create_limit,_destroy_limit);
	///@param	_old_map		The map as it currently stands
	///@param	_create_limit	The neighbour count that will turn an EMPTY cell SOLID
	///@param	_destroy_limit	The neighbour count that will turn a SOLID cell EMPTY
		
	var _new_map = []; // Create a new map to modify
	for (var xx=0;xx<map_width;xx++) {
		for (var yy=0;yy<map_height;yy++) {
			var _count = CountNeighbours(xx,yy,_old_map); // Check how many SOLID neighbours the current cell has on the old map
			if (_old_map[xx][yy]) { // If the old map cell is SOLID
				if (_count < _destroy_limit) { // If the SOLID neighbour count is less that the "underpopulation" limit
					_new_map[xx][yy] = EMPTY; // Set the corresponding cell on the new map to EMPTY
				}
				else { // Otherwiise if the SOLID neighbour count is greater than the "underpopulation" limit
					_new_map[xx][yy] = SOLID; // Set the corresponding cell on the new map to SOLID
				}
			}
			else { // If the old map cell is EMPTY
				if (_count > _create_limit) { // If the neighbour count is greater that the "birth" limit
					_new_map[xx][yy] = SOLID; // Mark the corresponding cell on the new map to SOLID
				}
				else { // Otherwise
					_new_map[xx][yy] = EMPTY;
				}
			}
		}
	}
	return _new_map;
}

Let’s go over that code block. First, we want to create a “new” map. This is because we don’t want the current results of the processing to be influencing future results in the same iteration until we have fully iterated through the map. In other words, if we are working on a cell at position x:2,y:2 and we change that cell from EMPTY to SOLID, when we move onto the cell at position x:3,y:2, it will be influenced by the change on cell x:2,y:2. We don’t really want that to happen. We get around this problem by creating a new map, doing our checks on our old map and applying changes to the new map, before finally updating the old map to equal the new map after the whole map has been iterated over. We could just work with the old map and let current changes influence the future results, but that tends to make the resulting maps look much less like a cave with walls/floors and more like a world map with landmass/water (and it also requires a bit more precise tuning of the spawn chance and death/birth limits to get good results).

In any case, we loop through the map for each cell, storing the number of SOLID neighbours for the current cell in the _count variable. Then we do some checks.

If the current cell is SOLID, we check to see if the neighbour _count is less than the “underpopulation” limit. If it is, we set the corresponding cell on the new map to EMPTY. If it isn’t, we set the corresponding cell on the new map to SOLID (this is the equivalent of the cell living on to the next generation).

If, instead, the current cell is EMPTY, we check to see if the neighbour _count is greater than the “birth” limit. If it is, we set the corresponding cell on the new map to SOLID and if it isn’t we set the corresponding cell on the new map to EMPTY.

You can mess around with this section if you want. Try to think of some different ways you could check the neighbours. For instance, you could more closely adhere to Conway’s original rules and have it so that there’s an “underpopulation” check for SOLID cells (It would be another else if inserted when the current cell is SOLID). Or whatever you like. Small changes in these rules can lead to drastically different results.

After we’re done completely iterating over the map, we return the new map and move on to the next section.


RINSE AND REPEAT

This is where it all starts to come together. We will take the methods that we have created and insert them into a larger function structure (all except the CountNeighbour() function, which is not a method) that automatically does all the above steps necessary for creating a CA map and then have that larger function return the map at the end, so we will simply be able to type cell_map = RunCellularAutomata(arguments); and cell_map will end up holding the fully realised CA map we want.

We’re going to create a “plain” function, not a method variable, and you should notice that all the previous methods we created are actually inside of this one (so if you’ve been typing up your own version as you’ve been reading, create this function and then copy and paste what you’ve already typed inside of it). Let’s get on with it:

#macro EMPTY 0
#macro SOLID 1
#macro CELLSIZE 4
function CountNeighbours(x,y,_map) { // We input the x (or column) and y (or row) of the cell we want to access, as well as the map we are using
	///@func	CountNeighbours(x,y,_map);
	///@param	x				The current cell's x position
	///@param	y				The current cell's y position
	///@param	_map			The current map
		
	var _count = 0; // This will keep track of how many neighbours are solid
	for (var dx=-1;dx<2;dx++) { 
		for (var dy=-1;dy<2;dy++) { // Double for loop again, but this time a variant explained below
			var xx = x+dx; // Get the x position of the neighbour cell
			var yy = y+dy; // Get the y position of the neighbour cell
			if (xx < 0 || yy < 0 || xx >= map_width || yy >= map_height) { // If the neighbour cell we are trying to check is out of bounds
					
				/* We have two choices here: either act as though any neighbours outside of the
				grid are SOLID or act as though they are EMPTY. The cellular automata will behave
				differently depending on which we choose. I've chosen to act as though they are
				SOLID */
					
				_count++; // Add to count because we decided to act as though out of bounds cells are SOLID
			}
			else if (dx == 0 && dy == 0) {
				continue; // If dx and dy equal 0, then we are checking the supplied cell, not it's neighbours, so skip it with a continue
			}
			else {
				var _neighbour = _map[xx][yy]; // Get the value of the neighbour cell
				if (_neighbour == SOLID) { // If the value of the neighbour is SOLID
					_count++; // Add to the solid count
				}
			}
		}
	}
	return _count; // Finally, return the SOLID count
}
function RunCellularAutomata(_map_width,_map_height,_spawn_chance,_create_limit,_destroy_limit,_iterations) {
	///@func	RunCellularAutomata(_map_width,_map_height,_spawn_chance,_create_limit,_destroy_limit,_iterations);
	///@param	_map_width		The width of the map
	///@param	_map_height		The height of the map
	///@param	_spawn_chance	The chance a cell is turned SOLID
	///@param	_create_limit	The neighbour count that will turn an EMPTY cell SOLID
	///@param	_destroy_limit	The neighbour count that will turn a SOLID cell EMPTY
	///@param	_iterations		The number of iterations we want to perform on the map
	
	map_width = _map_width;
	map_height = _map_height;
	
	static CreateMap = function() { // When we call CreateMap we will supply the w (or width) and h (or height) that we want
		///@func	CreateMap(w,h);
		///@param	w	Map width
		///@param	h	Map height
		
		var _map; // Create a temporary variable to hold our 2D array
		for (var xx=0;xx<map_width;xx++) { // Loop through the width/columns we want
			for (var yy=0;yy<map_height;yy++) { // Loop through the height/rows we want
				_map[xx][yy] = EMPTY; // Set the 2D array to EMPTY at cell xx,yy
			}
		}
		
		return _map; // Return the 2D array
	}
	
	static RandomiseMap = function(_map,_spawn_chance) { // We supply the map we want to randomise, along with the chance each cell has of being turned SOLID (between 0 and 100, think of it as a percentage)
		///@func	RandomiseMap(_map,_spawn_chance);
		///@param	_map			The current map
		///@param	_spawn_chance	The chance that each cell is turned SOLID
		
		for (var xx=0;xx<map_width;xx++) {
			for (var yy=0;yy<map_height;yy++) {
				var _roll = random(100); // Choose a random number between 0 and 100
				if (_roll <= _spawn_chance) { // If the roll is less than or equal to the spawn chance we supplied
					_map[xx][yy] = SOLID; // We set the current cell to SOLID
				}
			}
		}
		return _map; // Return the map when we are done
	}
	
	static Iterations = function(_old_map,_create_limit,_destroy_limit) { // Pass in the currently existing map
		///@func Iterations(_old_map,_create_limit,_destroy_limit);
		///@param	_old_map		The map as it currently stands
		///@param	_create_limit	The neighbour count that will turn an EMPTY cell SOLID
		///@param	_destroy_limit	The neighbour count that will turn a SOLID cell EMPTY
		
		var _new_map = []; // Create a new map to modify
		for (var xx=0;xx<map_width;xx++) {
			for (var yy=0;yy<map_height;yy++) {
				var _count = CountNeighbours(xx,yy,_old_map); // Check how many SOLID neighbours the current cell has on the old map
				if (_old_map[xx][yy]) { // If the old map cell is SOLID
					if (_count < _destroy_limit) { // If the SOLID neighbour count is less that the "underpopulation" limit
						_new_map[xx][yy] = EMPTY; // Set the corresponding cell on the new map to EMPTY
					}
					else { // Otherwiise if the SOLID neighbour count is greater than the "underpopulation" limit
						_new_map[xx][yy] = SOLID; // Set the corresponding cell on the new map to SOLID
					}
				}
				else { // If the old map cell is EMPTY
					if (_count > _create_limit) { // If the neighbour count is greater that the "birth" limit
						_new_map[xx][yy] = SOLID; // Mark the corresponding cell on the new map to SOLID
					}
					else { // Otherwise
						_new_map[xx][yy] = EMPTY;
					}
				}
			}
		}
		return _new_map;
	}
	
	var _ca_map = CreateMap(map_width,map_height);
	_ca_map = RandomiseMap(_ca_map,_spawn_chance);
	
	repeat(_iterations) {
		_ca_map = Iterations(_ca_map,_create_limit,_destroy_limit);
	}
	
	return _ca_map;
	
}

The very first thing we do is to setup our macros. We want one for EMPTY, one for SOLID and one for our CELLSIZE. You should know by now what EMPTY and SOLID are used for, but what about CELLSIZE? This is the “multiplier” for the size of our cells when we go to draw the map later. If you set it to 1, each cell of the grid will be 1 pixel in size, leading to a pretty small display of the map. A common value for a full size playable map in a pixel game would be 32. But we will set ours to 4 (meaning each cell will be 4 pixels wide and 4 pixels tall when it is drawn), which allows us to see the full map without having to scroll around the room or fullscreen the game.

Then we create our RunCellularAutomata() function. This is a proper function and not a method, as we have been creating before. Inside the function, we first create two instance variables called map_width and map_height. This will “save” the width and height we provide in the arguments of the function as instance variables in the instance we call the function from, which is useful both later on in the method variables (as we don’t need to keep passing them in as arguments) and also if we want to work with the map somewhere else in the same instance (if we wanted to draw the map in the Draw Event, as an example).

One thing to note here, if you look through the above code block, I’ve added the keyword static before some of the methods (basically every one except CountNeighbours(), which isn’t a method, as I mentioned earlier). What this does is make it so that those method variables are only ever defined once. This helps cut down on extraneous instance variables (each method will create a new variable in the instance running it, if static is not used) and also helps the garbage collection, as the garbage collector doesn’t have to clean up the “old” methods if we rerun RunCellularAutomata() again. Without static, each time we run the function it will overwrite the methods that were created the first time the function was run with new methods that hold exactly the same functionality, meaning that the “old” methods lose their reference and have to be garbage collected. This is just a small piece of optimisation, but it is useful to learn about.

Then we have all the previous methods we have created, which we don’t need to go over and finally, we actually use the method variables we have created to generate the map. If you’ve noted that we keep putting return X; at the end of the functions, this is why. First of all we call the method variable CreateMap() and store the returned map into a temporary variable called _ca_map (I named it that for cellular automata map, but you can name it whatever you like).

Beginners Note: return basically spits out whatever variable we give it after the function has run. So if we have a function called MyFunction that ends with return 1;, by typing my_var = MyFunction();, we make it so that my_var will end up holding the value 1, because that is what the function returns.

Then we randomise the map by sending it to RandomiseMap() with the appropriate arguments. That is followed up by a repeat(X) loop, which runs the code inside it as many times as X equals. This is our iterations for the cellular automata. Each time repeat() runs, our whole map is iterated over, and the cells are turned SOLID or EMPTY based on their neighbours, then the map is updated and the loop repeats again. The more iterations we tell it to do, the “smoother” the map will become. Later on, when we called the RunCellularAutomata() function, try supplying 1 for the _iterations argument and then try providing 25 for the _iterations argument. You should notice that the more iterations, the more “rounded” the SOLID and EMPTY sections become.

After we’ve finished with the iterations, we return the map. And that means our function work is done (or at least, the cellular automata part of it is).


THE BIG PICTURE

We’ve now got everything setup to actually create our map, so let’s go ahead and create an object, named whatever you like (I call mine obj_cell_auto). In the Create Event, type in this:

cell_map = RunCellularAutomata(75,75,65,5,5,10);

We create a new instance variable called cell_map (obviously, again, you can name it whatever you like) and assign it to the return value of our RunCellularAutomata function (which is the map we create inside of that function). The arguments we provide are, in order:

  1. Map width (75)
  2. Map height (75)
  3. Spawn chance (65)
  4. Create limit (5)
  5. Destroy limit (5)
  6. Iterations (10)

The values I’ve provided there should give pretty good results for cave-like maps, but this is where you can play around with the values and see how the map changes based on what you input. Try smaller create or destroy limits, or change the spawn chance. Try doing fewer iterations or more. The world is your oyster. However, a lot of that oyster can be useless, which is where iteration and experimentation come into the PCG side of things. The more you experiment and toy with the values, the more likely you are to hit upon a combination that yields the results you want. So don’t be afraid to alter > test > alter > test > etc.

But before you can actually see the results of your map, we have one final thing to do, which is draw the map itself to the screen. So open up our cell_auto_funcs script (or whatever you called it), as we’re going to create one more function to draw the map.

function DrawMap(_map,x,y) {
	///@func	DrawMap(_map,x,y);
	///@param	_map	The map we want to read
	///@param	x		The x position to start drawing the map at
	///@param	y		The y position to start drawing the map at
	
	for (var xx=0;xx<map_width;xx++) {
		for (var yy=0;yy<map_height;yy++) {
			var x1 = x+xx*CELLSIZE;
			var y1 = y+yy*CELLSIZE;
			var x2 = x1+CELLSIZE;
			var y2 = y1+CELLSIZE;
			if (_map[xx][yy] == SOLID) { // If the current cell is solid, set the colour to a light colour to signify a wall
				draw_set_color(make_color_rgb(102,100,112));
			}
			else {
				draw_set_color(make_color_rgb(13,11,16)); // Otherwise set the colour to a darker colour to signify a floor
			}
			draw_rectangle(x1,y1,x2,y2,false); // Draw a rectangle representing the cell
		}
	}
}

First we create a new function called DrawMap(), it takes our map and an x and y position as arguments. The x and y positions are basically where on the screen the top left corner of our map will start. Then we loop through our map and start finding the positions for each cell. If we have a look at these lines var x1 = x+xx*CELLSIZE; we can see that we take the position we want to start drawing at (x) and add whatever column we are at (xx) multiplied by the CELLSIZE macro. So if we are looking at all the cells in column 0 and we provide 10,10 as the x and y arguments, the computer will do this:

 x = 10
+
xx = 0 * CELLSIZE
=
10+0
= 10

So all our cells of column 0 will be drawn at an x position of 10 (with y changing based on what row is being drawn). If we run through the loop a few times so we are looking at cells in column 1 we will get:

x = 10
+
xx = 1 * CELLSIZE
=
10+4
=
14

Which means all the cells in column 1 will be drawn at an x position of 14, or shifted over by 4 pixels (our CELLSIZE). The more columns we go along, the higher the shift will be (the next column will be shifted by CELLSIZE again to end up equaling 18 and so on). This lets us draw our map as a grid and modify the size of the cells simply by changing the value of CELLSIZE.

Then we just look at whether the current cell is SOLID or EMPTY, set an appropriate draw_set_color() depending on the result, draw a rectangle and viola, we end up with a nicely drawn grid showing us what our map looks like.

If we wanted to create wall objects instead of just drawing the map, we would use pretty much the same format, except we would create instances at the x1 and y1 position, rather than drawing a rectangle, like this:

function CreateWalls(_map,x,y) {
	///@func	CreateWalls(_map,x,y);
	///@param	_map	The map we want to read
	///@param	x	The x position to start creating instances at
	///@param	y	The y position to start creating instances at
	
	for (var xx=0;xx<map_width;xx++) {
		for (var yy=0;yy<map_height;yy++) {
			var x1 = x+xx*CELLSIZE;
			var y1 = y+yy*CELLSIZE;
			if (_map[xx][yy] == SOLID) {
				instance_create_layer(x1,y1,layer,obj_wall);
			}
		}
	}
}

The only thing we would need to change is what Event we called the function from (drawing the map should be called in the Draw Event, obviously, whereas creating instances should be done in the Create Event after the map has been created).

So finally, let’s call the DrawMap function in the Draw Event for our obj_cell_auto (or whatever you called it).

DrawMap(cell_map,10,10);

Replace cell_map with whatever you called your map. This will draw the map at x:10,y:10, change it however you see fit. Now drag your obj_cell_auto into your room and run the game. Hopefully you should see a cellular automata map being drawn in your room. Hoorah!


CLOSING NOTES

We’ve had a lot to go over in this tutorial and I’ve tried to break down any bits that are potentially confusing, especially common coding patterns, as best I can. As we go further into the proc-gen world, these long-winded explanations will get less and less frequent as we can re-use coding patterns we have already discussed. So if you already understood a lot of the stuff I covered, don’t worry, it won’t all be so basic.

One of the problems with CA (and a lot of map generation techniques) is unreachable/unplayable areas. For instance, if you just place down a player and a goal in random EMPTY spots using just this basic CA generator, there’s a chance there won’t be a path from the player to the goal. There’s a few ways to fix this, but one of the more common ones is pathfinding, which we will be covering in a future entry in the series (if the pathfinding algorithm can’t find a path from the player to the goal, you can throw out the map and regenerate a new one, until one with a successful path is created, as a basic example). As we go along, you’ll add more and more tools to your coding tool-belt to help you deal with any potential problems like that. However, I think this is a good enough spot to stop.

Finally, here is an exported project file if anyone wants to have a look at how I implemented the automata, or the settings changer in the gif at the start: Cellular Automata Project


THE NEXT STEP

As I said at the start of this entry, Bresenham’s and CA tied for first place, so I’ll be covering Bresenham’s line algorithm next and that should lead us neatly into some of the other topics which use Bresenham’s as part of their generation.

Read on with #4: Connecting the Dots with Bresenham’s.

If you’ve got any comments, criticisms or advice don’t hesitate to comment and let me know, I’m always happy to hear feedback from readers. And if you like what I’m doing, consider supporting me through either a donation at the bottom of the page or buying my game Spaceslingers!


Sign up to get notified whenever I upload a blog post, so you don’t miss any of the next installments!

By RefresherTowel

I'm a solo indie game developer, based in Innisfail, Australia.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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