Chapter 8. Fractals

“Pathological monsters! cried the terrified mathematician

Once upon a time, I took a course in high school called “Geometry.” Perhaps you did too. You learned about shapes in one dimension, two dimensions, and maybe even three. What is the circumference of a circle? The area of a rectangle? The distance between a point and a line? Come to think of it, we’ve been studying geometry all along in this book, using vectors to describe the motion of bodies in Cartesian space. This sort of geometry is generally referred to as Euclidean geometry, after the Greek mathematician Euclid.

Figure 8.1

For us nature coders, we have to ask the question: Can we describe our world with Euclidean geometry? The LCD screen I’m staring at right now sure looks like a rectangle. And the plum I ate this morning is circular. But what if I were to look further, and consider the trees that line the street, the leaves that hang off those trees, the lightning from last night’s thunderstorm, the cauliflower I ate for dinner, the blood vessels in my body, and the mountains and coastlines that cover land beyond New York City? Most of the stuff you find in nature cannot be described by the idealized geometrical forms of Euclidean geometry. So if we want to start building computational designs with patterns beyond the simple shapes ellipse(), rect(), and line(), it’s time for us to learn about the concepts behind and techniques for simulating the geometry of nature: fractals.

8.1 What Is a Fractal?

The term fractal (from the Latin fractus, meaning “broken”) was coined by the mathematician Benoit Mandelbrot in 1975. In his seminal work “The Fractal Geometry of Nature,” he defines a fractal 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.”

Figure 8.2

One of the most well-known and recognizable fractal patterns is named for Benoit Mandelbrot himself. Generating the Mandelbrot set involves testing the properties of complex numbers after they are passed through an iterative function. Do they tend to infinity? Do they stay bounded? While a fascinating mathematical discussion, this “escape-time” algorithm is a less practical method for generating fractals than the recursive techniques we’ll examine in this chapter. However, an example for generating the Mandelbrot set is included in the code examples.

Let’s illustrate this definition with two simple examples. First, let’s think about a tree branching structure (for which we’ll write the code later):

Figure 8.3

Notice how the tree in Figure 8.3 has a single root with two branches connected at its end. Each one of those branches has two branches at its end and those branches have two branches and so on and so forth. What if we were to pluck one branch from the tree and examine it on its own?

Figure 8.4

Looking closely at a given section of the tree, we find that the shape of this branch resembles the tree itself. This is known as self-similarity; as Mandelbrot stated, each part is a “reduced-size copy of the whole.”

The above tree is perfectly symmetrical and the parts are, in fact, exact replicas of the whole. However, fractals do not have to be perfectly self-similar. Let’s take a look at a graph of the stock market (adapted from actual Apple stock data).

Figure 8.5: Graph A

And one more.

Figure 8.6: Graph B

In these graphs, the x-axis is time and the y-axis is the stock’s value. It’s not an accident that I omitted the labels, however. Graphs of stock market data are examples of fractals because they look the same at any scale. Are these graphs of the stock over one year? One day? One hour? There’s no way for you to know without a label. (Incidentally, graph A shows six months’ worth of data and graph B zooms into a tiny part of graph A, showing six hours.)

Figure 8.7

This is an example of a stochastic fractal, meaning that it is built out of probabilities and randomness. Unlike the deterministic tree-branching structure, it is statistically self-similar. As we go through the examples in this chapter, we will look at both deterministic and stochastic techniques for generating fractal patterns.

While self-similarity is a key trait of fractals, it’s important to realize that self-similarity alone does not make a fractal. After all, a line is self-similar. A line looks the same at any scale, and can be thought of as comprising lots of little lines. But it’s not a fractal. Fractals are characterized by having a fine structure at small scales (keep zooming into the stock market graph and you’ll continue to find fluctuations) and cannot be described with Euclidean geometry. If you can say “It’s a line!” then it’s not a fractal.

Another fundamental component of fractal geometry is recursion. Fractals all have a recursive definition. We’ll start with recursion before developing techniques and code examples for building fractal patterns in Unity.

8.2 Recursion

