The following article is a reproduction. The original article, and over 150 more, can be found at RemptonGames.com
Minecraft, Spelunky, Civilization – What do all of these games have in common? They are all games that have a seemingly limitless amount of content, and you can play for hundreds of hours without it getting repetitive. Why? Because all of these games make use of procedural generation – using computer algorithms to produce content that is different every time, rather than designing everything by hand. Procedural generation is a powerful tool that, if used correctly, can take a game from good to great, and keep players coming back over and over again.
In today’s video we will begin exploring the topic of procedural generation by looking at 3D terrain generation – how it works, and why It is used. To do so, we will actually be coding a procedurally generated 3D landscape completely from scratch.
To make our 3D landscape I will be using a program called Processing, which is a programming environment that makes it really easy to draw things to the screen. While I will be explaining what I’m doing as I go, this is not a “how to program in processing” video, and my goal here is more to demonstrate some of the tools and techniques behind 3D terrain generation, rather than to be a step-by-step guide. Without further ado, let’s get started.
Let’s start by getting our project set up. Processing projects are called “sketches”, and every sketch needs two function. The first function is the setup function, which is called once when we first start our program. The main thing we need to do in the setup function is set our size – this determines how big our screen will be. We can also choose our renderer – because this will be a 3D project I will use P3D.
The second function is the draw function, which is called over and over. Let’s start by just picking a random background color and I’ll show you what our window looks like.
So right now all we have is a single color – not very exciting. The first step to getting something more interesting is to make some noise – literally. Noise is a special form of randomness with some very useful properties. To demonstrate, lets do a little side-by-side. First, I’m going to fill the screen with randomness, then I’ll fill the screen with noise, and we can see why noise is so nice.
My screen, like most screens, including the one you are watching this on, is made of pixels. For this demonstration I am going to go through each of those pixels one by one and assign it a random color between black and white. When I say random, I mean that there is an equal chance of any pixel having any value from black to white to all the shades of grey in-between. I just need to loop through the horizontal pixels, loop through the vertical pixels, and voila! A salt and pepper storm. I’m just going to go ahead and set “noLoop” so we can look at this. This is what randomness looks like – all of the pixels are completely disconnected from everything else around it. Randomness is generally NOT what you want for procedural generation.
Lets see what happens if I replace the “random” function with a “noise” function instead. Noise only produces a value between 0 and 1, while brightness goes from 0 to 255, so let’s just multiply our noise by 255 so we get a full range of brightness. Let’s take a look. We get this much more structured, repeating pattern than we did before. However, this still isn’t what we want – let’s “zoom in” a bit. To do this I’m gonna create a new variable, called “increment”, that determines how quickly we move through the noise. I’ll set that to 0.05, and use it to multiply my X and Y and lets see what we get. Much better! Alright, now that we have something to look at let’s talk about the noise function.
First, let’s talk about what noise is. Noise is basically controlled randomness. As you can see, the colors vary from black to white with all of the different shades of grey in-between, but it isn’t as harsh as when it was just purely random. Instead, it transitions smoothly through the different shades. The specific type of noise that Processing uses for its noise function is called Perlin Noise, and if you are interested in learning the specifics of how it works I would recommend Coding Train, which has a series that goes much more in-depth into how it works. However, for the purposes of this video all we really need to know is that it produces a kind of smooth randomness that is much more useful for procedurally generated terrain, textures, and so forth.
Another nice thing about noise is that it is repeatable. Noise is all based on a special number called a seed – different seeds will give you different noise patterns, but using the same seed will get you the same result every time. Lets set our seed to something nice – 10052014.
There are lots of different kinds of noise algorithms that can be used depending on what kind of look you are going for, but for this video we are going to be sticking with Perlin noise. That being said, one of the other major benefits of noise algorithms is that they are easily customizable. We already showed what happens when you zoom on Perlin noise, but there are plenty of other things we can do that change how it looks. For example, we can change the level of detail of our noise using the noiseDetail() function. This function takes two numbers – the first determines how many layers of Perlin noise we want to generate, and the second determines how the layers get added together. The more layers of noise we add, the “grittier” the result. The default is 4 layers – lets see what happens when we drop it down to just one.
The result looks much smoother – it almost looks like it’s been blurred. Now lets try cranking it up to 8 and see what happens. Now it’s got a lot more fine, gritty details. For our purposes lets use 3 layers. There are lots of other ways we can play with the results, but we will explore those more after we get our terrain working. After all, all we really have now is some fuzzy shapes in 2D – a far cry from 3D terrain. True, but what if instead of using the noise to get colors we used it to get a height value? A 2D image used to produce a 3D surface is called a height-map, and height-maps have been used to generate 3D terrain for decades now.
So, lets quickly modify our project to turn our surface into a heightmap. The first thing we need to do is create a flat mesh – All virtual 3D objects are made up of meshes, which are basically the points, edges and triangles that make up the object. All meshes are basically made up of triangles because triangles are the simplest shape, so for our mesh we first need to create a bunch of triangles. To do this I will be creating what Processing calls a “triangle strip”, and I will basically just be creating a bunch of rows and columns of triangles.
For this I will create a scale factor, which basically determines how big our triangles will be. Then, I will use this scale factor to determine how many rows and columns we need – we want to fill the whole screen, so I will just take the width and height divided by the scale, and that will give us the number of rows and columns. Now instead of looping through the pixels on the screen I simply need to loop through the rows and columns, and create my triangle strip as I go. Let’s take a look at that. Fantastic – we now have a very regular grid of points that we can use to make our terrain. Right now each of our points has the same height value of 1 – the next step is to change the z-value based on our noise function.
For each point we basically just need to get the noise value of our X and Y coordinates, multiplied by the increment variable that we created earlier. Remember that noise only gives us a value between 0 and 1 – that wouldn’t change our height much at all, so lets multiply that by a big value – 200. Now we use those variables for our height, and get something much more interesting. This is actually already our 3D terrain, but it’s kinda hard to tell because we are basically looking down on it from above. It might be easier to see what’s going on it we tilted it, and looked at it from the side instead.
To do that, all we have to do is add a few quick lines of code – we first move the image down a bit, then rotate it by 60 degrees. Congratulations – we have a 3D landscape! And it only took use a few minutes and a couple lines of code. However, we aren’t done quite yet. Now that we have our landscape ready I’m going to cheat a bit and add some code from a project I prepared earlier. This will help demonstrate a problem with our landscape.
Alright, I’m back and I’ve basically done 2 things to my project. The first is add some color – I changed the background color to look like a sky, and changed the color of each point based on it’s height. That part was pretty simple – all I had to do was check how high the point was, and assign it a color.
The second thing that I did was add some code that lets me “fly” around in our virtual space. This code basically checks if I am pressing an arrow key, and updates an offset in the x or y direction which moves us through the space. Let’s look around a bit, shall we?
Not half bad! However, this does highlight a problem with simple noise-based terrain generation. Sure, this is a decently convincing mountain terrain, but because everything is using the same noise function everything in the world is going to look like this. In addition, as we saw when we zoomed out the noise function will eventually repeat itself, which means that our world will just be an endlessly repeating collection of same-y mountains. I think we can do better.
One way to add more variety to our virtual landscapes is to have multiple different “noises” that control different aspects of the world. One noise value may control the surface displacement, while another controls things like temperature. Lets go ahead and add a second noise value that controls what type of terrain we will be creating. Specifically, if this second noise has a high value we will have jagged, mountainous terrain, but if the value is low we will have a flatter landscape with more gentle hills.
To do this we are going to add a third Z dimension to our noise. Our noise so far has been 2 dimensional, but noise can actually be 3, 4, or any number of dimensions. Our old noise will use a Z value of 0, and our need noise will use a Z value of 10. Also, while the increment we are using is fine for individual mountains, we want our different terrains to be bigger, so I’m going to create a second, smaller increment. I’ll also turn off the current color so we can see the terrain better.
Now as we move around you can see that as the land gets darker it also gets flatter, and as it get brighter it gets more hilly. This still isn’t terribly impressive – after all, its just different heights of hills, but you could use this technique to determine things like vegetation, rainfall, all sorts of different things. Also, because we now have two different kinds of noise layered on eachother it will take a much longer time before the pattern repeats. By adding more and more layers of noise you can create even more diverse landscapes, and have an endless. Variety.
There is one last trick I want to show you, and then I want to discuss some of the weaknesses of this approach. Up to this point we have basically been using the noise values as-is, but by messing with the values themselves you can actually get a lot more interesting results. The one simple example I want to show is using the absolute value of the noise instead of the noise itself. To do so we need to double the range of our noise, so that it covers -1 to 1 instead of just 0 to 1. I’m simply going to multiply our noise by 2, and then subtract 1 to get this range. Then we just have to take the absolute value of our new number. I’m also going to add the color back.
Let’s just quickly remind ourselves what our world looked like before. Now lets see what we can do with a quick bit of math. Now we get these sharp peaks and valleys, with rivers and lakes nestled in-between. This is caused by the transition between positive and negative numbers – because we are using the absolute value function, this creates a “crease” whenever a value crosses 0, which creates the sharp valleys that we see here. And this is only one of the many different effects you can get by messing with your noise function. By changing the level of detail of the noise, zooming in and out, layer different noises upon each other, and apply different mathematical functions to the noise, there is an infinite number of different effects you can create.
This technique does have some limitations, however. Because you are simply adjusting the height of your terrain you can’t get things like overhangs, caves, things like that. However, there are ways around this. We have mostly been dealing with 2 dimensional noise, but it is possible to create a landscape using 3 Dimensional noise as well, which does allow for these kinds of details. However, writing code to render 3D noise will take a lot longer than this video.
The second way to get around this is to generate your heightmap, turn it into a mesh, and then have a separate “pass” to add your 3 dimensional details. This second pass can be used to remove parts of your mesh for caves and overhangs, or even add things to it such as natural arches.
Until Next Time!
There is so much more to talk about in this topic, but I think that’ll do it for this video. If you liked this video make sure to leave it a like, and subscribe so you don’t miss future terrain generation videos. If you found this video interesting you should check out some of the other videos on my channel – I cover a wide range of topics in the realms of game design and development. You can also check out the RemptonGames blog, where I have over 150 articles at the link in the description below. And join me next week where we will be applying what we learned today to explore how Minecraft generates it’s terrain! Until then, thank you so much for watching and I’ll see you all next time.