ExtroForge Terrain Generation

ExtroForge uses a lot of different algorithms and formulas to determine how the terrain is generated. Today, our Team Lead Glen R. explains the process of how we achieved it.

Posted by on

In ExtroForge, the terrain of each playable level is a major part of the experience. We say, in some ways, that the planet itself is a major character in the story. That means that the terrain has to be unique and interesting enough to be the stage upon which every game is played.

Each game, round, or match in ExtroForge takes place on a 16 sq km island; 4km from East to West, and 4 km from North to South. When it came to creating the terrain, we went through several code iterations. We will be presenting a series of articles on the ExtroForge terrain generation over the next little while.

## The Terrain

The terrain in ExtroForge is procedurally generated. That means, that out of a single random number seed, each connected client knows how to create the exact same terrain, right down to the blade of grass. There are as many procedural terrains to be made, as there are random number seeds that can be represented by a 32 bit integer.

That means, that we have 4,294,967,294 different possible islands.

If you played each one in order, and each game took you an hour to complete, and you never slept, ate or did anything else but play the game, you’d have to play the game for 178,956,971 days, or 490,293 years. If each game took you a minute to play, you could get them all done in 8,172 years. And of course, if you played a game a second non-stop, it would only take you 136 years to play every island.

We thought about using 64 bit integers, which would give you 18,446,744,073,709,551,616 possible islands (which would provide you with 2,105,792,702,478,259 years of gameplay – over two quadrillion years), but we figured that a 32 bit int was enough to keep you entertained for the rest of your natural life.

So, once every client connects to the server, all we need to do is have the server tell each client the same random number seed, and just like that, every client generates the same island.

So let’s look at how the terrain itself is built.

## Base Geometry

In general, terrains are represented by something known as a height map. A height map is a black and white image, where the white parts represent the highest values, and the black parts represent the lowest values. From a height map, Unity’s built in terrain engine can be told to create the physical geometry that represents that map.

The first thing one needs to do when you want to generate a procedural terrain, is get some underlying geometry going. For this, we turn to our old friend, Perlin. The Perlin noise function generates random values from an x and a y value. It in essence creates a 2D grid of something that looks like a cloud.

If we use the Perlin noise function to begin generating our height map, all we have to do is take the result from Perlin noise, and place it directly into the height map. When that alone is used to create terrain, you end up with very smooth rolling hills, the size of which are determined by the scale of the numbers you extract from the Perlin noise function. In our case, we wanted to begin with some very large areas of useable real estate for players to have meaningful battles on, and build big bases.

However, this isn’t very interesting. It looks a little too perfect, and ends up looking like some sort of alien golf course without the golf cart to get you around.

So how do we make it a little more interesting?

## Small Bumps

Well it turns out that Mr. Perlin is once again incredibly helpful. This time, however, we use a smaller scale, and instead of setting the terrain height at each point to a specific value, we add to the terrain height that we computed in the previous step. The results begin to look a little more interesting, though still not very believable.

## Contrast

Perlin tends to look a little too evenly spread out between the highs and the lows. To fix this, we next add a little bit of contrast – we stretch the mid-range of the terrain, which creates a little more steepness as it transitions from hills to under water. The differences are subtle, but it creates higher highs and lower lows, which adds some interest – creating some nice steep cliffs to plummet off of.

## Make me an Island

One of the things that we haven’t dealt with yet is the fact that the Perlin noise goes on in every direction forever. So, at this point, if we run to the edge of the map, the edge of the world actually looks like this:

The island is quite literally sliced at the edge, where the height map ended.

Which is not very island-like.

So what we need to do is decrease the vertical scale of the height map as it approaches the edge. To achieve this, we use a simple algorithm that scales the height down by a certain percentage, based on how far from the dead center of the map it is. It’s not perfectly linear though; instead we skew the scale-down to be more heavily applied toward the edge of the map. This means that the terrain in the center of the map is unaffected, while the terrain at the edges is scaled to almost at level zero - which is ocean floor.

