GML Cellular Automata (Cave generation)

Bingdom

Googledom
GM Version: GMS 1.4.1773
Target Platform: ALL
Download: N/A
Links: N/A

Summary
Cellular Automata is a discrete model which can be used for procedural cave generation.

Cellular Automaton.gif

Required knowledge
  • ds_grid
  • loops (for, repeat)
  • scripts, arguments

Tutorial

In this setup, we will be using ds_grids. For each cell, it will represent either a 1 (wall) or a 0 (empty).
The process goes like this:
  1. Generate random noise inside our grid, based on fillPercentage.
  2. For every cell, we will check neighbouring cells. If there are not enough neighbouring walls, kill the wall. If there's enough, create a new wall on our check position.
  3. Repeat step 2 several times.
  4. Create tiles based on the data from our ds_grid (So we can see it)
First things first, we will eventually upscale our tiles. It's important that we disable pixel interpolation so that things draw correctly. Global Settings -> Windows -> Uncheck Pixel interpolation. Let's create a background for our tileset. Create a background with a size of 4x2. Make the left half a dark brown (or any colour of your choice, as long as it helps you see it as the ground) and the right half a brighter colour.
upload_2017-11-15_0-22-48.png

Now, we will need a generator object.
Create one and place it in a room.
Make the room a size of 1024x576.

In the create event, we will need some initialization code. This is a pretty standard setup for a grid.
Code:
randomize(); //Get a different seed every launch
cellSize = 8; //The size for each terrain block

//This will give us the size for our data grids
width=room_width div cellSize;
height=room_height div cellSize;

//Create the grid
mapData = ds_grid_create(width,height);
Lastly, these variables are important for our generator scripts. These also belong in our object's create event.
Code:
//Threshold to determine if the cell is either a 1 or 0. 45 is a good value. Should be between 0 - 100.
fillPercentage = 45;

//The number of times we will iterate through our smoothness script
smoothness = 5;
Now that we have initialized our variables, time to do the generator scripts! This is step 1 for the main process.

We now need to fill our grid with random noise, using the variable fillPercentage
Let's create a new script. Call it scrGenerate. Make sure to call it inside our object's create event.

