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#.

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:

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.

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.

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:

1. Finding our start position
2. Calculating the number of floor tiles we need to remove
3. Removing the tile at the start position
4. Adding one to our floor count

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

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;
}

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.

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:

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;
    }

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.

    //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:

1. 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.
2. Finally, we tunnel out the new section we have created.

The end results of this implementation look like this:

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:

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:

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:

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.

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.

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:

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.

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.

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!

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!