In this blog post I will discuss some technical details and give a glimpse of Terraced Terrain Generator’s (TTG) development process. TTG is a free Unity tool for procedural generation of terraced terrain meshes. It’s open source and it’s on GitHub! Here are some examples of the type of terrains TTG is able to generate:

Five images of generated terraced terrains looping. The post follows TTG’s four terrain generation steps: basic shape generation, mesh fragmentation, mesh sculpting and terrain slicing. Then, we discuss performance improvements and future developments. Finally, a short conclusion wraps the post up.

Let’s dive in TTG’s generation steps right away.

Step 1: Basic shape generation 📐

This step is responsible for generating the polygon that will server as a basic shape for the terrain. In order words, how the terrain will look like from a high up, top view.

Supported shapes

  • Equilateral triangle.
  • Any regular (equilateral and equiangular) polygon, from 4 to 10 sides.

Equilateral triangle

Generating an equilateral triangle is trivial: create 3 vertices equally distant from the center of the terrain. Each pair forms a 60° angle with the center.

Triangle

Any regular polygon

All other regular polygons (independent of the number of sides) will be generated using the same strategy. We take advantage of the fact that regular polygons can be created by composing triangles and define all polygon generation based on it. Regular polygons are perfect for this task because their vertices are equidistant from the polygon’s center.

💡 Although it is possible to generate polygons with any number of sides using this strategy, the number of sides is limited to 10.

Square

A square can be created by overlapping 2 isosceles, right-angled triangles on their hypotenuses. The triangles are created in a similar manner to the equilateral triangles described above, but vertices are recycled to save memory. A square contains 4 vertices and 2 triangles.

Square

Pentagon

A pentagon can also be created using triangles, but differently from the strategies described above. A vertex is placed on the center of the pentagon and it’s used by all triangles that compose the polygon. All other vertices are equidistant from the center vertex. Once again, vertices are recycled to save memory.

Pentagon.svg

Other regular polygons

Other regular polygons with more than 5 sides are created using the same strategy as the pentagon’s, just increasing the number of vertices. For example, here’s a decagon:

Decagon

Step 2: Mesh fragmentation 🧨

The basic shape generated by the previous step does not contain enough vertices and triangles to generate a nice terrain. We need to fragment it into smaller triangles to increase its detail and resolution.

We start by taking advantage that all shapes generated in the previous steps are composed by triangles. Then, we can fragment these triangles into smaller ones. Breaking down a triangle into smaller triangles is trivial: divide it into 4 triangles like the image below. The outer, bigger triangle is the original one and the smaller, inner triangles are the outcome of a triangle fragmentation.

Triangle fragmented once

The fragmentation can continue recursively, on the generated triangles. If we fragment the 4 triangles above, we would obtain the following 16 triangles.

Triangle fragmented twice

The more fragmentation iterations we perform, the higher is the resolution of the final mesh. We can say a mesh was fragmented with a depth D of there were performed D fragmentation iterations on it. The resulting mesh will contain $T * 4^D$ triangles, where T is the number of triangles in the original mesh and D is the fragmentation depth.

Here’s an example of a triangle that has been fragmented 6 times (depth = 6):

Triangle fragmented six times

Here’s a pentagon that has been fragmented 5 times (depth = 5):

Pentagon fragmented 5 times

Step 3: Hills and valleys generation (a.k.a. mesh sculpting) 🏔

Now that we’ve got a flat surface which serves as a base to a terrain, it’s time to create hills and valleys to make the terrain more interesting.

Requirements

  • Fully automate this task, eliminating the tedious job of terrain shaping.
  • It should be able to repeatedly generate random terrains.
  • At the same time it should have a deterministic behavior, so it could easily reproduce a given terrain whenever necessary.
  • The following should be generation parameters:
    • The feature frequency (how often hills and valleys are formed).
    • The maximum height of the generated hills.
    • The height distribution curve.

The strategy

The chosen strategy is well known in the field, yet it’s quite efficient: noise filters. These filters can generate noise, often following some pattern. Simply put, they are functions that, for a given point in space, will return a noise value - often between 0 and 1. The idea is to use the noise values to sculpt the mesh by moving its vertexes upwards, creating hills. This can be accomplished by multiplying the noise value by the maximum height, and adding it to the vertex’s y coordinate.

1
vertex.y += noise(vertex.x, vertex.y) * maximumHeight

