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.
Required knowledge
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:
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.
Lastly, these variables are important for our generator scripts. These also belong in our object's create event.
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.
Now, inside the nested for loop, we need to determine if it should be a wall or not.
Basically what happens; if irandom is less than fillPercentage, make the cell a 1 (wall). otherwise, make it 0 (empty).
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.
The final code should look like this:
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.
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:
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.
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.
We then should grab our passed variables.
We will use a nested for loop to iterate through a 3x3 grid.
It should look like this:
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:
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.
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.
Now inside that if check, add this:
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.
The final code should look like this
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:
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.
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.
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).
Target Platform: ALL
Download: N/A
Links: N/A
Summary
Cellular Automata is a discrete model which can be used for procedural cave generation.
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:
- Generate random noise inside our grid, based on fillPercentage.
- 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.
- Repeat step 2 several times.
- Create tiles based on the data from our ds_grid (So we can see it)
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);
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;
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 ++) {
}
}
Code:
if ( irandom(100) < fillPercentage ) {
mapData[# i, j] = 1;
} else {
mapData[# i, j] = 0;
}
}
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)
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;
}
}
}
The final result should look like this.
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();
}
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++) {
}
}
[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;
Code:
var _x = argument0, _y = argument1;
It should look like this:
Code:
for (var neighbourY = _y - 1; neighbourY <= _y + 1; neighbourY++) {
for (var neighbourX = _x - 1; neighbourX <= _x + 1; neighbourX++) {
}
}
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) {
}
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++;
}
Code:
if (neighbourX != _x or neighbourY != _y) {
//Add to wall count if it's a wall
}
Code:
wallCount += mapData [# neighbourX, neighbourY];
Finally, at the end of the script, we will need to return our value.
Code:
return wallCount;
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;
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];
}
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);
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: