Fractal Skymap Generator

[cavetroll]

This is just a simple program that generates fractal skymaps. It is based on the Diamond-Square algorithm. I am sending in a similar program with my Shad Valley application. Although the one I am using for Shad Valley in python, I feel that this program gives slightly better results.

The algorithm can be also be used to generate height maps.

Changing the size constant to increases the size of the generated map (Make sure to change the setscreen line as well).
Changing the roughness value will generate more or less wispy terrain (I recommend a value between .55 and .75).

Turing:

setscreen ("graphics:512,512") const size := 2 ** 9 const roughness := .7 var grid : array 0 .. size, 0 .. size of real var add1, add2, add3, add4, average, clr, mx, mn : real := 0.0 var n : int := 0 for i : 0 .. size     for t : 0 .. size         grid (i, t) := 0     end for end for grid (0, 0) := (Rand.Real-.5)*roughness grid (size, 0) := (Rand.Real-.5)*roughness grid (0, size) := (Rand.Real-.5)*roughness grid (size, size) := (Rand.Real-.5)*roughness for decreasing p : round (ln (size) / ln (2)) .. 0     n += 1     for x : 0 .. size by 2 ** p         for y : 0 .. size by 2 ** p             if x mod 2 ** (p + 1) = 0 and y mod 2 ** (p + 1) = 0                     or y + 2 ** p > size or y - 2 ** p < 0 then             else                 if x mod 2 ** (p + 1) = 0 then                     average := (grid (x, y + 2 ** p) + grid (x, y - 2 ** p)) / 2                     clr := average + roughness ** n * (Rand.Real - .5)                 end if                 if y mod 2 ** (p + 1) = 0 then                     average := (grid (x + 2 ** p, y) + grid (x - 2 ** p, y)) / 2                     clr := average + roughness ** n * (Rand.Real - .5)                 end if                 if x mod 2 ** (p + 1) >= 0 and y mod 2 ** (p + 1) >= 0 and clr = 0 then                     add1 := grid (x + 2 ** p, y + 2 ** p)                     add2 := grid (x + 2 ** p, y - 2 ** p)                     add3 := grid (x - 2 ** p, y + 2 ** p)                     add4 := grid (x - 2 ** p, y - 2 ** p)                     average := (add1 + add2 + add3 + add4) / 4                     clr := average + roughness ** n * (Rand.Real - .5)                 end if                 grid (x, y) := clr                 mx := max (grid (x, y), mx)                 mn := min (grid (x, y), mn)             end if             clr := 0         end for     end for end for for x : 0 .. size     for y : 0 .. size         grid (x, y) := ((grid (x, y) - mn) / (mx - mn))         drawdot (x, y, RGB.AddColor (grid (x, y), grid (x, y), 1))     end for end for

[Parker]

Wow thats very nice. I have no clue how to do that so I cannot give any accurate critizism (or however that is spelled) but it looks pretty good

[md]

care to post a screenshot so those of us who lack turing can see the output?

[Tony]

cavetroll @ Mon Dec 08, 2008 4:41 pm wrote:

Make sure to change the setscreen line as well

The point of using constants is so that one doesn't have to do things like that. Instead, use something like this:

Turing:

const size := 2 ** 9 setscreen ("graphics:" + intstr(size) + "," + intstr(size))

[SNIPERDUDE]

That is actually pretty awesome. I think I'm going to use something like this for my next game...

Awesome job.

[gitoxa]

Sky 1
Sky 2
Sky 3
Sky 4 (Big)

This thing is pretty sweet

[cavetroll]

Tony @ Tue Dec 09, 2008 1:00 pm wrote:

cavetroll @ Mon Dec 08, 2008 4:41 pm wrote:

Make sure to change the setscreen line as well

The point of using constants is so that one doesn't have to do things like that. Instead, use something like this:

Turing:

const size := 2 ** 9 setscreen ("graphics:" + intstr(size) + "," + intstr(size))

Ah, you're right. I hadn't though of doing something like that, it would work better. Thanks for the advice, I'll remember to include it in later programs.

[Tyr_God_Of_War]

Amazing. I wish I understood how you did that.

[S_Grimm]

@md. Felt Sorry for you.

http://i383.photobucket.com/albums/oo272/Allthatfails/Output.jpg

or

[md]

Sweet, that's kinda cool!

/me goes back to ignoring turing

[kelvinc2]

masterpiece of turing..

can you explain the concept on how to do this?

*i'm observing right now*

[A.J]

nice fractal generator!

the next step for you would be to generate a scenery with the sky (i.e. make other fractal generators to generate trees, grass, etc...)

Well Done!

[cavetroll]

Well, several people have expressed interest in how it works, so here's a basic description.

