Algorithms for Procedural Terrain Heightmaps

Procedural terrain generation in video games relies on mathematical algorithms to create expansive, realistic landscapes without manual modeling. By calculating elevations across two-dimensional grids, developers produce heightmaps representing mountains, valleys, plains, and coastlines. This article covers the foundational mathematical algorithms used in procedural heightmap generation, including gradient noise functions, fractal subdivision, Voronoi partitioning, and physical erosion simulations.

Gradient Noise: Perlin and Simplex Noise

Gradient noise functions are the bedrock of procedural terrain. Developed by Ken Perlin, Perlin noise assigns pseudo-random gradient vectors to grid points and computes interpolations between them to yield smooth, continuous value transitions. Simplex noise improves on this by dividing space into simplexes (triangles in 2D) rather than hypercubes, reducing computational complexity from \(O(2^n)\) to \(O(n^2)\) and eliminating directional grid artifacts. These algorithms provide the base elevation layer for natural terrain.

Fractal Brownian Motion (fBm)

Raw noise creates smooth, rolling hills rather than rugged mountains. To introduce natural roughness, developers use Fractal Brownian Motion (fBm), also known as octave summing. This technique layers multiple evaluations of a base noise function at increasing frequencies (detail) and decreasing amplitudes (influence). The mathematical formula combines these layers:

\[\text{Elevation}(x, y) = \sum_{i=0}^{n-1} \text{gain}^i \cdot \text{Noise}(x \cdot \text{lacunarity}^i, y \cdot \text{lacunarity}^i)\]

Here, lacunarity controls the frequency multiplier per step, while gain (or persistence) scales the amplitude, producing self-similar fractal details seen in real topography.

Midpoint Displacement and the Diamond-Square Algorithm

Midpoint displacement is a recursive fractal subdivision technique. The Diamond-Square algorithm applies this concept to a two-dimensional square grid:

  1. Initialization: Assign height values to the four corners of the grid.
  2. Diamond Step: Find the center point of each square and set its height to the average of the four corner points plus a random offset.
  3. Square Step: Find the midpoint of each diamond shape and set its height to the average of its corner points plus a random offset.
  4. Iteration: Reduce the random offset range and repeat the process on smaller sub-squares until every grid cell is resolved.

This method generates highly fractured, mountainous terrain efficiently, though it can exhibit subtle square-aligned artifacts.

Voronoi and Worley Noise

Voronoi diagrams partition space based on the distance to a set of randomly distributed feature points. Worley noise uses the distance to the \(n\)-th closest point to compute a height value. In heightmap design, Voronoi mathematics generate distinct structural formations such as volcanic calderas, cracked desert basins, mesas, and tectonic plate boundaries.

Domain Warping

Domain warping feeds the output of one noise function into the input coordinates of another:

\[\text{Height}(p) = \text{Noise}(p + \vec{D}(p))\]

Where \(\vec{D}(p)\) is a vector generated by secondary noise functions. This distortion bends the rigid symmetry of standard noise, producing realistic geological patterns such as winding river valleys, twisted mountain ridges, and dynamic coastlines.

Hydraulic and Thermal Erosion

Purely mathematical noise lacks the directional wear caused by gravity and climate. Developers apply physical simulation algorithms as a post-processing pass:

  • Thermal Erosion: Simulates rockfall and weathering. When the slope between adjacent grid cells exceeds a threshold (the angle of repose), material shifts from the higher cell to the lower one.
  • Hydraulic Erosion: Simulates rainfall and water runoff using particle or grid-based fluid dynamics. Virtual raindrops land on the heightmap, flow downhill based on the height gradient, dissolve sediment, deposit it in lower depressions, and evaporate. This forms natural drainage basins, river tributaries, and alluvial fans.