The challenge is to choose the right filter. Fortunately, the Perlin filter is famous for delivering filters that are a great fit for the kind of sculpting we’re looking for. Better yet, Unity’s standard API already contains a function for Perlin noise: Mathf.PerlinNoise. Here’s an example of an image of a Perlin filter:

Perlin noise example

In order to control the frequency, we simply multiply the vertex coordinates by a given parameter frequency.

1
2
3
var filterX = vertex.x * frequency;
var filterY = vertex.z * frequency;
vertex.y += height * Mathf.PerlinNoise(filterX, filterY);

Unity’s API call doesn’t support randomizer seeds, so we had to get creative. We introduced randomisation by offsetting all vertices’ position by a random value.

1
2
3
4
5
6
7
8
9
10
11
12
var vertices = mesh.vertices;
var xOffset = _random.Next(-1_000, 1_000);
var yOffset = _random.Next(-1_000, 1_000);

for (var i = 0; i < vertices.Length; i++)
{
    var vertex = vertices[i];
    var filterX = (vertex.x + xOffset) * frequency;
    var filterY = (vertex.z + yOffset) * frequency;
    vertex.y += height * Mathf.PerlinNoise(filterX, filterY);
    vertices[i] = vertex;
}

And to add replicable, deterministic terrain generation, the randomizer’s seed can be provided.

Outcome

The outcome was quite convincing. Here’s an example of a pentagon-based terrain, fragmented 2 times (depth = 2), with a maximum height of 5 and a frequency of 0.2.

Terrain1

Here’s another example; an octagon-based terrain, fragmented 6 times (depth = 6), with a maximum height of 10 and a frequency of 0.2.

Terrain2

Here’s the same octagon-based terrain with a frequency of 0.5:

Terrain3

Height curve

Even though this strategy delivers great results and we can control the noise frequency, it would be great if we could control other parameters. For example, we could benefit from controlling the height distribution over the terrain: how low valleys and how high hills should be, and everything in between. This would allow developers to customize the terrain with characteristics such as “I want a mostly flat terrain, with sudden hills”.

This can be accomplished by using a height curve that modifies the output of the Perlin noise algorithm. This curve would be limited to the [0,1] interval, on both X and Y axes, where the X axis represents the Perlin noise output and the Y axis represents the modified value. Finally, the final value can be multiplied by the maximum height as explained on the section above.

Such a curve can be easily defined in Unity using Animation Curves. The function that calculates the height of a given points becomes:

1
2
3
4
5
6
7
8
9
static float GetHeight(float x, float y, float maximum, AnimationCurve heightDistribution)
{
    // Step 1, fetch the noise value at the given point
    var noise = Mathf.PerlinNoise(x, y);
    // Step 2, apply the height sculpting curve (if it's not null) to the noise value
    var modifier = heightDistribution?.Evaluate(noise) ?? 1;
    // Step 3, apply the modifier to the maximum height
    return maximum * modifier;
}

At this point, we can start playing with the height distribution curve. Let’s play with a given terrain, changing the height distribution curve to see how it modified the generated terrain. A “neutral” curve (a curve that doesn’t modify the Perlin noise values) should output the same value as its input. That can be accomplished with a linear curve starting from (0,0) and ending at (1,1).

1c.png

The neutral curve generates the following unmodified terrain:

1t.png

Now let’s start playing with the height distribution curve. First, let’s try to change it to the following exponential curve:

2c.png

The curve above generates the terrain below. Notice how the hills seem higher. In reality, they are not; the valleys around the hills are lower.

2t.png

Let’s be even more aggressive in that distribution, bringing the lower values even closer to the Y=0 line and rise quickly towards (1,1):

3c.png

The curve above generates the following terrain. As expected, the terrain is flatter and the hills quickly “bump” out of the plane.

4c.png

We can get more creative and create curves like the one below, which creates a plateau with a few canyons:

4c.png

The curve above generates the terrain below.

4t.png

Or even a curve that has a plateau, but still has both hills and valleys:

5c.png

The curve above generates the terrain below.

5t.png

At this point, we have good control of the height distribution.

Step 4: Terrain slicing 🔪

The approach

Now that we’ve got a terrain with hills and valleys, it’s time to start creating some terraces. the method I used was based on Icospheric Planetoid’s approach of using the meandering triangles algorithm to slice each triangle using planes that are located exactly where the terraces will be. Check their article for further explanation on how that algorithm can be applied on this domain.

