The Diamond-Square algorithm fills a 2D grid with fractal heights by
repeatedly splitting squares in half and computing midpoints — exactly like
the 1D midpoint-displacement used in the Mountains app, but in two directions at once.
Why (2n+1) × (2n+1)?
The algorithm keeps dividing the step size by 2. The grid side must start as
a power of 2, so that halving always gives a whole number. We add 1 so that both
ends of every edge are included, giving us a closed grid with no missing boundary points.
The Two Steps — Alternating Every Pass
for each pass (step = N/2, N/4, ... 1):
DIAMOND STEP:
for every sub-square of side `step`:
center = avg(4 corners) + rand(−scale, +scale)
SQUARE STEP:
for every diamond's 4 edge midpoints:
midpoint = avg(2–4 neighbours) + rand(−scale, +scale)
scale ×= roughDecay
step ÷= 2
Key Concepts
-
Roughness / Hurst exponent.
The decay slider controls how quickly the random noise amplitude
shrinks. At 0.40 the noise practically disappears by the third pass,
leaving smooth hills. At 1.00 the noise never shrinks, producing jagged
alien terrain. The technical relationship is Hurst exponent
H = −log₂(decay).
-
Seeded PRNG.
We use a Linear Congruential Generator (LCG) seeded with a fixed value
so the same seed always produces the same terrain. This is the same
PRNG used in the Fractal Island class — it is fast, deterministic, and
needs no external library.
-
2D grid as a data structure.
The heightmap is stored as a 2D array indexed
h[row][col]. Understanding 2D arrays is essential for
game boards, image processing, simulations, and terrain generation.
-
Sea-level flooding.
We simply subtract a threshold: heights below it become ocean.
This is how real GIS (Geographic Information Systems) software
computes flood zones — no special algorithm, just a comparison.
-
Connection to Mountains app.
The 1D midpoint-displacement in Fractal Mountains is exactly
the Diamond-Square algorithm restricted to a single row. Diamond-Square
extends it to two dimensions by doing two kinds of midpoint fills
(diamond then square) instead of one.
Things to Try
- Set roughness to 1.0 and sea level to 50% — does it still look like terrain?
- Set roughness to 0.40 and raise the sea level to 80% — what does the coastline look like?
- Switch to Grayscale — this is the raw heightmap data that games and GIS software use.
- Generate a few different seeds at the same roughness. Are any two the same? Why not?