Bugfree.dk – Ronnie Holm's blog

In Generating 2D random fractal terrains with C# I implemented 1D midpoint displacement in an imperative language. Since I’m currently making my way through Robert Pickering‘s Foundations of F#, in this post I want to redo it in F#.

The first step along the way is the maxDisplacements function that, given a number of splits of line segments, returns a list of maximum displacements. Here list comprehension comes in handy as a way to generate maximum displacements where the next is half of that of the previous, starting with 0.5:

    let maxDisplacements n = [for i in 1 .. n -> 2.0**(float)(-i)]

Next is the composeCoordinates function whose job it is to infer the x coordinates from the y coordinates. When splitting line segments, as defined later by the split function, only y coordinates need to be dealt with. But for displaying the result as a list of points, e.g., as input to a graphing program, composeCoordinates generates the (x, y) coordinate pairs given a list of y coordinates. Again list comprehension is used to uniformly distribute the x coordinates in the range 0 to 1. Next, the x and y coordinates are fused using the build-in zip function, i.e., [x1; x2] and [y1; y2] become [(x1, y1); (x2, y2)].

    let composeCoordinates (ys : list<float>) =
        let dx = 1.0 / (float)(ys.Length - 1)
        let xs = [for x in 0 .. ys.Length - 1 -> (float)x * dx]
        List.zip xs ys

Now for the crux of the fractal generation process: the split function. As is customary with functional languages, looping is done using recursion and split is no exception. Passing in a list of y coordinates, a maximum displacement as generated by maxDisplacements, and a random number generator, split is defined as:

    let rec split (ys : list<float>) displacement (random : Random) =
        match ys with
        | a :: b :: tail ->
            let m = b - a / 2.0
            let r = random.NextDouble() * displacement
            a :: a + m + r :: split (b :: tail) displacement random
        | a -> a

Using pattern matching, an if-then-else construct on steroids, split examines its input of y coordinates to determine if the inductive or the base case of the recursive implementation needs to be invoked. The first pattern matches a list starting with elements a and b following by zero or more elements. In case this pattern matches, a new list is returned. It’s composed of the original a element, a new displaced element, the original b element, and split applied to the original list with its first element removed. Removing one element at a time, at some point only one element is left in the list in which case the base case is invoked. When this happens, all the original line segments have been split in two.

Finally, the main function ties together the previous ones. Given an initial line segment, the number of times to apply split to it, and a random number generator, the actual splitting is done using the build-in fold_left function. fold_left is an example of fun with folds and a function that is itself recursively defined to make looping implicit.

    let main() =
        let initial = [0.0; 0.0]
        let splits = 8
        let r = new Random()
        let ys = List.fold_left (fun s d -> split s d r) initial (maxDisplacements splits)
        print_any (composeCoordinates ys)

While initially hard to grog, the use of fold_left becomes clearer when applied to a list of integers to compute their product. Of the three arguments to fold_left the first is a function defined by a lambda expression (here the predefined multiplication operator is also applicable but less explicit). The second argument is the initial value of an accumulator. And finally, the third argument is the list to work on.

    List.fold_left (fun x y -> x * y) 1 [1;2;3]
    List.fold_left (*) 1 [1;2;3]

What fold_left does is recursively call itself passing along the first argument as is. The second argument is the new value of the accumulator, computed by passing to the function of the first argument the original value of the accumulator and the first element of the list. That way it’s up to the function passed as the first argument to decide what operation to apply to the elements in the list. The third argument is the original list with the first element removed. The recursive chain of calls with their arguments then takes on this form:

    List.fold_left (fun 1 1 -> 1 * 1) 1 [1;2;3]
    List.fold_left (fun 1 2 -> 1 * 2) 1 [2;3]
    List.fold_left (fun 2 3 -> 2 * 3) 2 [3]

Within the main function the first argument to fold_left is a lambda expression that applies the split function to a list. The second argument, the accumulator, isn’t a scalar like with the product example, but a list of line segments to be passed to split. Finally, the third argument is the maximum displacement list. And so for the original line segment to be split n times, n maximum displacements must be provided by the maxDisplacements function.

Back in 1999, when I was learning C++ and MFC, I remember spending a great deal of time writing an application that displayed the Mandelbrot set, probably the most famous of all fractals. And when I learned Remote Procedure Call, I even converted the application into a distributed Mandelbrot generator (which made sense given the CPU speed of the time).

What’s so fascinating about the Mandelbrot set, and other fractals, is that the often simple equations that define them are able to give birth to such complex creations.

In general, a fractal is defined as:

“[…] ‘a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole,’ a property called self-similarity. A fractal often has the following features: it has a fine structure at arbitrarily small scales; it is too irregular to be easily described in traditional Euclidean geometric language; it is self-similar (at least approximately or stochastically); [… and] it has a simple and recursive definition. […] Natural objects that approximate fractals to a degree include clouds, mountain ranges, lightning bolts, coastlines, and snowflakes.”

