Search Unity

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:

 

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.

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:

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:

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.

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

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:

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:

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.

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:

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.

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!

3 评论

订阅评论

留下评论

您可以使用这些HTML标签和属性: <a href=""> <b> <code> <pre>

  1. I will say that calling that method Cellular Automata is a bit misleading, because what you actually are doing is just generating noise.

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

  2. 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 :)