# GMS 2.3+Beginners Proc Gen in GMS #3: Generating Sweet Caves with Cellular Automata

#### RefresherTowel

##### Member
GM Version: 2.3+
Target Platform: All

Other Entries:
Summary:
The third entry in my on-going series about Procedural Generation in GMS. In this entry, we learn how to use the Cellular Automata algorithm to create some sweet looking cave maps. This series is aimed at beginners and intermediate users alike, so don't be afraid to have a read even if you no idea what Cellular Automata is or you feel like it might be too hard for you to implement.

Tutorial:

Procedural Generation in GMS #3: Cellular Automata

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

---

Section 1: 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 have 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”).
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.

---

Section 2: 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 two macros created, `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.

Code:
``````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
}``````
So 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 height we specify when we call the `CreateMap` method variable. 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 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.

Code:
``````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 toolbar 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.

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

---

Section 3: 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 another function assigned to the method variable `CountNeighbours`.

Code:
``````CountNeighbours = function(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
map 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, removing this line acts as though they are EMPTY
continue;
}
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?

Code:
``````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 keyword that will exit 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` as arguments, 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:

Code:
``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.

---

Read the rest of the tutorial to find out how to make the cells mutate based on what is around them and how to use the map in-game!

Last edited: