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

GM Version: 2.3+
Target Platform: All
Download: Exported GMS File
Links: Read the full tutorial here

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

---

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:

samspade

Member
Here is a video tutorial following mostly the same code (posted with permission). I didn't incorporate sliders into this tutorial though, and I kind of regret it as the sliders make experimenting way easier, so if you're actually going to download code, I'd get his. Thanks again to @RefresherTowel for letting me work off of his stuff!

 
Top