The Mandelbrot set is an example of a fractal whose definition contains no stochastic element, i.e., the fractal looks the same every time it’s generated. Recently, though, I came across a simple algorithm that claimed to generate fractal terrains by adding randomness to the equation. So, given my history with fractals, I wanted to play with the algorithm that’s based on progressive refinement through midpoint displacement in one dimension:

    Start with a single horizontal line segment
    Repeat for a sufficiently large number of times
        Repeat over each line segment
            Find the midpoint of the line segment
            Displace the midpoint in y by a random amount
        Reduce the range for random numbers

Here’s my implementation of the algorithm in C#:

    class Program {
        static void Main() {
            var ys = new List<double>(new double[] { 0.0, 0.0 } );
            double displacement = 1.0;
            Random random = new Random();

            for (int i = 0; i < 8; i++)
                ys = Split(ys, displacement *= 0.5, random);
            ComposeCoordinatePairs(ys);
        }

        static List<double> Split(List<double> ys, double displacement, Random random) {
            if (ys.Count < 2)
                throw new ArgumentException(">= 2 coordinates required");
            var r = new List<double>();
            for (int i = 0; i < ys.Count - 1; i++) {
                double dy = (ys[i + 1] - ys[i]) / 2.0;
                double d = random.NextDouble() * displacement;
                r.Add(ys[i]);
                r.Add(ys[i] + dy + d);
            }
            r.Add(ys.Last());
            return r;
        }

        static void ComposeCoordinatePairs(List<double> ys) {
            double dx = 1.0 / (ys.Count - 1);
            for (int i = 0; i < ys.Count; i++)
                Console.WriteLine("{0:0.000} {1:0.000}", i * dx, ys[i]);
        }

Splitting line segments, the C# code doesn't store the x-component of the coordinate pairs because it can be inferred from the number of y-components and the fact that x-components go from 0 to 1, both inclusive. Hence, starting with the line segment (0,0)-(1,0), the code splits it by calling the Split method passing in a list of y-components of the line segment. After the first iteration the single line segment becomes two, then four, then eight, and so on until the line segments have undergone eight iterations of splitting. Generally, after the i'th iteration the number of line segments is 2^i and so after eight iterations we end with 256 line segments.

As prescribed by the algorithm, merely splitting line segments doesn’t give rise to a mountain. The mountain emerges because each time a line segment is split in two, a random displacement is added to the y-component at the center of the line segment. Assigning an upper limit to the maximum displacement within an iteration is what defines the roughness of the generated terrain. For the above implementation, the maximum displacement is defined as half of that of the previous iteration starting with 0.5. Thus, the first couple of iterations roughly define the terrain and additional iterations fill in the details.

In animated form the transformations from two to 256 line segments looks like so:

Among the practical applications of such a random fractal terrain generator are computer games. Not necessarily for generating 2D ridgelines, but for generating entire 3D terrains or even clouds. It works by generalizing 1D midpoint displacement to 2D in the form of the diamond-square algorithm. Then a cloud, for instance, can be derived from the 3D terrain by applying a height map to it; a height map in which different heights get assigned different colors.

I was watching the interview with Brian Beckman on real time physics simulation in games over at Channel 9. In the video Brian explains the challenges involved in creating an accurate, real time physics model in games, specifically for flight simulators and race car games. Although the math is quite involved, Brian does a superb job of transforming the material into something digestible and fascinating.

In summary, Moore’s law enables game designers to use real time physics in games to accurately simulate something as complicated as a race car. Simulating an airplane has been possible for well over twenty years, but that’s only because the airplane moves smoothly through the air and is composed of simple components, such as a wing and a fuselage, which translates into few and simple equations to solve for each frame.

A race car, on the other hand, has four wheels touching the ground and connected to the car through some kind of suspension. Hence each wheel has to be accounted for independently. In addition, the clutch, gear box, and aerodynamics of the car, not to mention the terrain, have a profound impact on the physics model, calling for a more involved set of equations to solve.

As computes have become fast enough to match the frame rate given this challenging set of equations, race car games have become as realistic as flight simulators. With more horsepower, however, comes a need for even more realism. So even though computers become faster/fatter at an exponential rate, simplifying the model is, and probably always will be, worth striving for.

This is where Rigs of Rods enters the video at time index 00:56:10. The game takes the opposite approach of using advanced equations, with the risk of introducing divergence or singularities into the model when, say, the denominator of a fraction approaches zero. Instead the game uses simple/simpler equations, such as harmonic oscillators, as a mean of modeling airplanes, cars, trucks, etc. using sticks and stones (or rigs of rods, hence the name).


The sticks and stones approach works by assigning mass to the stones and connecting them using the sticks, and then adding textures on top. This more general, but also more computationally intensive, model creates a very realistic experience.

I’ve been playing the game for a couple of days now, and although it initially appears simple it’s surprisingly entertaining. A lot of time goes into exploring the scenery using the various modes of transportation.