Let’s begin our discussion of recursion by examining the first appearance of fractals in modern mathematics. In 1883, German mathematician George Cantor developed simple rules to generate an infinite set:

Figure 8.8: The Cantor set

There is a feedback loop at work here. Take a single line and break it into two. Then return to those two lines and apply the same rule, breaking each line into two, and now we’re left with four. Then return to those four lines and apply the rule. Now you’ve got eight. This process is known as recursion: the repeated application of a rule to successive results. Cantor was interested in what happens when you apply these rules an infinite number of times. We, however, are working in a finite pixel space and can mostly ignore the questions and paradoxes that arise from infinite recursion. We will instead construct our code in such a way that we do not apply the rules forever (which would cause our program to freeze).

Before we implement the Cantor set, let’s take a look at what it means to have recursion in code. Here’s something we’re used to doing all the time—calling a function inside another function.

    //Calling the function Background() in the definition of SomeFunction()
    void SomeFunction() 
    {
        Background(0);
    }
    

What would happen if we called the function we are defining within the function itself? Can someFunction() call someFunction()?

    void SomeFunction() 
    {
        SomeFunction();
    }
    

In fact, this is not only allowed, but it’s quite common (and essential to how we will implement the Cantor set). Functions that call themselves are recursive and good for solving certain problems. For example, certain mathematical calculations are implemented recursively; the most common example is factorial.

The factorial of any number n, usually written as n!, is defined as:

n! = n * n – 1 * . . . . * 3 * 2 * 10! = 1

Here we’ll write a function in Unity that uses a for loop to calculate factorial:

    int Factorial(int n) 
    {
        int f = 1;
        for (int i = 0; i < n; i++) 
        {
            f = f * (i+1);
        }
        return f;
    }
    

Upon close examination, you’ll notice something interesting about how factorial works. Let’s look at 4! and 3!

4! = 4 * 3 * 2 * 13! = 3 * 2 * 1

therefore. . .

4! = 4 * 3!

In more general terms, for any positive integer n:

n! = n * (n-1)!1! = 1

Written out:

The factorial of n is defined as n times the factorial of n-1.

The definition of factorial includes factorial?! It’s kind of like defining “tired" as “the feeling you get when you are tired.” This concept of self-reference in functions is an example of recursion. And we can use it to write a factorial function that calls itself.

    int factorial(int n) 
    {
        if (n == 1) 
        {
            return 1;
        } 
        else 
        {
            return n * factorial(n-1);
        }
    }
    

It may look crazy, but it works. Here are the steps that happen when factorial(4) is called.

Figure 8.9

We can apply the same principle to graphics with interesting results, as we will see in many examples throughout this chapter. Take a look at this recursive function.

• Code
• Demo

DrawCircle() draws an ellipse based on a set of parameters that it receives as arguments. It then calls itself with those same parameters, adjusting them slightly. The result is a series of circles, each of which is drawn inside the previous circle.

Notice that the above function only recursively calls itself if the radius is greater than 2. This is a crucial point. As with iteration, all recursive functions must have an exit condition! You likely are already aware that all for and while loops must include a boolean expression that eventually evaluates to false, thus exiting the loop. Without one, the program would crash, caught inside of an infinite loop. The same can be said about recursion. If a recursive function calls itself forever and ever, you’ll be most likely be treated to a nice frozen screen.

This circles example is rather trivial; it could easily be achieved through simple iteration. However, for scenarios in which a function calls itself more than once, recursion becomes wonderfully elegant.

Let’s make DrawCircle() a bit more complex. For every circle displayed, draw a circle half its size to the left and right of that circle.

Example 8.2: Recursion twice

• Code
• Demo

With just a little more code, we could also add a circle above and below each circle.

Example 8.3: Recursion four times

• Code
• Demo

Try reproducing this scene with iteration instead of recursion—I dare you!

8.3 The Cantor Set with a Recursive Function