Technically, we don’t use a perfect circle. Instead we use something along the lines of a rounded square, which buys us a little more usable terrain, since a circle would eliminate a lot of geometry toward the corners. The results are a nice island edge that descends into the ocean on all sides of the map.

## Clamp

In a game where we’re trying to create areas where players can build bases, we need to create some level ground. As of the previous stage in our terrain generation, there’s really no level ground on the map. In other words, every polygon on the terrain has some sort of slope to it, even if it's very slight. Not ideal for placing down command posts, weapons forges, and building your epic voxel walls and structures.

So we need to do some sort of clamp, where we cap the height of the terrain at certain spots, to create plateaus that players will aim toward when dropping in from the dropship. The simplest way to do this is to set anything above a certain height, to a maximum height, or ceiling. We don’t really need to worry about clamping the minimum height – the floor – because this is always deep under water, and we want the depth. More room to build your underwater lair.

But here’s the thing – we don’t want to clamp the entire map. We do still want some peaks, so we do something similar to the island edge process. We do more clamping toward the edges of the map, while we leave the peaks in the center untouched. This helps to ensure that players will build their bases at opposite ends of the map, and creates some cool terrain obstacles between them. The result of the clamp looks like this:

That looks like a perfect place to establish a base. And it even has some resource nodes to get us started. (More on the placement of trees, objects, resources in another article).

## Coastal Erosion

One of the problems at this point is the fact that the terrain plunges smoothly into the water. There’s not really any sense of a coast, or a beach. Yes, the terrain texture draws a sand texture (more on that in another article), but beaches tend to be flat, as the effects of water over time create coastal erosion. So at this point we do a quick and dirty coastal erosion calculation, to squash and flatten things at sea level. In effect, we create beach from terrain that was previously under the water, and we smooth the cliffs that were previously plunging straight down. The results are effective:

After traveling all this way, this is a great place to set up a chair, put up an umbrella and start a beach bar. Piña colada anyone?

## Geological Stamps

So things were looking pretty good at this point. Certainly useable for a battle. But we found that there was still something missing. Something that terrain tends to do over time. We wanted to add some sort of geological erosion. The kind of thing that gives mountains and hills their unique shape, with gullies and regions where the land ‘flows’ down. The geographic term for that is fluvial erosion.

The problem is, these kinds of calculations in terrain generation are very costly and end up being very slow. Remember, these terrains are being generated on the fly, every time a player joins the game.

Fluvial erosion looks like this:

And it goes a long way to forming the realistic look of mountains and valleys in a procedural terrain. But how do we do something like that in a game, where players don’t have 10 minutes to wait for their terrain to be generated? Well, like all things in games, we need to use some tricks – to approximate the effect.

In the same way that shapes and brushes are used in a graphics program like Photoshop, we use pre-created erosion shapes and brushes, and “stamp” geological processes randomly onto the terrain over top of geometry that approximates them. So, if we have a nice hill that we want some fluvial erosion on, we rotate and scale the effect of the erosion as a brush that we imprint into the height map. We take the terrain we've generated, and mold it with a pre-calculated erosion effect.

The end result, is that we have regions of very believable erosion, on a procedural terrain, without the computational overhead:

It's not 100% geologically accurate, but it works well for a game. Just like that, you get valleys, ravines and areas where it looks like water has flowed and carved the terrain over millions of years. All this is designed to give players interesting things to do with their voxel creations. Bridges that span ravines. Fortified walls that overlook steep cliffs. Stairs that ascend from a valley to a mountain top. The options are limitless.

That’s it for part 1 of our look at the terrain generation. In future installments we’ll look at how the terrain is textured (splat map), how the grass and trees are placed, and how the entire thing is rendered as a minimap, with randomly generated geological feature names.

This is very interesting. I personally never got this advanced with the terrain in Unity, but man this is cool!

Author

It gets even better in part 2! Stay tuned for the release and thanks!