Field Diamond Squared Fractal Terrain Algorithm
The traditional Diamond Squared algorithm for generating fractal terrain has a number of constraints that make it really hard to use.
https://code.google.com/p/fractalterraingeneration/wiki/Diamond_Square
Gives a pretty good rundown of the cons:
* The map must be stored in memory, because pixels reference other pixels.
* Because it must be stored in memory, memory becomes a constraint. [...]
* The map must have a width and height of 2x + 1 pixels.
* Has creasing artifacts if wrapping isnt used.
* Wrapping isnt always wanted.
I have solved all of these. And simplified the algorithm.
The traditional algorithm is that you set 4 corners to random values and wrap around the edges.
0 0
0 0
You double the height and width. Then each place you have four corners available to you, you insert the average of those corners and a slight random offset.
0 0
1 1
0 0
1 1
Due to the wrapping. You have four diamonds.
Then after all the diamond steps are done, you add in the square sections.
0 2 0 2
2 1 2 1
0 2 0 2
2 1 2 1
Keeping in mind it wraps around.
----
My solution is to simply view the base step as an infinite field of purely random values. This seems harder to conceptualize. But, it fixes the problems. You cant create an infinite field with twice the width as an infinite field. But, if you note, the next iteration doesnt require anything more than 1 away from the current iteration.
Even without any wrapping you can take:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
And diverge.
0 0 0 0
1 2 1 2 1
0 2 0 2 0 2 0
1 2 1 2 1
0 2 0 2 0 2 0
1 2 1 2 1
0 0 0 0
We went from a 4x4 to a 5x5. Next it goes to a 7x7 then a 11x11 then a (2n-3)x(2n-3)...
So we can simply reverse this with our well formed request.
If we want 1000x1000 block of data say at the range [0-1000], [0-1000] at 24 iterations (which under the traditional method would require 2^48 bits of memory to store), we can request:
[0,1000] [0,1000] @ 24 which means we divide the range in half rounding towards the larger area and increasing the bounds by 1.
We need the range:
-1 to 501 @ 23
Then:
-1 to 252 @ 22
Then:
-1 to 127 @ 21
Then:
-1 to 65 @ 20
Then:
-1 to 34 @ 19
Then:
-1 to 17 @ 18
Then:
-1 to 10 @ 17
Then:
-1 to 6 @ 16
Then:
-1 to 4 @ 15
Then:
-1 to 3 @ 14
Then:
-1 to 3 @ 13
...
...
Then:
-1 to 3 @ 1
Then:
-1 to 3 @ 0 which simply returns a field of 4x4 random numbers.
Rather than all that nonsense with wrapping and seeding and making what is actually a special case of the base case, we can simply reduce the algorithm to:
getTerrain(x0,y0,x1,y1,iterations) {
if (iterations == 0) return maxtrixOf(random numbers);
map = getTerrain(floor(x0/2) - 1, floor(y0/2) - 1, ceiling(x1/2), ceiling(y1/2), iterations-1);
make a newmap twice as large.
copy values from map into x*2,y*2 locations in newmap.
apply diamond where possible. +- smaller random offset
apply square where possible. +- smaller random offset
return requested area from within newmap. (This is typically newmap from [1,(n-1)] [1,(n-1]
}
Done.
Thats the entire algorithm. No more constraints and its easier. On top of this the number of iterations doesnt control the size of the field but rather smoothness, of the underlying fractal. And since the base case is seen as an infinite field of purely random numbers, it goes on forever even at just a couple iterations as the iterations has no bearing on the size (its always infinite).
On top of this rather than using a random number, you can use the the x, y, and iterations to make a pseudorandom but deterministic number like through a SHA1 hash. Then you can page from within the same area, forever without needing to have calculated all of it to start. You can create an infinite landscape without needing infinite memory to start, and returning to the same coordinates will give you the same results, and it doesnt matter which way you took to get there. There will be deterministic.
---
I hacked together a working bit of the code in javascript:
http://tatarize.nfshost.com/FieldDiamondSquare.htm
Stealing liberally from http://www.somethinghitme.com/2009/12/06/terrain-generation-with-canvas-and-javascript/
---
Also check my newer algorithm Olsen Noise (though still lacking a javascript implementation) which corrects the artifacting and allows it to be changed into N dimensions. It also, simplifies. The algorithm even more.
http://godsnotwheregodsnot.blogspot.com/2014/08/3d-olsen-noise.html
download file now