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/
---
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
19 comments:
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.
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.
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.
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.
Quick Questions
1. What if wrapping is desired for the inifinite terrain or just the specific tile?
2. Where would a hash table or randomized from a seed be implemented?
Sorry. I meant randomized seed.
1. You could still wrap in specific directions, but only within the limitations of the original algorithm. So you could make a (2Q)^N-1 (where Q is the initial size at the base case) by infinity field by making the base case infinite in one direction and of a set size in a different direction.
The main advantage of making it a scoping field algorithm is that you can have an infinite base case and you don't have to calculate all the end values, but have a stable algorithm by which you can do that.
But, you could have a finite base case or any base case you wanted including one also seen in the original algorithm. As well as wrapping base cases. Or hybrid infinite/finite base cases. The caveat however. There is a caveat. Which I'll get to because it fits so well with your second question.
2. The reason you need a hash is that you don't want a real random number generator. You want something that is deterministic. You need something that for any particular X and Y and iteration will always give you the same number which *looks* random. And that's the secret there. Because recalculating the values will *always* give you the same answer, then can tunnel in on a specific portion of the final solution (which means the final solution can be infinite).
Now, the wrapping caveat is this, it needs to have the same answers everywhere. So at each iteration you need to wrap the Y value at a different amount. So for example if the first height is 1. The second height is 2. The third height is 4. So each iteration the hash has to be identical. I think it's simply having the hash at the base case be mod(1) and the next case be mod(2) and the next iteration mod(4) but I'm not sure. I haven't actually explored the issue.
Now if your second question is how would you apply a seed to the algorithm in effect making each one give you a different fractal. You simply add that to the hash routine. So the hash for (x,y,iteration,seed) should always be the same and should always seem random.
(Hash tables simply hash data and put it in particular buckets so that it can hash new data to look for the original data by searching just the bucket it would have been put into. You aren't using a hash table here, but just a hash).
I also had a bit of discussion about the wrapping issue in my follow-up bit on Olsen Noise. Where I take the Diamond Squared out of the algorithm completely it replace it with a more coherent box blur. Which solves problems or artifacting and differing max values and allows it to be expanded into N dimensions out of the box (a feat that proved untenable with diamond squared).
http://godsnotwheregodsnot.blogspot.com/2014/08/3d-olsen-noise.html
I've been trying to convert the code to the C++ equivalent. I think I got it but it's still bugged. Maybe you can pick up on the mistake.
Vivienne
Picture of generated image:
http://tinypic.com/r/oistxi/8
Blog with code:
http://urho3d.prophpbb.com/topic435.html#p2398
That's noise. You've got it. It's crimping prematurely or isn't setup to deal with grays. You get the foggier look by intermediate gray forms. Seems like there's a couple but not enough.
Looks like it's just a problem either normalizing it or with the extremes. Try asking for a smaller size and just outputting it in numbers. Gives you a pretty good understanding of what's going on or wrong as the case may be.
I would be more helpful but the C++ link lead to nothing. Or rather a downed site.
The more typical place to get bugged up is passing the request and losing where you are at one level to another level. You really need to be able to move around to be sure you're doing it right.
While the code is great when it works, there's kind of a pain in the butt when it comes to applying kernels to a scoped context like that. I'm planning on finishing up the code for my newer noise algorithm in Java and posting that. Wouldn't be too hard to back port the Diamond Squared version.
Or let me see a copy of the source somehow Tatarize at the yahoo (if you don't want to plain text it somewhere due to different licensing (my Javascript should be MIT license so use it for whatever).
)
This is the code. That I'm having problems with.
http://pastebin.com/79QtUPkE
Code looks like a solid transcode of the javascript version.
int col=(int)(image[x+(y*newimage.get_width())]+1)*255;
I'd say this is the bug. The values are between 0-1 and so. And you convert to (int) outside where you multiply by 255. So the *only* two values accepted are 0 and 255, aka white and black.
Multiply that number by 255 and then cast it to an int.
That's not the problem.
I did a cout on the map values before writing to a png.
Some individual values are
0
-8.59313e-05
0.000740951
-0.00112015
-0.00146794
So, I guess a take a look at it again!
Hm. I think I saw an error like this before and I just recoded the normalization routine to make sure it knew the high value and the low value and then put everything between those at 0 to 1.
Depending on the needed application I have my newer noise algorithm written in Java and totally functional now. I genuinely think it's a lot better than DS.
http://pastebin.com/gh6P5zf3
Stable and doesn't require any normalization, heck I have it currently running on integers and will natively range from 0-255, for each pixel (rather than having any artifacts), and is a bit easier to follow.
I'll double check the DS code though.
Okay. Somehow I managed to ignore the fact in my Javascript version that the given randomized bits have to be variations from zero. So when they are normalized by the maximum amount they are normalized to values between -1 and 1 not 0 and 1. Javascript apparently has no objection to a colordata of -39. Etc. And since the absolute value of a fractal noise is fractal noise (basically everything you do it it makes it still just fractal noise).
The reason its giving you those numbers is because the normalization is different than what the Javascript would have assumed.
The reason they needed to be values centered at zero is that DS as a general rule has artifacting that just gets blurred away by the noise. The max deviation at some points are actually greater than at other points. If the random additions are actually all additions rather than variations it causes the pattern to show (one of the reasons I made my newer noise algorithm to avoid those artifacts).
But, to avoid them you need to make all random changes deviations from zero. Which I did. Then I normalized by dividing by the maximum deviation. But, that simply makes the normalization between 1 and -1. And javascript didn't throw an error. And if it spits out the absolute value like it very well might be doing, you can't see it because oddly doing that just produces slightly darker fractal noise.
I'll fix my javascript version. But, checked the debugger in Chrome and sure enough it's feeding negative numbers into the colors.
Fixed the Javascript demo. And looks way more fluffy. I think that your code:
int col=(int)(image[x+(y*newimage.get_width())]+1)*255;
should actually be casting the value +1 to an integer and multiplying by 255. So -1, 0. Depending on whether it's positive or negative when the floor is called on the casting. Then +1 to 0 & 1. Then *255 to just white and black in almost equal proportions.
When I ported it to Java, I ran into an issue. And just recoded the normalization but I didn't double check that the normalization was bad in the Javascript.
Post a Comment