Now we’re ready to visualize the Cantor set in Unity using a recursive function. Where do we begin? Well, we know that the Cantor set begins with a line. So let’s start there and write a function that draws a line.

    void Cantor(float x, float y, float len)
    {
        line(x, y, x + len, y); // Create the first line
    }
    

The above cantor() function draws a line that starts at pixel coordinate (x,y) with a length of len. (The line is drawn horizontally here, but this is an arbitrary decision.) So if we called that function, saying:

    cantor(minPos.x + 3, maxPos.y - 2, (maxPos.x - minPos.x) - 6);
    

Figure 8.10

Figure 8.11

Now, the Cantor rule tells us to erase the middle third of that line, which leaves us with two lines, one from the beginning of the line to the one-third mark, and one from the two-thirds mark to the end of the line.

We can now add two more lines of code to draw the second pair of lines, moving the y-location down a bunch of pixels so that we can see the result below the original line.

    void Cantor(float x, float y, float len)
    {
        Line(x, y, x + len, y); // Create the first line

        if (len >= 0.01f) // Stop at 0.01 meters length!
        {
            y -= 2;

            Line(x, y, len / 3);
            Line(x + len * 2 / 3, y, len / 3);
        }
    }
    

Figure 8.12

While this is a fine start, such a manual approach of calling line() for each line is not what we want. It will get unwieldy very quickly, as we’d need four, then eight, then sixteen calls to line(). Yes, a for loop is our usual way around such a problem, but give that a try and you’ll see that working out the math for each iteration quickly proves inordinately complicated. Here is where recursion comes and rescues us.

Take a look at where we draw that first line from the start to the one-third mark.

    Line(x, y, x + len/3, y); // Create the first line
    

Instead of calling the line() function directly, we can simply call the cantor() function itself. After all, what does the cantor() function do? It draws a line at an (x,y) location with a given length! And so:

    Line(x,y,x+len/3,y);         becomes ------->  Cantor(x,y,len/3);
    

And for the second line:

    Line(x+len*2/3,y,x+len,y);   becomes ------->  Cantor(x+len*2/3,y,len/3);
    

Leaving us with:

    void Cantor(float x, float y, float len)
    {
        line(x, y, x + len, y); // Create the first line

        if (len >= 0.01f) // Stop at 0.01 meters length!
        {
            y -= 2;

            Cantor(x, y, len / 3); // Call the function recursively
            Cantor(x + len * 2 / 3, y, len / 3); // We need two lines for each line above it
        }
    }
    

And since the Cantor() function is called recursively, the same rule will be applied to the next lines and to the next and to the next as Cantor() calls itself again and again! Now, don’t go and run this code yet. We’re missing that crucial element: an exit condition. We’ll want to make sure we stop at some point—for example, if the length of the line ever is less than 1 pixel.

Example 8.4: Cantor set

• Code
• Demo

8.4 The Koch Curve and the List Technique

Writing a function that recursively calls itself is one technique for generating a fractal pattern on screen. However, what if you wanted the lines in the above Cantor set to exist as individual objects that could be moved independently? The recursive function is simple and elegant, but it does not allow you to do much besides simply generating the pattern itself. However, there is another way we can apply recursion in combination with a List that will allow us to not only generate a fractal pattern, but keep track of all its individual parts as objects.

To demonstrate this technique, let’s look at another famous fractal pattern, discovered in 1904 by Swedish mathematician Helge von Koch. Here are the rules. (Note that it starts the same way as the Cantor set, with a single line.)

Figure 8.13

The result looks like:

Figure 8.14

We could proceed in the same manner as we did with the Cantor set, and write a recursive function that iteratively applies the Koch rules over and over. Nevertheless, we are going to tackle this problem in a different manner by treating each segment of the Koch curve as an individual object. This will open up some design possibilities. For example, if each segment is an object, we could allow each segment to move independently from its original location and participate in a physics simulation. In addition, we could use a random color, line thickness, etc. to display each segment differently.

In order to accomplish our goal of treating each segment as an individual object, we must first decide what this object should be in the first place. What data should it store? What functions should it have?