Here’s an example of a terrain before and after slicing it into 15 terrains:

Terrain before slicing

Sliced terrain 1

The end result looks great, but something is missing…

Material assignment

Using the same material for all terraces is boring. Ideally, we should be able to assign a different material for each terrace to introduce some color palettes and progressions. To achieve this, terrace generation creates multiple sub-meshes, one for each terrace. This simple trick allows for material assignment on a sub-mesh basis in Unity. The image below is an example of how simple color changes can influence a terrain’s look:

Sliced terrain 2

Custom terrace heights (added on version 1.1.0)

Even though material assignment brings new customization capabilities to TTG, and I was happy with what version 1.0.0 delivered, there was still room for improvement. I was particularly bothered by the fact that all terraces were equally spaced—the height gap between a terrace and its predecessor was constant. Equal spacing might be desirable in some scenarios, but in others it just doesn’t make sense, particularly when we’re trying to resemble real-life terrains.

Take a sandy beach with multiple terraces representing the sand, for example. If they’re equally spaced, the height gap between each sand terrace will be considerable, which doesn’t match the smooth, slow ascends of a sandy beach. At the other end of the spectrum are snowy mountain peaks, which every so often extrude from their surroundings. A constant progression spanning from the bottom of the ocean to the highest mountain peak (like the last picture from the session above) doesn’t look convincing.

With that in mind, version 1.1.0 added support for custom terrace heights. In addition to the existing generation parameters, users can provide an array of relative terrace heights: floating point values between 0 (0%) and 1 (100%) that represent the height of the terraces relative to the terrain’s maximum height. On a terrain with a maximum height of 10 units, a relative terrace height of 0 would place that terrace at 0 units high. A terrace with a relative height of 1 would be placed at 10 units high, and one with a relative height of 0.62 would be placed at 6.2 units high, and so on.

Implementing this feature did not require substantial code changes, and it did not introduce a new generation step. Previous versions already used a terrace height array during the slicing step of the terrain generation—it just wasn’t customizable, and the terrain heights were equally distributed between 0 and the terrain’s maximum height. All that was necessary to introduce this feature was to replace the existing code that calculates terrace heights with code that takes the user-defined relative terrace heights into consideration:

1
_terraceHeights = relativeTerraceHeights.Select(h => h * maximumHeight);

We can modify the last terrain example using the new custom terrace heights feature to make it more dynamic and convincing. Sandy terraces can be placed unevenly and closer together to reflect the smooth ascend of a beachfront. Desert terraces can be placed closely to mimic an erosion effect. The gap between the dry and snowy portions of the mountains can be widened to highlight the mountain’s peak. The image below displays an example of these changes:

Perlin noise octaves (added on version 1.2.0)

The problem

Custom terrace heights were a nice addition to TTG, but something still felt off. The generated terrains look great, but they don’t exactly pass as real-life terrains. An example is the best way to understand the problem at hand. Take the following terrain, with a feature frequency of 0.055: Even though it looks quite nice, it is quite feature-poor and its edges are quite smooth, far from natural-looking. How can we change the generation parameters to obtain more detail? Given that the level of detail is a generation parameter (a.k.a. feature frequency), we can try increasing it. Let’s give it a try. If we increase the feature frequency of the terrain above to 0.7, we get the following terrain:

The terrain above is definitely feature-rich, but it has two problems. First, if you look closely, you will notice that the features are relatively smooth and none of them resembles erosion, random land formations, pits, etc. Second, there is a lot of repetition. It seems like the terrain was generated by creating an island terrain, copying and pasting it dozens of times side by side. Tweaking other generation parameters might help a bit, but only gets us so far.

Ideally, we would like to have more details and variation within the terrain features; not just copies of the same features, over and over again. It would be nice to be able to create, for example, a terrain with a large portion of water with some bays and a detailed, feature-rich land with large beaches containing some peninsulas and islands, a dense forest with some clearings and rocky mountains with signs of erosion. In short, it would be great to have more imperfect, natural-looking terrain.

The behavior described above is a characteristic of the noise algorithm chosen on step 3: Perlin noise. The previously introduced sample graphical representation of a Perlin noise output is a great way to gain some insight on what is going on: Perlin noise example Notice how the features (white and black areas) are of comparable size. There are no large areas, neither black nor white. Similarly, there are no small but abrupt color changes; the clusters are always surrounded by a gradient. Finally, the shape of the features is mostly round, with smooth transitions between them.

