Saturday, November 9, 2013

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 isn't used.
* Wrapping isn't 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 can't create an infinite field with twice the width as an infinite field. But, if you note, the next iteration doesn't 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.

That's the entire algorithm. No more constraints and it's easier. On top of this the number of iterations doesn't 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 (it's 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 doesn't 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/



4 comments:

Anonymous said...

Very interesting. Would you be able to explain (or better, show) a little more how you would implement the infinite scrolling field where going back to the same coordinates would be deterministic? I can't see from your javascript example how you could do that, even with a deterministic pseudorandom number generator. It seems like in your example you still need to generate an array the size of your map to store and display the data.

Tatarize said...

You would have to use the coordinates in a sort of hash. So that two X, Y values will give you a somewhat random number but will always produce that number given the same input. Fed into a SH1 hash or largely any type of hash of sufficient quality would work.

Tatarize said...

I really need to demonstrate that part accurately. So as to allow the canvas to scroll and also fix the noisiness of the algorithm. The randomness between iterations is too great and it produces excessively noisy images.

Tatarize said...

Okay. I fixed it. Check the demo again and you'll find it allowing you to drag the canvas around.

It isn't storing anything at any time. It regenerates the entire thing each and every refresh.