The Koch curve is a series of connected lines, and so we will think of each segment as a “KochLine.” Each KochLine object has a start point (“a”) and an end point (“b”). These points are PVector objects, and the line is drawn with Unity’s line() function.

    void Start()
    {
        FindWindowLimits();

        points = new List<vector2>(); // Our List of points that will make up our line

        points.Add(new Vector2(minPos.x, minPos.y + 1f)); // Left side of window
        points.Add(new Vector2(maxPos.x, minPos.y + 1f)); // Right side of window

        for (int i = 0; i < 5; i++)
        {
            Generate(); // We want to expand our points 5 times!
        }

        KochLine = Line(points); // We then show the line by passing the points into a LineRenderer
    }

    void Generate()
    {
        if (KochLine != null)  // We're going to replace the line!
        {
            Destroy(KochLine);
        }

        List<vector2> newPoints = new List<vector2>();

        for (int i = 0; i < points.Count - 1; i++) // We're going to use 2 points each time to make a line
        {
            Vector2 v = points[i+1] - points[i]; // This gives up the length of the line in 2 dimentions
            v = v / 3; // We only need 1/3rd of it since the line is split into thirds

            // First we need to define each new point from the original points in the line

            Vector2 a = points[i]; // This is the first point in the original line
            Vector2 b = v + a;  // 1/3rd after point A is where point B lies
            Vector2 c = Rotate(v, 60) + b; // Point C is 60 Degrees up from point B
            Vector2 d = (v * 2f) + a; // 2/3rds after point A is where point D lies
            Vector2 e = points[i+1]; // This is the last point in the original line

            // Now we add those points, in order, to our newPoint list

            newPoints.Add(a);
            newPoints.Add(b);
            newPoints.Add(c);
            newPoints.Add(d);
            newPoints.Add(e);
        }

        // After each line is added, we redefine the original points with the newPoints
        points = newPoints;
    }
    

Now that we have our KochLine method in our Chapter8 Figure 5 class, we can get started on the main program. We’ll need a data structure to keep track of what will eventually become many KochLine objects, and a List (see Chapter 4 for a review of Lists) will do just fine.

    List<vector2> points;
    

In start(), we’ll want to create the List and add the first line segment to it, a line that stretches from 0 to the width of the scene.

    points = new List<vector2>(); // Our List of points that will make up our line

    points.Add(new Vector2(minPos.x, minPos.y + 1f)); // Left side of window
    points.Add(new Vector2(maxPos.x, minPos.y + 1f)); // Right side of window
    

Then in line(), all the KochLine object will be created (just one right now).

    void Start()
    {
        FindWindowLimits();

        points = new List<vector2>(); // Our List of points that will make up our line

        points.Add(new Vector2(minPos.x, minPos.y + 1f)); // Left side of window
        points.Add(new Vector2(maxPos.x, minPos.y + 1f)); // Right side of window

        for (int i = 0; i < 5; i++)
        {
            Generate(); // We want to expand our points 5 times!
        }

        KochLine = Line(points); // We then show the line by passing the points into a LineRenderer
    }

    private GameObject Line(List<vector2> linePoints)
    {
        // We first generate a new object and give it a LineRenderer like in 8.4
        GameObject obj = new GameObject();
        obj.name = "Line";
        LineRenderer line = obj.AddComponent<linerenderer>();

        // We give it a material and a color so we can see it
        line.material = new Material(Shader.Find("Sprites/Default"));
        line.startColor = line.endColor = Color.black;

        // Let's give it a small width so we can see the complexity of the curve
        line.widthMultiplier = .01f;

        // We have to tell the LineRenderer to expect as many points as we have before we assign them
        line.positionCount = linePoints.Count;

        // We then can loop through those empty points and give them values
        int index = 0;
        foreach (Vector2 point in linePoints) 
        {
            line.SetPosition(index, new Vector3(point.x, point.y, 0));
            index++;
        }

        return obj;
    }
    

This is our foundation. Let’s review what we have so far:

• KochLine GameObject: A GameObject to keep track of a line from point A to B.
• >
• List: A list of all KochLine points.

