Diamond-square algorithm
Generates fractal terrain by repeatedly setting a midpoint to the average of its neighbours plus a shrinking random offset.
The algorithm works on a grid of side 2^n+1. Seed the four corners, then run a diamond step (the centre of each square) and a square step (the centre of each edge), where each new point becomes the average of its neighbours plus a random offset whose amplitude halves each pass.
Fournier, Fussell and Carpenter described it in 1982 as a 2D generalisation of midpoint displacement. It yields believable heightmaps cheaply, but leaves a telltale flaw: visible creases along the grid axes, because the square-step points have fewer neighbours to average.