Fractals

Introduction

There are many interesting applications for noise and fractals in RL games, not just for terrain generation, but for adding natural-feeling patterns to monster behavior, treasure drops, and many other features.

In this article I will give a brief overview of fractals and how they can be implemented in RL games. There is also some code available and a set of references for further study.

Midpoint Displacement

The easiest way to generate fracta-like behavior is to use midpoint displacement.

Midpoint displacement takes a straight line and turns it into a ragged line that can look like the outline of a mountain range. The resulting fractal has a dimension between 1 and 2. Start with a straight line between points A and B. Create the midpoint, M, half way between A and B. Then displace the midpoint up or down by a random value. This creates two new lines joined at the midpoint. We then repeat this displacement algorithm recursively for each new line segment. At each step, we also adjust the amplitude of the displacement by some method. One usually reduces it by an exponential function.

The result of this process resembles jagged terrain. However it is fairly homogenous and isotropic. It tends to look fake to the eye. You can search online for examples of this terrain.

Midpoint displacement can be done in higher dimensions as well, but the process gets more and more complex. For 2D terrain, which is useful for RL terrain generation, we need to displace the midpoint of a square and partition the square into four smaller ones, which are then recursively displaced. The algorithm is know as Diamond-Square, referring to the two steps of displacement then partitioning.

Here is rough pseudo-code for the midpoint displacement algorithm in 1D.

void midpoint(VECTOR a, b, float scale)
{
 VECTOR m, d;
 float amount;
 .
 // Find the midpoint
 m = (a   b) / 2;
 .
 // This is the displacement direction.
 // We are displacing along the y axis.
 d.assign(0, 1, 0);
 .
 // Find the amount to displace.
 // We start with a random number -1..1
 amount = rand(-1, 1);
 .
 // We now scale by the current scale amount
 amount *= scale;
 .
 // We now update our scale amount.  If we left the
 // scale unchanged, we'd end up with increasingly
 // spiky line.
 // Because we cut the length of the line in half with
 // every iteration, multiplying the scale by .5 will
 // maintain the same "spikiness" at all levels.  A value
 // less than .5 will cause things to quickly smooth out.
 scale *= 0.5;
 .
 // And do the displacement.
 m  = d * amount;
 .
 // Now, create