With the above elements, how and where do we apply Koch rules and principles of recursion?

Remember the Game of Life cellular automata? In that simulation, we always kept track of two generations: current and next. When we were finished computing the next generation, next became current and we moved on to computing the new next generation. We are going to apply a similar technique here. We have a List that keeps track of the current set of KochLine objects (at the start of the program, there is only one). We will need a second List (let’s call it “next”) where we will place all the new KochLine objects that are generated from applying the Koch rules. For every KochLine object in the current List, four new KochLine objects are added to the next List. When we’re done, the next List becomes the current one.

Figure 8.15

Here’s how the code will look:

    void Generate()
    {
        if (KochLine != null)  // We're going to replace the line!
        {
            Destroy(KochLine);
        }

        List<vector2> newPoints = new List<vector2>();

        for (int i = 0; i < points.Count - 1; i++) // We're going to use 2 points each time to make a line
        {
            newPoints.Add(?????);
            newPoints.Add(?????);
            newPoints.Add(?????);
            newPoints.Add(?????);
            newPoints.Add(?????);
        }

        // After each line is added, we redefine the original points with the newPoints
        points = newPoints;
    }
    

By calling Generate() over and over again (for example, each time the mouse is pressed), we recursively apply the Koch curve rules to the existing set of KochLine objects. Of course, the above omits the real “work” here, which is figuring out those rules. How do we break one line segment into four as described by the rules? While this can be accomplished with some simple arithmetic and trigonometry, since our KochLine object uses PVector, this is a nice opportunity for us to practice our vector math. Let’s establish how many points we need to compute for each KochLine object.

Figure 8.16

As you can see from the above figure, we need five points (a, b, c, d, and e) to generate the new KochLine objects.

    newPoints.Add(a);
    newPoints.Add(b);
    newPoints.Add(c);
    newPoints.Add(d);
    newPoints.Add(e);
    

Where do we get these points? Since we have a KochLine object, why not ask the KochLine object to compute all these points for us?

    void Generate()
    {
        if (KochLine != null)  // We're going to replace the line!
        {
            Destroy(KochLine);
        }

        List<vector2> newPoints = new List<vector2>();

        for (int i = 0; i < points.Count - 1; i++) // We're going to use 2 points each time to make a line
        {
            Vector2 v = points[i+1] - points[i]; // This gives up the length of the line in 2 dimentions
            v = v / 3; // We only need 1/3rd of it since the line is split into thirds

            // First we need to define each new point from the original points in the line
            Vector2 a = points[i]; // This is the first point in the original line
            Vector2 b = v + a;  // 1/3rd after point A is where point B lies
            Vector2 c = Rotate(v, 60) + b; // Point C is 60 Degrees up from point B
            Vector2 d = (v * 2f) + a; // 2/3rds after point A is where point D lies
            Vector2 e = points[i+1]; // This is the last point in the original line

            // Now we add those points, in order, to our newPoint list
            newPoints.Add(a);
            newPoints.Add(b);
            newPoints.Add(c);
            newPoints.Add(d);
            newPoints.Add(e);
        }

        // After each line is added, we redefine the original points with the newPoints
        points = newPoints;
    }
    

Figure 8.17

The last point, C, is the most difficult one to find. However, if you recall that the angles of an equilateral triangle are all sixty degrees, this makes it a little bit easier. If we know how to find point B with a PVector one-third the length of the line, what if we were to rotate that same PVector sixty degrees and move along that vector from point B? We’d be at point C!

Figure 8.18

• Code
• Demo

Exercise 8.2

Draw the Koch snowflake (or some other variation of the Koch curve).

Exercise 8.5

Draw the Sierpiński triangle (as seen in Wolfram elementary CA) using recursion.

8.5 Trees

The fractals we have examined in this chapter so far are deterministic, meaning they have no randomness and will always produce the identical outcome each time they are run. They are excellent demonstrations of classic fractals and the programming techniques behind drawing them, but are too precise to feel natural. In this next part of the chapter, I want to examine some techniques behind generating a stochastic (or non-deterministic) fractal. The example we’ll use is a branching tree. Let’s first walk through the steps to create a deterministic version. Here are our production rules:

