12
4
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 length2^l+1
. Atl=10
you will have to store about one million numbers. - Four seeds (floating point) for each corner
- A parameter
0<h<1
that determines the roughness (H
in the link) that means how big the random range is initially - Parameters
a,b
that represent initial lower and upper bounds for the random range and get multiplied byh
in each refinement step. (The random number is uniformly chosen betweena
andb
.
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
I created a small drawing function in javascript for displaing heightmaps in 2d as grayscale image. http://jsfiddle.net/flawr/oy9kxpsx/
If anyone of you is into fancy 3d and can make a script to view maps in 3d let me know!=)
Thank you very much! Could you perhaps provide a class around that with all the necessary imports so no big modification is needed? That would be awesome! – flawr – 2014-12-23T22:55:19.950
@flawr I'm working on it. – TheNumberOne – 2014-12-23T22:57:46.063
Just got it working, if you know how to do it, it would be great if you could make the window show up 'uncollapsed'. At least on my machine you have to draw it open every time you start it. Here is how I completed the class: http://pastebin.com/pRAMst4d
– flawr – 2014-12-23T23:03:35.863This looks awesome! I especially like the elegant way you are dealing with the boundaries where one vertice is missing=) – flawr – 2014-12-24T10:16:43.080
@flawr The window won't be collapsed when you open it now. – TheNumberOne – 2014-12-24T14:50:03.397