## Introduction

This article describes the theory behind, and how to implement, a basic fractal height map generator. It is based upon the algorithm defined at http://gameprogrammer.com/fractal.html. Height maps are used in many things: positioning software, graphical rendering, and procedural map generation. Given the right conditions, height maps can be used to create visually stunning images, and are frequently used with an alpha channel to simulate clouds.

All source code used in this article shall be made freely available, under a Creative Commons GPL Licence

The implementation which will be defined here outputs an array of numbers, which on the surface seems fairly mundane. However, with a bit of tweaking with VT100 colour codes, or passing to an image generation program, the algorithm can produce outputs such as this:

The ASCII renderer assigns a colour code to a range of numbers and then depending on your ranges, you can create rainbow-like maps like the one above. The grey scale and transparent images had their number arrays passed to an image generation program called RMagick.

## The Theory

I will go through the basic idea again as it was defined in the gameprogrammer link, to keep a consistency with terms used further in the article. So before we get on to the DiamondSquare algorithm, I shall implement the simpler 1 dimensional algorithm, which will describe the height of a line, similar to a horizon. The patterns created show some fractal behaviour, in that it is said to be *self-similar*. An object is said to be *self-similar* when magnified subsets of the object look like, or are identical to, the whole and to each other[1].

In context of this algorithm, it means that as we add more detail, the more rougher and major features will still hold true, but more detail will become apparent as we look closer. This makes the algorithm ideal for recursion or iterative methods. This implementation uses an iterative method.

### Midpoint Displacement in One Dimension

For the creation of the 1 dimensional height map, similar to a horizon, a very simple algorithm is used:

def generateLine(length) # Due to this algorithm being simple for # the articles sake, length should be # constrained to the powers of 2. # # As we need a midpoint, however, length # should be defined as (2^n)+1. # Create an array which describes a line. # Set the default values to 0American Standard Code for Information Interchange line = Array.new(length, 0) # Define the range of the terrain values. # For this example we shall take the range # of values to be -63 to 63, with the midpoint # at 0, out default value. # Range is then 128. range = 128; # Work out the number of line segments # levels there are in the line. As each line # segment level is defined by deviding by two # until length is 1, the number of segments # is the log_2 of the length. noSegments = Math.log(length-1, 2) #Iterate through the levels (1 .. noSegments).each{ |level| # Work out the line segment length so you # can properly address the offset. segLength = (length/2**level) # Work out the number of line segments # within this level noSegL = (2**level)-1 # Iterate through the line segments and # apply your random function. (1 .. noSegL).each{ |segOffset| # If value is not zero, skip over it, done on a previous # level if( line[segLength*segOffset] == 0 ) # Make sure the current value of the line # is directly midway between its two parents. line[segLength*segOffset] = (line[segLength*(segOffset-1)] + line[segLength*(segOffset+1)])/2 # Apply random function to value line[segLength*segOffset] = randomFunction(line[segLength*segOffset], level, range) end } } return line end

Now as you can see the most important part of that algorithm is that which I have purposely missed, *randomFunction*. This is where you, quite obviously, define how you want your heights defined. A good way is to simply use a bounded random function, where the bounds are defined by the line segment level you are currently within. For example, a function like: ` `

def randomFunction(value, level, range) # Roughness constant 0 < h < 1 # As h approachs 0, the level dependent # bounds grow and tend to 1 for all values # of level h = 0.8 # Define bounds in terms of level and a roughness # function multiplier = 2 ** (-h * level-1) # Perform random function, bound it, and then apply # multiplier value += (rand() * (range) - (range / 2)) * multiplier # Return return value end

` `

Would offset the value of the line a random amount which is bounded by a function dependent on the line segment level and a roughness coefficient. As this function is the heart of this algorithm and the 2 dimensional algorithm, I will go into some detail on the use of the roughness coefficient. If the roughness coefficient is set to 1, then the multiplier acts the same as : . This gives us the gaseous image that has been generated above.

## Code Listings

A library version of the ruby code found in this tutorial can be found at GitHub.

## References

- Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987

Ruby Diamond Square Height Map Generator by Mr Carl Ellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.

Based on a work at gameprogrammer.com.