GML Cellular Automata (Cave generation)

Discussion in 'Tutorials' started by Bingdom, Nov 14, 2017.

  1. Bingdom

    Bingdom Googledom

    Joined:
    Jul 1, 2016
    Posts:
    1,673
    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.

    [​IMG]
    [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: Nov 19, 2018
  2. warmhotself

    warmhotself Member

    Joined:
    Sep 3, 2016
    Posts:
    9
    Wow this is a really helpful tutorial that appeared just exactly when I needed it! Thank you so much!
     
  3. Tyche

    Tyche Member

    Joined:
    Nov 23, 2017
    Posts:
    6
    Coo, Thanks!
     
  4. LCArt

    LCArt Member

    Joined:
    Dec 11, 2017
    Posts:
    3
    wow nice tut, saved :3
     
  5. Moises Abraham

    Moises Abraham Member

    Joined:
    Dec 27, 2017
    Posts:
    12
    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
     
  6. Qual

    Qual Member

    Joined:
    Aug 16, 2016
    Posts:
    29
    does it output the same thing across android YYC and windows ?
     
  7. Bingdom

    Bingdom Googledom

    Joined:
    Jul 1, 2016
    Posts:
    1,673
    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).
     
  8. MagnumVulcanos

    MagnumVulcanos Member

    Joined:
    Dec 20, 2016
    Posts:
    46
    This can be used to generate asteroids/rocks/mountains as well.
    [​IMG]
    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!.
     
  9. IgniFerroque

    IgniFerroque Member

    Joined:
    Aug 28, 2017
    Posts:
    21
    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];
                   }
               }
           }
       }
     
  10. Bingdom

    Bingdom Googledom

    Joined:
    Jul 1, 2016
    Posts:
    1,673
    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: Nov 19, 2018
  11. Aajowa

    Aajowa Member

    Joined:
    Sep 9, 2018
    Posts:
    6
    Thanks for this Blingdom! So smooth
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice