The diamond square algorithm is a fractal terrain (heightmap) generating algorithm. You can find a nice description how it works here:
http://www.gameprogrammer.com/fractal.html (Used as a reference.)
http://www.playfuljs.com/realistic-terrain-in-130-lines/ (Great JS implementation, perhaps you might want to steal his renderer. Take a look here what this algorithm is capable of http://demos.playfuljs.com/terrain/.)
The general idea is that you have 4 corners as seeds (a), and calculate the height of the center point by averaging those four corners and adding a random value e.g. between -0.5 and 0.5 (b). If you apply this to the grid you get again a grid of diamonds (squares turend 45°) and you repeat the same (c,d), but the random range gets smaller, e.g. -0.125 to 0.125 etc.
Your program must accept a number of inputs:
- An integer
l=1,2,3,...that determines the size of the square grid with side length
l=10you will have to store about one million numbers.
- Four seeds (floating point) for each corner
- A parameter
0<h<1that determines the roughness (
Hin the link) that means how big the random range is initially
a,bthat represent initial lower and upper bounds for the random range and get multiplied by
hin each refinement step. (The random number is uniformly chosen between
The output must consist of the finished 2d grid.
So the rough algorithm would look like this:
Create a square grid with sidelength 2^l+1 Place seed values in the corners Repeat: | Perform square steps | Refine Range: a = a*h; b=b*h; | Perform diamond steps | Refine Range
There is one detail you should be aware of: At the boundary of the grid, you will only have three vertices of the diamond, so you should also only calculate the average of those three points.
A visualization of some examples (please tell us what parameters you used) is optional but appreciated, and does of course not add to the byte count.
A slight variated implementation of this algorithm can be found here: Parallel projected voxel terrain generator
If anyone of you is into fancy 3d and can make a script to view maps in 3d let me know!=)