The first few lines are pretty easy to understand, but I will explain them anyway.

Turing:

const size := 2 ** 9 setscreen ("graphics:" + intstr(size) + "," + intstr(size)) const roughness := .7 var grid : array 0 .. size, 0 .. size of real var add1, add2, add3, add4, average, clr, mx, mn : real := 0.0 var n : int := 0 for i : 0 .. size     for t : 0 .. size         grid (i, t) := 0     end for end for

Size represents the size of the picture to generate (must be a power of 2).
The setscreen line just changes the size of the window (Thanks to Tony for the advice).
Roughness specifies how much the variation for each point. As specified above, looks best between .55 and .75
Grid just stores each height value.
The for loops initialize each height at zero.

Turing:

grid (0, 0) := (Rand.Real-.5)*roughness grid (size, 0) := (Rand.Real-.5)*roughness grid (0, size) := (Rand.Real-.5)*roughness grid (size, size) := (Rand.Real-.5)*roughness

Initializes each corner value with a random value.

Turing:

for decreasing p : round (ln (size) / ln (2)) .. 0     n += 1     for x : 0 .. size by 2 ** p         for y : 0 .. size by 2 ** p             if x mod 2 ** (p + 1) = 0 and y mod 2 ** (p + 1) = 0                     or y + 2 ** p > size or y - 2 ** p < 0 then             else

The for loop finds out x in 2^x=size and then iterates from that value to zero.
The second two for loops iterate from 0 to the size of the picture by the each value of p from the first loop.
The if just makes sure that any value that is going to be accessed within the loop is valid for our calculations.

Turing:

if x mod 2 ** (p + 1) = 0 then                     average := (grid (x, y + 2 ** p) + grid (x, y - 2 ** p)) / 2                     clr := average + roughness ** n * (Rand.Real - .5)                 end if                 if y mod 2 ** (p + 1) = 0 then                     average := (grid (x + 2 ** p, y) + grid (x - 2 ** p, y)) / 2                     clr := average + roughness ** n * (Rand.Real - .5)                 end if

These two if's are used to check whether it is valid to perform a diamond step. Then the two surrounding points are averaged and then have a random value added to the average.

Turing:

if x mod 2 ** (p + 1) >= 0 and y mod 2 ** (p + 1) >= 0 and clr = 0 then                     add1 := grid (x + 2 ** p, y + 2 ** p)                     add2 := grid (x + 2 ** p, y - 2 ** p)                     add3 := grid (x - 2 ** p, y + 2 ** p)                     add4 := grid (x - 2 ** p, y - 2 ** p)                     average := (add1 + add2 + add3 + add4) / 4                     clr := average + roughness ** n * (Rand.Real - .5)                 end if                 grid (x, y) := clr                 mx := max (grid (x, y), mx)                 mn := min (grid (x, y), mn)             end if

This sections checks if a square step is valid. The four corner values are then averaged plus a random value to set the height. Regardless of whether a square or diamond step is performed, the maximum and minimum values are kept track of.

Turing:

for x : 0 .. size     for y : 0 .. size         grid (x, y) := ((grid (x, y) - mn) / (mx - mn))         drawdot (x, y, RGB.AddColor (grid (x, y), grid (x, y), 1))     end for end for

This section of code is used to normalize and then draw the grid. The normalization works by subtracting the value by the minimum and then dividing by the range of values. This will result in a value between 0-1 for all points. This makes drawing easier because Turing's RGB colors are based off 0-1 instead of 0-255. (Although if Turing used 0-255 colors, you would just need to multiply each value by 255.
The drawing line is fairly simple. if all values are equal to 1, it will output white. if the height is 0, it will output blue. Anything in between will produce a shade of blue.


Now, to explain the mathematics behind the diamond and square steps I referenced above.

x mod 2**(p+1)=0 checks to see of the point being accessed would be valid in the previous iteration of the p loop. This also works for y. If both are equal to zero, this means the point has been accessed already, and so no value needs to be added. If it is only equal to zero on one, then a diamond step is performed. The diamond step works by averaging the surrounding points on the opposite axis. (i.e. if x mod 2**(p+1) = 0 then the point will be the average of the points above and below it, plus a small height addition.)

The square step finds values for all the points that don't fall evenly on valid points for the previous loop. Since it works with multiples of two, we know that it will be exactly half way between previous points, so if e add or subtract properly, we can find it's four corner heights. These values are then averaged and a small random value added to produce a height.

The algorithm works by repeating the diamond and square steps, over and over again till they get down to p=0. It starts with large values for points and works progressively smaller.


It's sorta late when I'm writing this, so there may be inconsistencies or weird grammar. If there is, I apologize in advance. If anything needs clarification, just ask and I will post a more descriptive explanation.