The idea: split, nudge randomly, halve the nudge
Midpoint displacement turns a straight line into a mountain ridge with one rule, applied again and again:
- Split every segment in half.
- Put the new middle point at the average of the two ends.
- Nudge it up or down by a random amount between −d and +d.
- Shrink d (halve it, in the classic version) and go back to step 1.
The page's line has 65 points: the ends are 30 and 55, the first nudge is up to ±40, and 6 levels of splitting give 3, 5, 9, 17, 33 and 65 points. Each level is two Steps: the new points appear in orange on the old line, then move by their nudge. (Demo: first 2 levels of the line, with numbers, then Demo: a ridge line in 6 levels, nudge × ½.)
In symbols, for the point between a and b at level k:
h(mid) = (h(a) + h(b)) / 2 + random(−dₖ … +dₖ) dₖ = d₁ · f^(k−1), f = ½Why the nudge must shrink
At level k the segments are 64 / 2ᵏ long. If the nudge shrinks by the same factor as the segment, each new bump is the same shape as the bumps before it, only smaller: zoom into any piece of the ridge and it looks like the whole ridge. That is statistical self-similarity, the random cousin of the exact copies in a Koch curve.
The factor f is the roughness knob, usually written f = 2^(−H) with H the Hurst exponent:
| nudge factor f | H | what the line looks like | demo |
|---|---|---|---|
| 0.35 | ≈ 1.5 | smooth rolling hills: the first nudges decide the shape, later ones barely show | smooth hills, nudge × 0.35 |
| ½ | 1 | the classic: big shapes plus visible small bumps | a ridge line in 6 levels |
| 0.7 | ½ | a rough, jagged ridge, like a random walk (Brownian motion) | rougher, nudge × 0.7 |
| 1 | 0 | spikes: every level adds as much as the first, so the line is noise | never shrink the nudge |
For a line with 0 < H < 1 the fractal dimension is about 2 − H: a ridge with f = 0.7 has dimension near 1.5, more than a line but less than an area. (For f < ½ the later nudges are smaller than the segment shrinks and the line ends up smooth, dimension 1.)
Diamond-square: the same rule on a map
A terrain is a heightmap: a grid of heights, 17 × 17 on this page (2⁴ + 1, so 4 levels). Start with the 4 corners set: 35, 75, 15 and 55. Each level has two steps, both with the level's nudge:
- Diamond step: the centre of every square gets the average of the square's 4 corners, plus a nudge.
- Square step: the middle of every edge gets the average of its neighbours left, right, up and down (only 3 on the border), plus a nudge.
Then the squares are half as wide and the nudge is multiplied by f. The new cells show in orange with only their average, then get their nudge and the colour of their height band: water below 20, sand, grass, rock and snow from 80. Levels 1–4 set 1 + 4, 4 + 12, 16 + 40 and 64 + 144 cells. (Demo: diamond-square, level 1 step by step and Demo: diamond-square to a 17 × 17 map.) The name comes from the shapes: in the square step each cell's sources form a diamond.
Seeds: the same number gives the same world
The nudges come from a seeded random generator. The same seed always gives the same nudges, so the same landscape; that is why Undo and Reset replay exactly, and how games rebuild a huge world from one stored number instead of saving every height. (Demo: another seed, another landscape.)
Creases, and what games use now
Diamond-square was published by Fournier, Fussell and Carpenter in 1982 and drove early fractal landscapes in films and games. Its weak spot is visible on a big map: the first splits happen along fixed lines, so faint straight creases can follow the grid. Today most terrain generators add up several layers ("octaves") of smooth gradient noise (Perlin or simplex noise), each twice as detailed and about half as strong as the last: the same idea of "smaller detail, smaller amplitude", without the grid artefacts and with no need for a 2ⁿ + 1 size.
See also Fractal Curves for exact self-similar copies, The Chaos Game and The Barnsley Fern for fractals drawn by random choices, The Mandelbrot Set, and Monte Carlo Estimation of π for more seeded randomness.
What the page leaves out
Gaussian nudges (the classic method uses a normal distribution; the page uses whole numbers spread evenly in −d … +d so the sums are easy to read); random end and corner heights; maps that wrap around; erosion, rivers and other post-processing that make real game terrain; 3D rendering of the heightmap; and the proof that the dimension of the surface is 3 − H.