Terrain from Noise

For a map I need a height at every point. The simplest idea is one random number per pixel. The result is TV static. Every pixel is independent of its neighbor, so there are no mountains and no valleys, just grains. What you want are numbers that change slowly from point to point and still look random.

Value noise is on the left, gradient noise on the right, both driven by the same sliders and the same color ramp from water through meadow to snow. The sliders set octaves, lacunarity, persistence, base frequency and seed, and dragging a map pans the view. Below them are the individual octaves of the gradient noise as gray tiles. The demo starts with linear blending on purpose so you see the grid right away. Chip 3 switches to the right curve and the grid disappears.

Random numbers on a grid

Value noise is the version you invent first. Every lattice point gets a random number and you blend in between. The number comes from a hash of the lattice coordinates and the seed, so it is reproducible anywhere and needs no storage:

inline double latticeValue(int x, int y, int seed) { return static_cast<double>(latticeHash(x, y, seed) >> 8) / 16777216.0; }

The upper 24 bits of the hash divided by 2^24 give a number in [0, 1). For a point inside a cell you take the four corner values and mix them, first in x, then in y:

const Cell c = cellOf(x, y);
const double u = applyFade(fade, c.fx);
const double v = applyFade(fade, c.fy);
const double top = lerp(latticeValue(c.ix, c.iy, seed), latticeValue(c.ix + 1, c.iy, seed), u);
const double bottom = lerp(latticeValue(c.ix, c.iy + 1, seed), latticeValue(c.ix + 1, c.iy + 1, seed), u);
return lerp(top, bottom, v);

fx and fy are the fractional part inside the cell. The applyFade in between is where the difference comes from.

The fade curve

With chip 1, u is simply fx. The slope then changes abruptly at every cell border and the eye sees that as a crease. On the left of the demo you get pyramids and diamonds, on the right a few faint folds along the grid remain. Chips 2 and 3 bend the curve so it runs flat into the cell border:

case Fade::Linear: return t;
case Fade::Cubic: return t * t * (3.0 - 2.0 * t);
case Fade::Quintic: return t * t * t * (t * (t * 6.0 - 15.0) + 10.0);

Both have slope 0 at the ends. The cubic still has a curvature there (magnitude 6), the quintic (6t^5 - 15t^4 + 10t^3) does not. That is enough for cell borders to stop standing out. The test compares them at t = 0.01: the quintic is at about a thirtieth of the cubic.

Gradient noise

Annoying: even with the good curve, value noise keeps a problem. The highs and lows always sit exactly on the lattice points, because that is where the random values are, and in between you only average. The grid shows through, just softer.

Gradient noise stores a random unit vector at every lattice point, and the height only appears when you evaluate it. Each corner contributes the dot product of its direction with the vector from the corner to the point, and the four contributions are blended as above:

const double n00 = g00.x * fx + g00.y * fy;
const double n10 = g10.x * (fx - 1.0) + g10.y * fy;
const double n01 = g01.x * fx + g01.y * (fy - 1.0);
const double n11 = g11.x * (fx - 1.0) + g11.y * (fy - 1.0);

On a lattice point the offset vector of its own corner is zero and the other contributions have weight zero, so exactly 0 comes out there (checked in the test for every lattice point). The swings are in between and the directions turn freely, so there is no grid anymore. With unit vectors the raw value stays at most √2/2 (about 0.71), I scale it with √2 to [-1, 1] and map it to [0, 1] for the map.

One quirk shows in the value range above the maps: at seed 7 and five octaves value noise runs from 0.20 to 0.91, gradient noise only from 0.23 to 0.73. With the same color ramp the right map gets hardly any snow, its values sit closer to the middle. If you want more mountains, stretch the range before coloring.

Octaves

A single layer looks like clouds. Terrain only appears in the sum: the same function once more at a higher frequency and a smaller amplitude, and once more. That is fbm (fractal Brownian motion):

for (int i = 0; i < clampOctaves(p.octaves); ++i) {
    sum += amplitude * noise(x * frequency, y * frequency, i);
    frequency *= p.lacunarity;
    amplitude *= persistence;
}
return p.normalize ? sum / amplitudeSum(p.octaves, p.persistence) : sum;

Lacunarity is the factor the frequency grows by per octave (2 means twice as fine), persistence is the factor for the amplitude (0.5: half as high). The tiles under the maps show each octave with its frequency f and amplitude a. Only the third or fourth tile brings the ragged detail, and its amplitude is so small that it hardly changes the shape of the landmass. You see how much it matters best by pushing persistence up.

Pitfalls

Normalizing: five octaves at persistence 0.5 add up to as much as 1.94. If I do not divide by that sum, the height leaves [0, 1]. The demo paints everything above orange, chip N shows it. At four octaves and frequency 11 the sum reaches 1.70 (value noise) and 1.48 (gradient noise), and large areas turn orange.

A seed of its own per octave: if all octaves used the same seed, the same lattice index would get the same value in every octave, and each octave would be a compressed copy of the first. So octaveSeed shifts the seed by 1013 per octave.

Negative coordinates: static_cast<int>(-0.5) gives 0, which is the cell to the right of the origin, and the fractional part x - 0 would be -0.5. The blending would run past the cell. That is why it goes through std::floor. Because the cast afterwards only sees values up to ±10^9, sane() clamps the coordinate first and turns NaN into 0.

Octaves that are too high: an octave finer than the resolution adds nothing but flicker. At frequency 11 the last tiles are already almost plain gray, because every tile averages several samples. Eight octaves is the upper limit in the demo.

Red Blob Games explains noise and terrain in depth, in Making maps with noise and in the introduction to noise. Flafla2 walks through Perlin noise step by step.

The code is in the repo under terrain-fbm. The project Game Dev Snippets collects all demos of the series.