These characteristics reflect on the generated terrains. Clusters (either mountains or valleys) are of similar size, there are no abrupt changes of height and their shape is mostly round, with smooth edges. In other words, there is a general lack of detail within the terrain features.

The solution

There is a well-known strategy to eliminate this problem: Perlin noise octaves. The general idea is to apply multiple passes of Perlin noise algorithm, each one with a higher frequency than the previous one, but with a lower “strength”. The outcome is a noise that resembles and preservers the shape of the original one, but with finer, more localized detail. When applied to terrain generation, it potentially generates more natural-looking terrains—depending on parameter values.

Perlin noise octaves can be implemented as different iterations (or passes) using a for loop. Each iteration represent an octave and will apply the Perlin noise algorithm with slight different frequency and “strength” (often called “amplitude”), based on the values of the previous octave. Initially, the amplitude is set to 1 (representing 100%) and the frequency is set to the terrain’s base frequency. At the end of each iteration, the frequency is increased by multiplying itself by a constant factor (often called lacunarity, greater than 1) and the amplitude is decreased by multiplying it by another constant factor (often called persistence, less than 1). This process is repeated as many times as the desired number of octaves.

The function below uses Perlin noise octaves to calculate the height of a vertex based on its coordinates and the number of octaves to be applied. It is a slightly modified version of the code snippet in step 3. The values of the base frequency, persistence and lacunarity are constant for demonstration purposes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static float GetHeight(float x, float y, uint octaves, Vector2[] offsets)  
{  
    float height = 0;  
    var amplitude = 1f;  
    var frequency = 0.055f;  
    const float persistence = 0.5f;  
    const float lacunarity = 2.5f;  
    for (var i = 0; i < octaves; i++)  
    {       
       var offset = offsets[i];  
       var filterX = x * frequency + offset.x;  
       var filterY = y * frequency + offset.y;  
       var noise = Mathf.PerlinNoise(filterX, filterY);  
       height += amplitude * noise;  
       frequency *= lacunarity;  
       amplitude *= persistence;  
    }  
  
    return height;  
}

A fairly similar function is used in TTG’s code, with parameterized values instead of hard-coded ones.

The outcome

Perlin noise octaves are a simple solution that delivered a quite satisfactory result. The GIF below displays the usage of Perlin noise octaves, with four terrains: the terrain we’ve been using as an example in this section, and three other ones; each one with an increasing number of Perlin noise octaves, from 1 to 3 (check the right bottom corner of the image for octave count). All terrains were generated with a persistence of 0.375 and a lacunarity of 2.52. A looping gif displaying 4 different terrains, with increasing Perlin noise octaves count, from 0 to 3 The value of the octaves is clear: they add detail without changing the scale of the terrain, delivering a more natural-looking outcome. Both the API and the helper component were updated to support Perlin noise octaves.

Performance improvements ⚡️

Even though the goal of the terraced terrain generator was mostly accomplished on the feature level, performance was far from ideal. The efforts put into performance improvements were described in a separate article.

What’s next? 🔮

Although it looks like the Terraced Terrain Generator is complete, there’s always more work to be done. The following features are planned in future updates:

  • Custom terrain heights: instead of evenly spacing the terraces between the terrain’s lowest and highest points, allow custom heights to be chosen. Implemented on version 1.1.0.
  • Improve terrain detailing: use Perlin noise octaves to create more natural terrains. Implemented on version 1.2.0.
  • Sphere as a basic shape: let’s create completely terraced planets!
  • Realtime sculpting: instead of letting an algorithm generate the hills, let the user interactively sculpt them.
  • Outer walls: “close” the generated mesh so it looks like a model carved in wood, sitting on a desk.

You can follow the development of TTG in its Trello board. If you have suggestions, feature requests or bugs to report, use the Issues section of TTG’s GitHub repository to communicate them.

Conclusion 🏁

TTG was a great side project that taught me a lot about several aspects of game development tools creation—including non-coding nuances. I hope the effort I’ve put in the creation of the tool and its documentation help someone out there.

If you made it this far, thank you very much for the dedication. I hope you’ve found this an interesting read. As usual, feel free to leave comments, suggestions or corrections in the comments section. See you next time!