In part 1 we looked at some of the ways we can create top layers procedurally using various methods, like Perlin Noise and Random Walk. In this post, we are going to look at some of the ways to create Caves with procedural generation, which should give you an idea of the possible variations available.

Everything we are going to talk about in this blog post is available within this project. Feel free to download the assets and try out the procedural algorithms.

This blog post conforms to the same rules as Part I. To remind you, these rules are:

- The way we distinguish between being a tile or not is by using binary. 1 being on and 0 being off.

- We will store all of our maps into a 2D integer array, which is returned back to the user at the end of each function (except for when we render).

- I will use the array function GetUpperBound() to get the height and width of the map. This means that we have fewer variables going into each function, allowing for cleaner code.

- I often use Mathf.FloorToInt(), this is because the tilemap coordinate system starts at the bottom left and using Mathf.FloorToInt() allows for us to round the numbers to an integer.
- All of the code provided in this blog post is in C#.

# Perlin noise

In the previous blog post, we looked at some ways of using Perlin noise to create top layers. Luckily enough, we can also use Perlin Noise to create a cave. We do this by getting a new Perlin noise value, which takes in the parameters of our current position multiplied by a modifier. The modifier is a value between 0 and 1. The larger the modifier value, the messier the Perlin generation. We then proceed to round this value to a whole number of either 0 or 1, which we store in the map array. Have a look at the implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public static int[,] PerlinNoiseCave(int[,] map, float modifier, bool edgesAreWalls) { int newPoint; for (int x = 0; x < map.GetUpperBound(0); x++) { for (int y = 0; y < map.GetUpperBound(1); y++) { if (edgesAreWalls && (x == 0 || y == 0 || x == map.GetUpperBound(0) - 1 || y == map.GetUpperBound(1) - 1)) { map[x, y] = 1; //Keep the edges as walls } else { //Generate a new point using Perlin noise, then round it to a value of either 0 or 1 newPoint = Mathf.RoundToInt(Mathf.PerlinNoise(x * modifier, y * modifier)); map[x, y] = newPoint; } } } return map; } |

The reason we use a modifier instead of a seed, is because the results of the Perlin generation look better when we are multiplying the values by a number between 0 and 0.5. The lower the value, the more blocky the result. Have a look at some of the results. This gif starts with a modifier value of 0.01 and works it way to 0.25 in increments.

From this gif, you can see that the Perlin generation is actually just enlarging the pattern with each tick.

# Random Walk

In the previous blog post, we saw that we can use a coin flip to determine whether the platform will go up or down. In this post, we are going to use the same idea, but with an additional two options for left and right. This variation of the Random Walk algorithm allows us to create caves. We do this by getting a random direction, then we move our position and remove the tile. We continue this process until we have reached the required amount of floor we need to destroy. At the moment we are only using 4 directions: up, down, left, right.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public static int[,] RandomWalkCave(int[,] map, float seed, int requiredFloorPercent) { //Seed our random System.Random rand = new System.Random(seed.GetHashCode()); //Define our start x position int floorX = rand.Next(1, map.GetUpperBound(0) - 1); //Define our start y position int floorY = rand.Next(1, map.GetUpperBound(1) - 1); //Determine our required floorAmount int reqFloorAmount = ((map.GetUpperBound(1) * map.GetUpperBound(0)) * requiredFloorPercent) / 100; //Used for our while loop, when this reaches our reqFloorAmount we will stop tunneling int floorCount = 0; //Set our start position to not be a tile (0 = no tile, 1 = tile) map[floorX, floorY] = 0; //Increase our floor count floorCount++; |

We start out the function by:

- Finding our start position
- Calculating the number of floor tiles we need to remove
- Removing the tile at the start position
- Adding one to our floor count

Next, we move on to the while loop. This will create the cave for us:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
while (floorCount < reqFloorAmount) { //Determine our next direction int randDir = rand.Next(4); switch (randDir) { //Up case 0: //Ensure that the edges are still tiles if ((floorY + 1) < map.GetUpperBound(1) - 1) { //Move the y up one floorY++; //Check if that piece is currently still a tile if (map[floorX, floorY] == 1) { //Change it to not a tile map[floorX, floorY] = 0; //Increase floor count floorCount++; } } break; //Down case 1: //Ensure that the edges are still tiles if ((floorY - 1) > 1) { //Move the y down one floorY--; //Check if that piece is currently still a tile if (map[floorX, floorY] == 1) { //Change it to not a tile map[floorX, floorY] = 0; //Increase the floor count floorCount++; } } break; //Right case 2: //Ensure that the edges are still tiles if ((floorX + 1) < map.GetUpperBound(0) - 1) { //Move the x to the right floorX++; //Check if that piece is currently still a tile if (map[floorX, floorY] == 1) { //Change it to not a tile map[floorX, floorY] = 0; //Increase the floor count floorCount++; } } break; //Left case 3: //Ensure that the edges are still tiles if ((floorX - 1) > 1) { //Move the x to the left floorX--; //Check if that piece is currently still a tile if (map[floorX, floorY] == 1) { //Change it to not a tile map[floorX, floorY] = 0; //Increase the floor count floorCount++; } } break; } } //Return the updated map return map; } |

### So, what are we doing here?

Well, first of all, we are deciding which direction we should move using a random number. Next, we check the new direction with a switch case statement. Within this statement, we check to see if the position is a wall. If it isn’t, we then remove the tile piece from the array. We continue doing this until we reach the required floor amount. The end result is shown below:

I also have created a custom version of this function, which includes diagonal directions as well. The code for this function is a bit long, so if you would like to look at it, please check out the link to the project at the beginning of this blog post.

# Directional tunnel

A directional tunnel starts at one end of the map and then tunnels to the opposite end. We can control the curve and roughness of the tunnel by inputting them into the function. We can also determine the minimum and maximum length of the tunnel parts. Let’s take a look at the implementation below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public static int[,] DirectionalTunnel(int[,] map, int minPathWidth, int maxPathWidth, int maxPathChange, int roughness, int curvyness) { //This value goes from its minus counterpart to its positive value, in this case with a width value of 1, the width of the tunnel is 3 int tunnelWidth = 1; //Set the start X position to the center of the tunnel int x = map.GetUpperBound(0) / 2; //Set up our random with the seed System.Random rand = new System.Random(Time.time.GetHashCode()); //Create the first part of the tunnel for (int i = -tunnelWidth; i <= tunnelWidth; i++) { map[x + i, 0] = 0; } |

### So what is happening?

We first set up a width value. This width value will go from its minus counterpart to its positive value. This will end up giving us the actual size we want. In this case, we are using a value of 1. This, in turn, will give us a total width of 3, because we will use the values -1, 0, 1.

The next thing we do is set out starting x-position, this is done by getting the middle of the width of the map. Now we have those first to values set up we can tunnel the first part of the map.

Now let’s move on to creating the rest of the map.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
//Cycle through the array for (int y = 1; y < map.GetUpperBound(1); y++) { //Check if we can change the roughness if (rand.Next(0, 100) > roughness) { //Get the amount we will change for the width int widthChange = Random.Range(-maxPathWidth, maxPathWidth); //Add it to our tunnel width value tunnelWidth += widthChange; //Check to see we arent making the path too small if (tunnelWidth < minPathWidth) { tunnelWidth = minPathWidth; } //Check that the path width isnt over our maximum if (tunnelWidth > maxPathWidth) { tunnelWidth = maxPathWidth; } } //Check if we can change the curve if (rand.Next(0, 100) > curvyness) { //Get the amount we will change for the x position int xChange = Random.Range(-maxPathChange, maxPathChange); //Add it to our x value x += xChange; //Check we arent too close to the left side of the map if (x < maxPathWidth) { x = maxPathWidth; } //Check we arent too close to the right side of the map if (x > (map.GetUpperBound(0) - maxPathWidth)) { x = map.GetUpperBound(0) - maxPathWidth; } } //Work through the width of the tunnel for (int i = -tunnelWidth; i <= tunnelWidth; i++) { map[x + i, y] = 0; } } return map; } |

Generate a random number to check against our roughness value, if it is above the value, we can change the width of the path. We also check to see if we are making the width too small. With this next bit of code, we are working our way through the map, tunneling as we go. With each step, we do the following:

- Generate a new random number to check against our curve value. Like the previous check, if it is above the value, we can change the center point of the path. We also check to make sure we aren’t going off the edges of the map.
- Finally, we tunnel out the new section we have created.

The end results of this implementation look like this:

# Cellular Automata

Cellular Automata uses a neighbourhood of cells to determine whether the current cell is on (1) or off (0). The basis for these neighbourhoods uses a randomly generated grid of cells. In our case, we are going to generate this initial grid using the Random.Next function in C#.

Because we have a couple of different implementations of Cellular Automata, I’ve made a separate function for generating this base grid. The function looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public static int[,] GenerateCellularAutomata(int width, int height, float seed, int fillPercent, bool edgesAreWalls) { //Seed our random number generator System.Random rand = new System.Random(seed.GetHashCode()); //Initialise the map int[,] map = new int[width, height]; for (int x = 0; x < map.GetUpperBound(0); x++) { for (int y = 0; y < map.GetUpperBound(1); y++) { //If we have the edges set to be walls, ensure the cell is set to on (1) if (edgesAreWalls && (x == 0 || x == map.GetUpperBound(0) - 1 || y == 0 || y == map.GetUpperBound(1) - 1)) { map[x, y] = 1; } else { //Randomly generate the grid map[x, y] = (rand.Next(0, 100) < fillPercent) ? 1 : 0; } } } return map; } |

In this function, we can also determine whether we want walls on our grid. Other than that, it’s relatively simple. We check a random number against our fill percentage to determine whether the current cell is on or off. Have a look at the result:

## Moore Neighbourhood

The Moore Neighbourhood is used to help smooth out the initial Cellular Automata generation. The Moore neighbourhood looks like this:

The rules for the neighbourhood are as follows:

- Check every direction for a neighbour.
- If a neighbour is an active tile, add one to the surround tiles.
- If a neighbour is not an active tile, do nothing.
- If the cell has more than 4 surrounding tiles, make the cell an active tile.
- If the cell has exactly 4 surround tiles, leave the tile alone.
- Repeat until we have tried every tile in the map.

The function for checking the Moore Neighbourhood is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
static int GetMooreSurroundingTiles(int[,] map, int x, int y, bool edgesAreWalls) { /* Moore Neighbourhood looks like this ('T' is our tile, 'N' is our neighbours) * * N N N * N T N * N N N * */ int tileCount = 0; for(int neighbourX = x - 1; neighbourX <= x + 1; neighbourX++) { for(int neighbourY = y - 1; neighbourY <= y + 1; neighbourY++) { if (neighbourX >= 0 && neighbourX < map.GetUpperBound(0) && neighbourY >= 0 && neighbourY < map.GetUpperBound(1)) { //We don't want to count the tile we are checking the surroundings of if(neighbourX != x || neighbourY != y) { tileCount += map[neighbourX, neighbourY]; } } } } return tileCount; } |

After we have checked our tile, we then proceed to use the information in our smoothing function. Again, like the initial Cellular Automata generation, we can set whether the edges of the map are walls.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public static int[,] SmoothMooreCellularAutomata(int[,] map, bool edgesAreWalls, int smoothCount) { for (int i = 0; i < smoothCount; i++) { for (int x = 0; x < map.GetUpperBound(0); x++) { for (int y = 0; y < map.GetUpperBound(1); y++) { int surroundingTiles = GetMooreSurroundingTiles(map, x, y, edgesAreWalls); if (edgesAreWalls && (x == 0 || x == (map.GetUpperBound(0) - 1) || y == 0 || y == (map.GetUpperBound(1) - 1))) { //Set the edge to be a wall if we have edgesAreWalls to be true map[x, y] = 1; } //The default moore rule requires more than 4 neighbours else if (surroundingTiles > 4) { map[x, y] = 1; } else if (surroundingTiles < 4) { map[x, y] = 0; } } } } //Return the modified map return map; } |

A key thing to note in this function is the fact that we have a for loop to smooth through the map a certain number of times. This ends up giving us a nicer map as the result.

We could always go on to modify this algorithm by connecting rooms to each other if, for instance, there are only 2 blocks between them.

## von Neumann Neighbourhood

The von Neumann Neighbourhood is another popular implementation method for Cellular Automata. For this generation, we use a simpler neighbourhood than the one we used in the Moore Generation. The neighbourhood looks like this:

The rules for this neighbourhood are as follows:

- Check around the tile to the direct neighbours, not including the diagonals.
- If the cell is active, add one to our count.
- If the cell is inactive, do nothing.
- If we have more than 2 neighbours, make the current cell active.
- If we have less than 2 neighbours, make the current cell inactive.
- If we have exactly 2 neighbours, don’t modify the current cell.

The second result takes the same principles as the first but expands the neighbourhood area.

We check for the neighbours by using the following function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
static int GetVNSurroundingTiles(int[,] map, int x, int y, bool edgesAreWalls) { /* von Neumann Neighbourhood looks like this ('T' is our Tile, 'N' is our Neighbour) * * N * N T N * N * */ int tileCount = 0; //Keep the edges as walls if(edgesAreWalls && (x - 1 == 0 || x + 1 == map.GetUpperBound(0) || y - 1 == 0 || y + 1 == map.GetUpperBound(1))) { tileCount++; } //Ensure we aren't touching the left side of the map if(x - 1 > 0) { tileCount += map[x - 1, y]; } //Ensure we aren't touching the bottom of the map if(y - 1 > 0) { tileCount += map[x, y - 1]; } //Ensure we aren't touching the right side of the map if(x + 1 < map.GetUpperBound(0)) { tileCount += map[x + 1, y]; } //Ensure we aren't touching the top of the map if(y + 1 < map.GetUpperBound(1)) { tileCount += map[x, y + 1]; } return tileCount; } |

After we have our result of how many neighbours we have, we can then move onto smoothing the array. As before, we have a for loop to iterate through the smoothing for the required amount inputted.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public static int[,] SmoothVNCellularAutomata(int[,] map, bool edgesAreWalls, int smoothCount) { for (int i = 0; i < smoothCount; i++) { for (int x = 0; x < map.GetUpperBound(0); x++) { for (int y = 0; y < map.GetUpperBound(1); y++) { //Get the surrounding tiles int surroundingTiles = GetVNSurroundingTiles(map, x, y, edgesAreWalls); if (edgesAreWalls && (x == 0 || x == map.GetUpperBound(0) - 1 || y == 0 || y == map.GetUpperBound(1))) { //Keep our edges as walls map[x, y] = 1; } //von Neuemann Neighbourhood requires only 3 or more surrounding tiles to be changed to a tile else if (surroundingTiles > 2) { map[x, y] = 1; } else if (surroundingTiles < 2) { map[x, y] = 0; } } } } //Return the modified map return map; } |

The end result looks a lot more blocky than the Moore Neighbourhood, as can be seen below:

Again, as with the Moore Neighbourhood, we could proceed to have an additional script run on top of the generation to provide better connections between areas of the map.

# Conclusion

I hope I’ve inspired you to start using some form of procedural generation within your projects. If you haven’t already downloaded the project, you can get it from here. If you want to learn more about procedural generating maps, check out the Procedural Generation Wiki or Roguebasin.com as they both are great resources.

If you make something cool using procedural generation feel free to leave me a message on Twitter or leave a comment below!

## 2D Procedural Generation at Unite Berlin

Want to hear more about it and get a live demo? I’m also talking about Procedural Patterns to use with Tilemaps at Unite Berlin, in the expo hall mini-theater on June 20th. I’ll be around after the talk if you’d like to have a chat in person!

trond

6월 8, 2018 12:44 오후I will say that calling that method Cellular Automata is a bit misleading, because what you actually are doing is just generating noise.

Sampsa

6월 12, 2018 9:37 오후Yeah, that part is just bootstrapping the cellular automata – it’s not the actual algorithm at all. What follows are the actual rules for the automata.

However, the implementation is flawed, because cellular automata is supposed to read from one buffer, and write to another. Now it’s actually modifying the map while it’s reading it. So the end results would be different depending on which direction the rules are processed.

Otherwise it’s a great primer for PCG. Too bad it’s littered with errors and mistakes.

Isaac Surfraz

6월 7, 2018 6:26 오후YAY! My favourite blog post series has returned :)

More procgen articles please! Some to do with 3d stuff such as scattering and placement, heightmap generation, and computational geometry (such as fitting x boxes in a space etc) would be great eventually :)