Figure 8.19

Again, we have a nice fractal with a recursive definition: A branch is a line with two branches connected to it.

The part that is a bit more difficult than our previous fractals lies in the use of the word rotate in the fractal’s rules. Each new branch must rotate relative to the previous branch, which is rotated relative to all its previous branches.

Let’s begin by drawing a single branch, the trunk of the tree. This is as simple as setting a particular transform. In this instance, we'll take the transform of the script object. You've seen this object in every one of our scenes. We'll also go ahead and give it a startLength!

    void Start()
    {
        // Start the recursive branch function.
        Branch(transform, startLength);
    }

    void Branch(Transform parentRoot, float length)
    {

    }
    

Figure 8.20

…followed by drawing a line upwards (Figure 8.20):

    void Branch(Transform parentRoot, float length)
    {
        // Determine where this branch ends.
        Vector2 end = parentRoot.position + parentRoot.up * length;

        // Create the line renderer for this branch.
        DrawLine(parentRoot.gameObject, parentRoot.position, end);
    }
    

Once we’ve finished the root, we just need to translate to the end and rotate in order to draw the next branch. (Eventually, we’re going to need to package up what we’re doing right now into a recursive function, but let’s sort out the steps first.)

Figure 8.21

Remember, when we rotate in Unity, we are always rotating around the point of origin, so here the point of origin must always be translated to the end of our current branch.

    Transform leftRoot = new GameObject().transform;
    leftRoot.parent = parentRoot;

    // Set the position and rotation relative to the previous branch.
    leftRoot.localPosition = Vector2.up * length;

    //use eulerAngles to handle rotation
    leftRoot.localEulerAngles = new Vector3(0, 0, childAngle);
    

Now that we have a branch going to the right, we need one going to the left. Let’s look at all the code together.

Figure 8.22

Figure 8.23

    void Branch(Transform parentRoot, float length)
    {
        // Determine where this branch ends.
        Vector2 end = parentRoot.position + parentRoot.up * length;

        // Create the line renderer for this branch.
        DrawLine(parentRoot.gameObject, parentRoot.position, end);

        // Create left and right branches depending on this branch length.
        if(length > minimumLength)
        {
            // Create a new child transform for this branch.
            Transform leftRoot = new GameObject().transform;
            leftRoot.parent = parentRoot;

            // Set the position and rotation relative to the previous branch.
            leftRoot.localPosition = Vector2.up * length;
            leftRoot.localEulerAngles = new Vector3(0, 0, childAngle);

            // Call this function again.
            Branch(leftRoot, length * childScale);

            // Repeat for the right branch, but with the opposite angle.
            Transform rightRoot = new GameObject().transform;
            rightRoot.parent = parentRoot;
            rightRoot.localPosition = Vector2.up * length;
            rightRoot.localEulerAngles = new Vector3(0, 0, -childAngle);
            Branch(rightRoot, length * childScale);
        }
    }
    

If you think of each call to the function line() as a “branch,” you can see from the code above that we have implemented our definition of branching as a line that has two lines connected to its end. We could keep adding more and more calls to line() for more and more branches, but just as with the Cantor set and Koch curve, our code would become incredibly complicated and unwieldy. Instead, we can use the above logic as our foundation for writing a recursive function, replacing the direct calls to line() with our own function called branch(). Let’s take a look.

Example 8.6: Recursive tree

• Code
• Demo

Notice how in the above code we use pushMatrix() and popMatrix() around each subsequent call to branch(). This is one of those elegant code solutions that feels almost like magic. Each call to branch() takes a moment to remember the location of that particular branch. If you turn yourself into Unity for a moment and try to follow the recursive function with pencil and paper, you’ll notice that it draws all of the branches to the right first. When it gets to the end, popMatrix() will pop us back along all of the branches we’ve drawn and start sending branches out to the left.

