Exploring the game development world: Procedural terrain generation — Theory
In my last post I said I would talk about the item system and procedural terrain generation. I’m going to start with the later.
The game I’m making is meant to be an open world, low poly, post-apocalyptic MMO — yeah, nothing new so far.
A good game that matches the description above is Unturned, where you are a survivor in a world plagued with zombies and there are a lot of places to explore and lots of things to do. Unturned is a big inspiration for this game because it adds something that Minecraft doesn’t have: an abandoned world. A post-apocalyptic world draws its magic from showing the player the world before the event (zombie outrage, atomic war, to name a few); how people lived back then, what they left behind, that sort of things are what makes you feel that things has changed and they won’t be getting back soon.
But Unturned has a static environment, of course some items can change positions between servers, but the overall map is the same, that’s one thing I didn’t want to replicate from it, because the exploration is over when you’ve met every single place, and we don’t want that. So it seems we can’t avoid creating a procedural world.
So, how to create a procedural terrain?
There are different ways we can do that, some simple, some rather complex. The simplest of all and the base of pretty much everything else is to generate heightmaps.
Heightmaps are 2D grids that defines a height value, they can be saved in textures as the one we see at the left. Represented graphically, its just a grey scale picture, as any of its color value represents the height of the respective point in the terrain.
Below we can see the same heightmap rendered in a 3D view, the pixel in the texture is interpreted as the Z (or Y) value to give the height, the lighter the pixel, the higher it’ll be.
So, we only need to set random numbers and use them as Y value, right? No. Creating a random terrain can bring us sudden changes in the ground, nature is crazy but not that crazy.
We need something else, a way to generate semi-random values that follows some degree of order. Fortunately, there exists one algorithm that can create what we are looking for: the Perlin Noise.
I’m pretty sure you have seen this picture before, maybe if you have designed anything and the tools you have used set that cloud-looking effect. Well, that’s the result of the Perlin Noise, it’s a procedural texture that follows a pseudo random behavior and can grow infinitely at any point, it could look messy but there is no sudden change in the values so there are smooth transitions between any point. The exact implementation of the algorithm deserves a whole post for itself and there are a lot of resources on the Internet to learn it, so I will only explain what it basically does in order to understand its input and output.
As a first step, the algorithm creates a constant grid where a cell contains several points, this is in the case of 2D, the noise can be created in a 3D space and in that case there would be cubes instead of squares. For each square corner, it will generate a random gradient. Both the grid size and gradients are constants and can be calculated at any given time and location, so the only inputs needed are the coordinates of the point to ask for, in the case of a texture, the (X, Y) position. The algorithm will return a float, generally between 0.0 and 1.0 that is the result of interpolating the given input between its four (or eight in 3D) grid’s gradients. In an example of creating the cloud texture we’ve seen above, we would run the algorithm for each pixel giving their coordinates and using its output as its (R, G, B) value to create a gray scale picture. Keep in mind that the picture we are creating can be infinite, it doesn’t need to have a fixed size as the algorithm works the same with any (X, Y) pair.
So, we can use the Perlin Noise to give it any 2D coordinate and get a float representing the height, we have now a procedural generated terrain and we don’t even need to create a heightmap file because the algorithm only needs the coordinates and is pseudo-random, that means whenever it receives the same input, it will result in the same output.
And yes, that’s what Minecraft uses to create its beautiful landscapes… with some tweaks of course. One of them is the common use of octaves (yes, as in music), that consists in simply generate several Perlin Noise outputs with different configurations (grid scale and gradients) at the same point and average all the results together, so we can have a more refined and random looking terrain. But for now we will not be doing that until we actually draw our terrain.
Now, knowing the theory of a basic terrain generation we move to think how to actually draw it.
Drawing the generated terrain
But wait, isn’t it enough just to draw a plane based on the heightmap we saw above? — Well, not exactly. We wan to create a sandbox game, where there are a lot of stuff you could do, like farming, mining, etc; so the ground is not the only important thing here, we want to be able to identify where is grass, where are rocks, snow, sand, that kind of stuff.
I’m pretty sure games with static maps like Unturned have a layer of data telling where is the grass where you can plant. But in a dynamically generated world we must add this detail on the mix, so I though about something like Minecraft, where each cube has its type ID and with that the game can find the cube’s properties (can be tilted, can be watered, which material it has, etc.), so this is a good model to follow.
That’s why we are going to start creating a voxel world!… At least for a start, while we create the basic layout, then we will transform it to something else.
Now, everybody knows how to draw a cube, right? Just insert the 8 vertices in the right order or define the triangles elsewhere, but to draw a cube world it’s not so simple as to draw every cube as an independent object. For example, if you draw a 3x3x3 block of cubes, you would end with something like this:
See the inner vertices no one will never see in the game? We end up with 216 vertices in total, because most of then are repeated by the neighbor blocks, and 60 of them are uselessly inside, just wasting memory and render time.
So we would need to check if a block is neighbor of another one to skip the drawing of the joining faces, like the ones we see here so we don’t waste on creating inner faces and vertices, like this.
And we would end with the same chunk resulting in a whole block without inner vertices.
To achieve this, I remembered something I learnt in my studies: graph paths. We just need to visit each block (node) and travel through their neighbors by the connecting face (edges) and if there is no neighbor block in a side, draw the corresponding face there.
Closing words
Well, that’s enough for now, next step is getting into the code and define some structures that will help us achieve what we are looking for.
If you would like to understand more deeply any concept mentioned here don’t hesitate to comment and I will take a time to write about it.
After we draw a voxel world we will see how we can transform it to a less blocky but still low poly terrain.
