🌄 Fractal terrain

About

🎯 Illustration of various noise operators applied to a (discrete scalar) field
🎯 A tiny procedural terrain generator, comparable with techniques used in the early days of gaming, such as The Elder Scrolls II: Daggerfall and many early flight simulators
🧠 Inspired by RandomFractalTerrain-Vpython
🐍 A VPython demo is available as well, see fractal_terrain.py

Live demo

On landscape generation

Fractal height-field (`DiscreteScalarField`)
↳ Apply Diamond-Square operator/algorithm
  ↳ Hand over to a surface  (`ScalarFieldSurface`)
    ↳ Synchronize field in surface with `StandardSurfaceView`
      ↳ Color vertices based on height

The diamond-square operator

The diamond-square operator is an implementation of the diamond-square algorithm, one of the most famous algorithms used for the generation of fractal terrains. It became popular in the eighties for procedure landscape generation and is closely related to the work of Benoît Mandelbrot on fractals and the natural roughness.

Central idea

We start with a square raster, e.g.

A-------B
|       |
|       |
|       |
D-------C

where only the four corners are known. Next we fill in more points by taking averages and adding random deviations to those averages. Without the randomness, everything would end up completely flat, as we would have implemented a plain bilinear interpolation. It is the randomness that creates the valleys and the crests.

This process consists of two steps:

1. Diamond step
2. Square step

Thereafter, we repeat the same on a smaller scale.

Diamond Step

Suppose we have a square:

A-------B
|       |
|   X   |
|       |
D-------C

Then the middle point is calculated with:

$$X = \dfrac{A + B + C + D)}{4} + \text{random}$$

Which translates to:

const average = 0.25 * (
    field.valueAt(x - half, y - half) +
    field.valueAt(x + half, y - half) +
    field.valueAt(x - half, y + half) +
    field.valueAt(x + half, y + half)
);

field.setValueAt(x, y, average + this.#random(scale));

The name derives from the fact that the four points used form a diamond around the new point.

Square Step

After performing the diamond step, we end up with:

A-------B
|   X   |
|       |
|   X   |
D-------C

The points on the edges are lacking still. For a point on the edge we take the averages of the available neighbors:

    T
    |
L -- P -- R
    |
    B

Which is equivalent to:

$$P = \dfrac{(L + R + T + B)}{4} + \text{random}$$

On the edges there are fewer neighbors, so that’s why we have:

let sum = 0;
let count = 0;

and subsequently:

sum / count

so that only existing neighbors count.

Why scale becomes smaller

This is the most important idea behind the algorithm, as in nature we frequently observe:

Big structures are rough Little structures contain many details.

Natural terrains often exhibit fractal behavior. Zooming in on a mountain, we may observe:

Big mountains
  ↳ Small hills
       ↳ Little ledges
            ↳ Rock formation

The same structure appears on many different scales. The diamond-square algorithm mimics this (fractal-like) behavior. This is also the reason why in the code we use scale *= Math.pow(2, -this._roughness). After every iteration the roughness becomes smaller.

For example, if roughness = 0.5, the noise decreases slowly. This results in a chaotic, raw and rocklike landscape, where as with roughness = 2 the noise decays quickly which results in a soft, undulating and hill like landscape.

Why the grid is 257 × 257

A requirement of the algorithm is that the grid needs to be given by $2^n + 1$, as each iteration divides the raster exactly in half (`step >>= 1“), e.g.

257 → 129 → 65 → 33 → 17 → 9 → 5 → 3 → 2 → 1

Concluding remarks

This demo implements a fractal geometry where the height is the outcome of a stochastic process with self-similar characteristics. The roughness parameter determines how many height-details are being conserved.

The diamond-square algorithm is:

• simple
• fast
• resource friendly (memory/CPU)
• easy to comprehend

However, today the diamond-square algorithm is much less frequently used, as modern engines often use:

• Perlin Noise
• Simplex Noise
• Fractal Brownian Motion gecombineerd met meerdere noise-lagen

as these algorithms suffer much less raster artifacts.