Inside
scrGenerate, let's create a nested loop to iterate through every cell.
Code:
for (var j = 0; j < height; j ++) {
    for (var i = 0; i < width; i ++) {

    }
}
Now, inside the nested for loop, we need to determine if it should be a wall or not.
Code:
if ( irandom(100) < fillPercentage ) {
        mapData[# i, j] = 1;
    } else {
        mapData[# i, j] = 0;
    }
}
Basically what happens; if irandom is less than fillPercentage, make the cell a 1 (wall). otherwise, make it 0 (empty).
upload_2017-11-15_0-53-25.png
This is working great! However, look at the borders... You can see that there's no wall borders. The player can escape! We don't want that.

A way to fix that would be to run a check inside that loop that would automatically make it a wall if the cell is along the border.
Code:
(i == 0 or i == width-1 or j == 0 or j == height-1)
The final code should look like this:
Code:
for (var j = 0; j < height; j ++) {
    for (var i = 0; i < width; i ++) {
        if (i == 0 or i == width-1 or j == 0 or j == height-1) or ( irandom(100) < fillPercentage )  {
            mapData[# i, j] = 1;
        } else {
            mapData[# i, j] = 0;
        }
    }
}
What does the "#" do? It's an alternative to writing ds_grid_read. They are known as accessors.

The final result should look like this.
upload_2017-11-15_1-0-24.png
Sweet! We can see the borders. Just as what we wanted.

Now we are in step 2! Killing off cells with little to no neighbours and creating new cells if there's enough!

Create a script and call it scrSmoothMap. We will quickly do step 3 right now. Inside scrGenerate, add this line:
Code:
repeat(smoothness) {
    scrSmoothMap();
}
This will call the
scrSmoothMap script "smoothness" (5) times. smoothness is equal to 5, as it's initialized in our object's create event.

Ok, let's jump back to
scrSmoothMap.
Let's create a nested for loop again to be able to iterate through the whole ds_grid.
Code:
for (var j = 0; j < height; j++) {
    for (var i = 0; i < width; i++) {

    }
}
Inside that loop, we will need to get the number of neighbouring cells for every cell we land on. Let's create a script for that. Let's call it
scrGetSurroundingWallCount. For our approach, we will specify x and y coordinates for it to check for neighbouring cells. It will return the number of neighbouring cells. The image below will show us how we will check for the 3x3 area.


[Image Source]

The x and y being the specified x and y coordinates being passed through the script.

Before we start anything, we should initialize our counter variable. So at the top of scrGetSurroundingWallCount, add this.
Code:
var wallCount = 0;
We then should grab our passed variables.
Code:
var _x = argument0, _y = argument1;
We will use a nested for loop to iterate through a 3x3 grid.
It should look like this:
Code:
for (var neighbourY = _y - 1; neighbourY <= _y + 1; neighbourY++) {
    for (var neighbourX = _x - 1; neighbourX <= _x + 1; neighbourX++) {

    }
}
The problem of using this loop is that we will likely go past the grid's boundaries. We need to run a check before reading our grid to prevent out of bound errors.

Inside the loop, put this:
Code:
//If the reading coordinates is inside the grid, then run this code.
if (neighbourX >= 0 and neighbourX < width and neighbourY >= 0 and neighbourY < height) {

}
Now we can't get any out of bounds errors. Since if we going to read outside the boundary, it's safe to say that it's a neighbour. We can add an else to the if check to automatically mark it as a neighbour.
Code:
if (neighbourX >= 0 and neighbourX < width and neighbourY >= 0 and neighbourY < height) { //Still in mapData bounds
            //Add to wall count if it's a wall
        } else {
            wallCount++;
}
Before we start to count the cell, we should make sure it doesn't count itself. Making sure that both our x and y coordinates don't match with the passed values should do the trick. Put this in the if check we just made previously.
Code:
if (neighbourX != _x or neighbourY != _y) {
    //Add to wall count if it's a wall
}
Now inside that if check, add this:
Code:
wallCount += mapData [# neighbourX, neighbourY];
When mapData equals to 1 (wall) at that position, add one to wallCount. This is easier than having to run an if check.

Finally, at the end of the script, we will need to return our value.
Code:
return wallCount;
The final code should look like this
Code:
var wallCount = 0;
var _x = argument0, _y = argument1;
for (var neighbourY = _y - 1; neighbourY <= _y + 1; neighbourY++) {
    for (var neighbourX = _x - 1; neighbourX <= _x + 1; neighbourX++) {
        if (neighbourX >= 0 and neighbourX < width and neighbourY >= 0 and neighbourY < height) { //Still in mapData bounds
            if (neighbourX != _x or neighbourY != _y) {
                wallCount += mapData [# neighbourX, neighbourY];
            }
        } else {
            wallCount++;
        }
    }
}
return wallCount;
Now, let's jump back to scrSmoothMap. We need to think back a moment. As we are editing the data, we need to make sure we don't edit the original grid as we go along. Otherwise, that would produce innaccurate results. Create a new ds_grid called mapData2 and make it the same size as mapData. Don't forget to destroy it after when we are done with it.

Inside the nested loop we made previously, we should add this:
Code:
neighbourWallTiles = scrGetSurroundingWallCount (i, j);
if (neighbourWallTiles > 4) {
    mapData2 [#i, j] = 1;
} else if (neighbourWallTiles < 4) {
    mapData2 [#i, j] = 0;
} else {
    mapData2 [#i, j] = mapData [#i, j];
}
scrGetSurroundingWallCount(i , j) returns the number of neighbouring walls. If it hits a certain number, we will make this cell a wall. Otherwise, if the cell is less, make this cell empty. If neither is the case, then leave the cell as is.

After the loop, we now can copy the data over to the original grid. This is done through ds_grid_copy.

The final code should look like this.
Code:
mapData2 = ds_grid_create(width, height);

for (var j = 0; j < height; j++) {
    for (var i = 0; i < width; i++) {
        neighbourWallTiles = scrGetSurroundingWallCount (i, j);
        if (neighbourWallTiles > 4) {
            mapData2 [#i, j] = 1;
        } else if (neighbourWallTiles < 4) {
            mapData2 [#i, j] = 0;
        } else {
            mapData2 [#i, j] = mapData [#i, j];
        }
    }
}
//Now copy data over to the original map
ds_grid_copy(mapData, mapData2);

ds_grid_destroy(mapData2);
That's it for step 2!
Now let's move to step 4 (since we did step 3 earlier) for drawing.
Create a new script. call it
scrApply. Make sure to call the script after scrGenerate() in your object's create event.
Inside
scrApply, we will iterate through the grid once again.
Code:
for(var j=0; j<height; j++) {
    for(var i=0; i<width; i++) {
        if (mapData[# i, j]) {
            //Is a wall
            var tile = tile_add(bckTile,0,0,1,1,i*cellSize,j*cellSize,0);
            tile_set_scale(tile, cellSize, cellSize);
        } else {
            //Empty
            var tile = tile_add(bckTile,2,0,1,1,i*cellSize,j*cellSize,0);
            tile_set_scale(tile, cellSize, cellSize);
        }
    }
}

And that's it! Voila!

Play around with the variable cellSize, smoothness, fillPercentage and room sizes.

To make it regenerate a new cave, simply just call a room_goto(room).
Note: Make sure to delete the data structure mapData in the room end event!.

room_restart causes a memory leak (iirc).


Some notes that you could do to improve this code (and possibly readability).
  • For checking with boundaries, you can use point_in_rectangle instead of having all of these comparisons. I avoided this function to prevent people being confused from using the function in a grid environment, rather than from the room. I also avoided it to give you more details about checking boundaries.
  • This does not check for disconnected parts of the cave. For that, you will need to use a flood fill algorithm. If this tutorial is popular enough, I might make a second part involving the use of the flood fill algorithm.
  • Try and see if you can figure out how to remove single pixels (without increasing smoothness).
  • You can use 2d arrays instead of ds_grids, which are faster.
  • For a faster approach, see this.
 
Last edited:
W

warmhotself

Guest
Wow this is a really helpful tutorial that appeared just exactly when I needed it! Thank you so much!
 
M

Moises Abraham

Guest
I really like your tutorial mate, it would be nice if you expanded it (if you feel like it) to have waterfalls and pools, and also a way to detect different areas so we could make transition tiles for different environment aesthetics and to discover good locations for placing goodies and minions :D
 

Bingdom

Googledom
does it output the same thing across android YYC and windows ?
I'm not entirely sure how the seed system works across different platforms.

Your best bet would be to create your own random scripts (or there is one online somewhere).
 
M

MagnumVulcanos

Guest
This can be used to generate asteroids/rocks/mountains as well.

Just change the following:
  • When first generating noise, do not generate anything on row 0 , line 0, last row and last line, meaning the initial nested for loop begins at 1 and ends at *end*-1.
  • Smoothness 4.
  • Fill 70.
  • Outside the grid aren't counted as walls.
Thanks for this ncie tutorial!.
 
Just a quick way to make it faster.

A 400*400 grid with 5 iterations
old: 6.60 seconds
mine: 0.70 seconds

without the part of filling the grid

Code:
//seperate rules for side, doesnt realy matter, with that variant they will allways be walls, like in the original, but could get other variable checks or constraints
    for (var yy = 0; yy < height; yy++) {
       var neighbourWallTiles = ds_grid_get_disk_sum(mapData,0,yy,1);
       if (neighbourWallTiles >= 1){
               mapData2 [# 0, yy] = 1;
       }
       var neighbourWallTiles = ds_grid_get_disk_sum(mapData,width-1,yy,1);
       if (neighbourWallTiles >= 1){
               mapData2 [# width-1, yy] = 1;
       }
   }
  
   for (var xx = 0; xx < width; xx++) {
       var neighbourWallTiles = ds_grid_get_disk_sum(mapData,xx,0,1);
       if (neighbourWallTiles >= 1){
               mapData2 [# xx, 0] = 1;
       }
       var neighbourWallTiles = ds_grid_get_disk_sum(mapData,xx,height-1,1);
       if (neighbourWallTiles >= 1){
               mapData2 [# xx, height-1] = 1;
       }
   }


// using the builtin functions
    for (var yy = 1; yy < height-1; yy++){
       for (var xx = 1; xx < width-1; xx++){
           var neighbourWallTiles = ds_grid_get_sum(mapData,xx-1,yy-1,xx+1,yy+1);
           if (mapData [# xx, yy] = 0){
               if (neighbourWallTiles > 4)
               {
                   mapData2 [# xx, yy] = 1;
               }else if (neighbourWallTiles < 4){
                   mapData2 [# xx, yy] = 0;
               }else{
                   mapData2 [# xx, yy] = mapData [# xx, yy];
               }
           }else if (mapData [# xx, yy] = 1){
               if(neighbourWallTiles > 5){
                   mapData2 [# xx, yy] = 1;
               }else if(neighbourWallTiles < 5){
                   mapData2 [# xx, yy] = 0;
               }else{
                   mapData2 [# xx, yy] = mapData [# xx, yy];
               }
           }
       }
   }
 

Bingdom

Googledom
Thank you for the post. I'll mention it in the notes. :)

Maybe I'll find the time and repair the intentional bitter practices on my original post.
 
Last edited:
Top