Fractal Terrain Generation

The original idea behind the generation was in Computer Rendering of Stochastic Models, in the June 1982 issue of  Communications of the ACM.  I’m basing my code on Paul Mertz’s Generating Random Fractal Terrain.

The gist of what I’m doing is to start with a square, like this (I’ve added a grid to make it easier to see the elements):

Our map

From here, we determine the corners:

Four corners

Each location in the grid has a “height”. In my implementation, I assign it a value from (-1 .. 1). From these four points we find the center point, then average the values of the 4 corners and add to it some random value.

The center point

This random value, h is in a range of (-1 .. 1). So if the 4 corners all had a value of 0, and our random value was .5, then the center would be .5:

From here we determine the midpoints on the sides of the square:

Midpoints

Notice that where we once had one (1) square, we now have 4 smaller squares.  From here, we do each square in turn in the same fashion.  However, this time the range of h has been halved — the range can be tweaked.  If you use the formula 2^(-n), to make the terrain smoother, use a n closer to 1.  Likewise, the smaller n is, the more random the terrain.

The smaller squares are each processed, yielding smaller squares.

Finally, you have a grid of values, which range from -1 < n < 1.  From this terrain, you could then assign ranges, such as n <= -.5  for water, -.5 < n <= -.3 for swamps, -.1 < n <= .2 for plains, snd so forth.  From that you could then have something like this (tiles are  from Wesnoth):

Sample Terrain

If anyone’s interested, I can post sample code.