The theme of Procedural Generation is extensive, so we’ll only touch the tip of the iceberg. We’ll focus only on terrain generation for 2D and 3D games.
What is Procedural Generation?
Procedural generation (or PG) is the ability to create “partially” random content by the computer.
This means that with little to no input, you can program infinite content for your players. PG can be used to create environments, monsters, drops… You name it. If you combine terrain generation with monster generation and loot generation, you’ll be able to create infinite unique worlds, which allows your game to have infinite replayability. And if well done, your players are able to enjoy your game for years to come, while experiencing endless challenges and experiences.
I know your mind must be exploding with ideas and exciting new games you want to make. However, please do remember, while powerful, PG is not for every game. There is nothing more powerful than a handcrafted experience for your players. PG is not for you, for example, when your focus is the narrative, or when you want your player to follow a certain story path. You may add some randomness with Random Generation, but that’s not the focus of this text. And, if you only have 1 or 2 levels, then don’t bother adding PG. It’s too OP.
Even though games like Minecraft have thousands of hours of replayability, truth is, you will at some point download mods. This happens because even though every world is different, there is a limit to the things you can do in the vanilla version.
Procedural Generation Rules
There is only 1 thing you must have in mind when using PG. And that is rules.
But, what rules? I thought this was a random generation!
Even though it is random, it can’t be chaotic (unless that’s what you want). So, when building (for example) a generated dungeon room, you will need rules (or procedures):
- A room cannot exist without an entrance/exit
- A room must have one or more of: loot, monsters or puzzle
Using a set of rules, we can now generate a room that a player would have 1 or more activities to complete, before moving on to the next room. Or maybe even grab some special requirement to unlock a hidden quest? Your call. You are the dungeon master. These rules should be defined early in the design stages in order to avoid changing the rules “mid-game”.
Just because it’s PG, doesn’t mean you don’t need to design it. Remember, the more you handcraft special pieces of the generation, the more your players will enjoy it.
How do I put it in my game?
This theory is all fun and stuff but I wanna put PG in my game!
As mentioned before, this text will only cover terrain generation. To add PG to your game, there are several things you should consider, because you can’t just generate meadows and hills. That’s boring. You need biomes, rivers, forests, deserts, stuff like that. And that is achieved with multiple PG layers (or passes, we’ll get there). So, before we can talk about PG, we must talk about noise and randomness.
Random number generation
The first thing you have to understand is: there is no true randomness for computers. Since computers only work with certainties, randomness is not an ability they have. A computer can only execute orders that someone programmed it to execute. They can, however, generate a number based on another number. This is called Pseudorandom generation. This is (pretty much) how they do it:
- First, get a really long constant number, example: 170141183460469231731687303715884105727
- Then, generate or give a seed to the number generator, for example 5
- We grab the seed 5 and use it on the 5th slot of the number, which is 4
- Then we multiply the number by 52 (hardcoded number made up by the programmer), we get 208
- We apply the modulus of 11 (again, hardcoded number, but made up by the programmer), we get 10.
- The final result would be 10 and that will be the input to the noise generation.
We now pass this seed that was just generated to the noise generator (usually the current system time is passed to the noise generator since it’s always different, but you can give it any value you want). Depending on the noise generator, the algorithm varies, but in this case, we’ll talk about Perlin.
How is it generated? Well, with traditional random number generation, we might get any value from 0 to 1 over time, so we could very well get 0.1 in time = 0 (or t = 0) and in the next step (time = 1) we could get 0.9.
Random generation example (numbers are time t)
But Perlin prevents that, since Perlin generation is relative to the previous step you took, so if you get a 0.1 at t = 0 you will never get a 0.9 at t = 1, you might get a 0.2 or a 0.4 but with Perlin, you are guaranteed that you’ll get much smoother values.
Example with Perlin generation
This was just for 1 row of values, but when we generate Perlin noise, we almost always deal with a matrix of values (or two-dimensional array, if that helps).
Empty matrix (10×10) to be filled with values
When a value is generated with Perlin, you know that it will be affected by the adjacent value that we just generated. This will also apply to a matrix: when we are generating the value in x = 4, y = 5, we care about all nearby values:
Green is the one being generated. Blue are the ones we will read to smooth out the value of green
This ensures that the values we generate are smoothed out and that we don’t have spikes when nearby a low value. Now, visualizing the low values as dark and the high values as light (so 0 is black and 1 is white), we get this:
If we visualize it in 3d, it would look something like this (remember 0=black/low altitude, 1=white/high altitude):
Luckily, almost all programming languages and frameworks already have a built-in noise function, so you don’t have to worry about implementing this 🙂
This is another type of random noise used for many things, but in this case, we will only talk about two: rivers, and cave systems. Can you imagine? After you generated your world, you will use this noise and pick the whitest parts (example above 0.7) and apply them to your map, and create rivers 🙂 The noise looks like this visually:
And in 3d, it would look really cool in cave systems:
At this moment you must be like this:
Don’t worry. We’ll get there 😀 Now begins the fun part!
While this sounds extremely boring, the good news is, you don’t have to generate it, you just have to use it. Take a look at these examples:
Terraria is a 2d game, and as such, we will use the 2d noise like you just saw above. The first step is to define an area: let’s go with 128px by 128px (easier to visualize) and 1 pixel is equal to your in-game tile:
Second, we define a baseline, where above this line, we’ll generate the overworld, and below, we’ll have the cave systems:
For the next step, we grab 1 row of the 2d noise from earlier. Here it is for easier visualization:
Make sure you understand that it is only 1 row, expanded vertically so you can see it better. We only care about 1 row of values from 0 to 1.
Now, we have to picture the white part as 1, and the black as 0. This allows us to generate, from left to right, the height of the map. Let’s define the maximum height that we will use, for example, to 30 tiles. Multiply it by the first noise value and add the baseline value to get the real position of the tile.
For example, if:
- maximum = 30 tiles
- noise value = 0.2
- baseline = 30 tiles
The real position of the tile is (maximum x noise value) + baseline = (30 x 0.2) + 30 = 36.
So we would put the first tile (grass) on the Y position of 6 tiles above baseline, which is 36 tiles above Y = 0.
After this, all of the tiles below this one will be filled with dirt, unless the distance to the first tile is greater than 10, in which case, we put stone.
Now, for each tile, from left to right, we repeat this process, ending up with something that looks like this (baseline is now blue for visualization):
Now, you noticed that we used some rules in this generation as we talked before. Can you identify the rules?
- The grass tile to add is identified by the formula above.
- Dirt will occupy 10 tiles below the grass tile
- For distance from the grass tile greater than 10 tiles, we put stone tiles.
These rules were used to create this measly 2d map, and it’s very ugly, but you get the point. And with this, you completed the first pass of the generation. The next step could be to generate, for example, trees and grass. Do you have an idea on how we could do it? How about this: for each tile of grass that we just spawned, check if it can support grass and a tree. (Notice the rules again).
2D Top-down games
For 2d top-down games, all we need is to simply generate noise, build the map based on altitude, apply different tiles to different values and voila, it’s done. As for the features of the overworld, we need as many passes you can give it. A properly handcrafted system should find a middle term between performance and special quirks.
Let’s imagine you just asked your game to generate three nice looking noises:
Using these noises, we will now generate our world in the following order:
- Altitude (mountains and lakes)
- Optional: If you generate a 4th noise (multifractal) you can generate rivers 🙂
- Vegetation (This helps keep your trees together and realistic)
And so, let’s generate biomes. At the moment, we only care about forest and mountains, so for each value in the noise A:
- If the value is above 0,5 the biome will be mountainous
- If the value is below 0,5, the biome will be forest
After that, we will generate altitude, using noise B:
- Value between 0 and 0.1, it’s a water tile
- Value between 0.2 and 0.3, it’s a dirt tile
- Value between 0.4 and 0.6, it’s a grass tile
- Value between 0.7 and 0.85, it’s a stone tile
- Value above 0.85, it’s a snow tile
And finally, the vegetation part (my favorite) using noise C:
- Value between 0 and 0.1, we spawn a “baby shrub”
- Value between 0.1 and 0.3, we spawn an “adult shrub”
- Value between 0.6 and 0.7, we spawn a tree sapling
- Value above 0.7, we spawn an adult tree
This is a very simple world that we just generated, but you get the gist. Now you only need your imagination and implement deserts, swamps and what not :). You don’t need to do it this way, but I believe this is the easiest way to introduce people to PG.
Procedures (rules) are everything when using PG, that’s why it’s called Procedural Generation.
But Minecraft is 3d! It’s much harder than this!
Or is it? Take a look at this chunk:
Take a look at the side on the right, notice the 1st layer of grass? Notice the 3 tiles of dirt below it? And the stone below the dirt? Sound familiar? If you said yes, then you’re right. Because it is. The only difference is that Minecraft is “infinite”, and so, instead of generating the whole world as we did just now, they split it in chunks of 16x16x256 tiles.
Can you imagine what it’s like generating a chunk of these? Follow me:
- Generate a Perlin noise (remember, you generate a two-dimensional array of values between 0 and 1), this noise will be used for the entire world (not really but just go with it for now). We’ll call it noise A.
- Select a biome based on a new Perlin noise generated, (for example, below 0.5 is meadows and above 0.6 is mountains), let’s call it noise B.
- Split A in chunks of 16×16, select the values for your current chunk
- Split B in chunks of 16×16, select the values for your current chunk
- For each of the values in A (horizontal and vertical, or X and Y) :
- Find the altitude, using the previous formula (maximum x value + baseline), or your own
- Determine the tile type based on the current biome of B, (if you are generating the tile x = 10, y = 15 of the noise A, you will read the type of biome from B from the tile x = 10, y = 15)
- After the tile is filled with either grass, sand or whatever, we need to fill all the way down to Y = 0, using the following rules:
- If Y = 0, we create bedrock
- If Y < 6, there is a 70% chance of putting bedrock, and 30% of stone
- If the distance to top tile is > 10, put stone, otherwise, put dirt.
- After the chunk is generated, we can apply some cave systems. We grab our friendly Ridged Multifractal Noise we generated (let’s call it C), which is a 2d noise:
- Instead of using it as a 2d noise, we put it side by side, effectively creating a 3d noise (easy to do in-code).
- This time, we only care about values below our baseline. So, we start from there until we reach Y = 0. For each of the values in the noise C, we apply empty spaces on values above 0.7 (in the example image, 0 is black and 1 is white).
- Now that we have a chunk with the overworld and a small cave system, it’s up to the features generation, such as trees, cacti and so on… Personally I used Perlin noise to create clusters of features, such as bushes and trees, which give a nice smooth transition from smaller trees on the outskirts to bigger trees deep in the forest.
Well, so far it’s been easy to handle all of this information. For terraria and other finite games, it’s a single map with proper borders, so we just generate the world and store it in our disk. But, what about Minecraft? Well… It’s the same 🙂 we generate the chunks as we need them (when the player approaches the chunk), and store it in the disk.
It can’t be this easy… What about endless worlds? Endless universe! Like No Man’s Sky! We would run out of space!!!
No Man’s Sky
Ah yes, No Man’s Sky… Their take on this is a little more ingenious, but not new to the programming world. Do you remember how we generated the world based on the different kinds of noise? Well, that’s what they’re doing, they generate worlds using those noises and (here is where they are different from the 2 examples above) they don’t store the world in their servers. They display the generated world to the players but…
They just store the changes someone did to said world.
This means if a player is about to reach a world, the world is generated using the seed from the server. If the server has stored for this world any changes made by someone (mining a rock, building a house), it applies them after generating the world. Which means that the world is generated, but never stored in any disk. And when it’s no longer needed, the world is unloaded from memory.
So the flow is:
- Player is within world generation range
- Generate world using seed
- Load changes that players did to this world (if there are no changes, then nothing gets applied)
- Player enters the world and sees it in the same state as the last visit.
So for example, if player A enters a new world, mines some rocks and builds a base, then logs out, the server stores the broken rocks, the base and the spaceship in the server disk, but not the entire world (as we do in finite world games). If player B approaches the world, the world is generated new first. But then, it has changes that player A did to it, which in turn, get applied to the world, the broken rocks, the base and the spaceship. Then, when player B is within reach, he visually sees these changes in his computer.
With all of this information, what is the conclusion? Well, Procedural Generation is great, but it’s not for everyone. And even though it can give you endless hours of fun, it requires a lot of polish to keep the players engaged with new random stuff, and not just different flavors of the same things.
If you want to have 1 or 2 levels, do it manually. If your goal is endless levels, then go for PG. The effort to implement PG for a few levels only, it’s not worth it.
And remember: The longer you tune your system, the more unique it will be.
Interesting site on PG: https://galaxykate0.tumblr.com/post/139774965871/so-you-want-to-build-a-generator
In case you’re interested in the details of noise generation, visit https://www.redblobgames.com/articles/noise/introduction.html
In case you just wanna see something cool regarding terrain:
A talk given at GDC (more detailed):