Diamond-square algorithm

The diamond-square algorithm is a method for generating heightmaps for computer graphics, used to build realistic looking landscapes and as a component of procedural textures. It is also known as the random midpoint displacement fractal, the cloud fractal or the plasma fractal, after the plasma effect it produces when applied. It begins with a square array of width and height 2 to the power n plus 1, with the four corner points set to starting values. It then alternates two steps until every value is set. In the diamond step, the midpoint of each square is set to the average of its four corner points plus a random value. In the square step, the midpoint of each diamond is set to the average of its four corners plus a random value. The random value is multiplied by a scaling factor that shrinks by a factor of 2 to the power minus h on each iteration, where h lies between 0 and 1 and lower values give rougher terrain. Points on the array edge have only three neighbours, which is handled by averaging those three or by wrapping around to the opposite side, which lets separately generated fractals be stitched together. The idea was first introduced by Fournier, Fussell and Carpenter at SIGGRAPH in 1982. Gavin Miller later described it as flawed because it leaves visible creases along the grid, and J. P. Lewis generalised it to reduce those artifacts.