You may have noticed that the recursive function we just wrote would not actually draw the above tree. After all, it has no exit condition and would get stuck in infinite recursive calls to itself. You’ll also probably notice that the branches of the tree get shorter at each level. Let’s look at how we can shrink the length of the lines as the tree is drawn, and stop branching once the lines have become too short.

    void Branch(Transform parentRoot, float length)
    {
        // Determine where this branch ends.
        Vector2 end = parentRoot.position + parentRoot.up * length;

        // Create the line renderer for this branch.
        DrawLine(parentRoot.gameObject, parentRoot.position, end);

        // Create left and right branches depending on this branch length.
        if (length > minimumLength)
        {
            int childBranchCount = Random.Range(minBranches, maxBranches + 1);

            for(int i = 0; i < childBranchCount; i++)
            {
                // Create a new child transform for this branch.
                Transform newBranch = new GameObject().transform;
                newBranch.parent = parentRoot;

                // Set the position and rotation relative to the previous branch.
                newBranch.localPosition = Vector2.up * length;
                newBranch.localEulerAngles = new Vector3(0, 0, Random.Range(minChildAngle, maxChildAngle));

                // Call this function again.
                Branch(newBranch, length * childScale);
            }
        }
    }
    

Example 8.7: Recursive tree

• Code
• Demo

We always call branch() twice. But why not pick a random number of branches and call branch() that number of times?

8.6 L-systems

In 1968, Hungarian botanist Aristid Lindenmayer developed a grammar-based system to model the growth patterns of plants. L-systems (short for Lindenmayer systems) can be used to generate all of the recursive fractal patterns we’ve seen so far in this chapter. We don’t need L-systems to do the kind of work we’re doing here; however, they are incredibly useful because they provide a mechanism for keeping track of fractal structures that require complex and multi-faceted production rules.

In order to create an example that implements L-systems in Unity, we are going to have to be comfortable with working with (a) recursion, (b) transformation matrices, and (c) strings. So far we’ve worked with recursion and transformations, but strings are new here. We will assume the basics, but if that is not comfortable for you, I would suggest taking a look at the Unity tutorial Strings and Drawing Text.

An L-system involves three main components:

• Alphabet. An L-system’s alphabet is comprised of the valid characters that can be included. For example, we could say the alphabet is “ABC,” meaning that any valid “sentence” (a string of characters) in an L-system can only include these three characters.
• Axiom. The axiom is a sentence (made up with characters from the alphabet) that describes the initial state of the system. For example, with the alphabet “ABC,” some example axioms are “AAA” or “B” or “ACBAB.”
• Rules. The rules of an L-system are applied to the axiom and then applied recursively, generating new sentences over and over again. An L-system rule includes two sentences, a “predecessor” and a “successor.” For example, with the Rule “A —> AB”, whenever an “A” is found in a string, it is replaced with “AB.”

Let’s begin with a very simple L-system. (This is, in fact, Lindenmayer’s original L-system for modeling the growth of algae.)

Figure 8.24: And so on and so forth...

Alphabet: A BAxiom: ARules: (A → AB) (B → A)

As with our recursive fractal shapes, we can consider each successive application of the L-system rules to be a generation. Generation 0 is, by definition, the axiom.

Let’s look at how we might create these generations with code. We’ll start by using a String object to store the axiom.

    // Start with "A"
    private string current = "A";
    

And once again, just as we did with the Game of Life and the Koch curve List examples, we will need an entirely separate string to keep track of the “next” generation.

    // A new StringBuilder for the next generation
    System.Text.StringBuilder next = new StringBuilder();
    

Now it’s time to apply the rules to the current generation and place the results in the next.

    // A new StringBuilder for the next generation
    System.Text.StringBuilder next = new StringBuilder();
    char[] currentCharString = current.ToCharArray();

    // Look through the current string to replace according
    // to L-System rules
    foreach (char c in currentCharString)
    {
        if (c == 'A')
        {
            // If we find A replace with AB
            next.Append("AB");
        }
        else if (c == 'B')
        {
            // If we find B replace with A
            next.Append("A");
        }
    }

    // The current String is now the next one
    current = next.ToString();
    count++;
    

And when we’re done, current can become next.

    // Print to console
    print("Generation " + count + ": " + current);
    

To be sure this is working, let’s package it into a function and and call it every time the mouse is pressed.

Example 8.9: Simple L-system sentence generation

• Code
• Demo

Since the rules are applied recursively to each generation, the length of the string grows exponentially. By generation #11, the sentence is 233 characters long; by generation #22, it is over 46,000 characters long. The C# String class, while convenient to use, is a grossly inefficient data structure for concatenating large strings. A String object is “immutable,” which means once the object is created it can never be changed. Whenever you add on to the end of a String object, C# has to make a brand new String object (even if you are using the same variable name).

    String s = "blah";
    s += "add some more stuff";
    

In most cases, this is fine, but why duplicate a 46,000-character string if you don’t have to? For better efficiency in our L-system examples, we’ll use the StringBuffer class, which is optimized for this type of task and can easily be converted into a string after concatenation is complete.

    StringBuffer str = new StringBuffer();
    for (int i = 0; i < current.length(); i++) 
    {
        char c = current.charAt(i);
        if (c == 'A') 
        {
          next.append("AB");
        } 
        else if (c == 'B') 
        {
          next.append("A");
        }
      }
      current = next.toString();
    }
    

You may find yourself wondering right about now: what exactly is the point of all this? After all, isn’t this a chapter about drawing fractal patterns? Yes, the recursive nature of the L-system sentence structure seems relevant to the discussion, but how exactly does this model plant growth in a visual way?

What we’ve left unsaid until now is that embedded into these L-system sentences are instructions for drawing. Let’s see how this works with another example.

Alphabet: A BAxiom: ARules: (A → ABA) (B → BBB)

To read a sentence, we’ll translate it in the following way:

A: Draw a line forward.B: Move forward without drawing.

Let’s look at the sentence of each generation and its visual output.

Generation 0: AGeneration 1: ABAGeneration 2: ABABBBABAGeneration 3: ABABBBABABBBBBBBBBABABBBABA

Look familiar? This is the Cantor set generated with an L-system.

Figure 8.25

The following alphabet is often used with L-systems: “FG+-[]”, meaning:

F: Draw a line and move forwardG: Move forward (without drawing a line)+: Turn right-: Turn left[: Save current location]: Restore previous location

This type of drawing framework is often referred to as “Turtle graphics” (from the old days of LOGO programming). Imagine a turtle sitting on your computer screen to which you could issue a small set of commands: turn left, turn right, draw a line, etc. Unity isn’t set up to operate this way by default, but by using Transform.Translate(), Transform.Rotate(), and the LineRenderer, we can emulate a Turtle graphics engine fairly easily.

Assuming we have a sentence generated from the L-system, we can walk through the sentence character by character and call the appropriate function as outlined above.

    string sentence = lSys.Sentence;
    for(int i = 0; i < sentence.Length; i++)
    {
        char c = sentence[i];
        if (c == 'F' || c == 'G')
        {
            line();
        }
        else if (c == '+')
        {
            state.Angle += theta;
        }
        else if (c == '-')
        {
            state.Angle -= theta;
        }
        else if (c == '[')
        {
            savedStates.Push(state.Clone());
        }
        else if (c == ']')
        {
            state = savedStates.Pop();
        }
    }
    

The next example will draw a more elaborate structure with the following L-system.

Alphabet: FG+-[]Axiom: FRules: F -→ FF+[+F-F-F]-[-F+F+F]

The example available for download on the book’s website takes all of the L-system code provided in this section and organizes it into three classes:

• Rule: A class that stores the predecessor and successor strings for an L-system rule.
• LSystem: A class to iterate a new L-system generation (as demonstrated with the StringBuffer technique).
• Turtle: A class to manage reading the L-system sentence and following its instructions to draw on the screen.

We won’t write out these classes here since they simply duplicate the code we’ve already worked out in this chapter. However, let’s see how they are put together in the main tab.

Example 8.10: LSystem

• Code
• Demo