Algorithmic Botany

Today, let’s dive into the world of algorithmic botany — the process of using simple mathematical models to create stunning virtual flora.

Introduction to L-Systems

Ever wondered how complex patterns in nature like the spirals in a seashell or the branching of trees are formed? Enter the world of L-Systems, a simple yet powerful idea that was first proposed by biologist Aristid Lindenmayer. These systems, named after Lindenmayer himself, provide us with a way to describe complex patterns using basic rules. Think of L-systems like a secret language of nature, where different letters or symbols stand for different growth actions. This language, which we refer to as a ‘formal grammar,’ might tell a tree to ‘grow a branch here’ or ‘sprout some leaves there.’ Although they were first used to study plant growth, artists and computer scientists now use L-systems to generate lifelike virtual plants and beautiful designs.

L-systems are composed of the following components:

• an Alphabet of symbols, where each symbol represents a specific drawing action
• an Axiom or initial phrase with which to begin construction
• a set of Production Rules, which will expand each symbol in our alphabet into a larger string of symbols
• a mechanism for translating the generated “strings” into geometrical structures.

Let’s draw a square with L-systems as an extremely basic example. We can model this with an Alphabet containing {F, +} (where F represents the action “go forward” and + means “turn right 90 degrees”), a production rule that states F turns into F+F+F+F, and an axiom of F.

As we read this string, we see our initial F and convert it into F+F+F+F using our production rules. Now we can take a pen and a piece of paper, and draw a square by reading the string:

• Go forward, turn right
• Go forward, turn right
• Go forward, turn right
• Go forward

Embracing the Logic of L-Systems

What makes L-systems exciting is how they can create complex structures from simple rules. Just as a tree might start as a seed and grow into a towering plant, an L-system starts with a simple starting point (like a single line) and then applies its rules over and over again to create a more complex image. If you’ve ever looked closely at a tree and noticed how the branches look like smaller versions of the whole tree, you’ve spotted what we call ‘self-similarity,’ a key feature in L-systems. By playing with these rules, we can mimic different kinds of natural growth and variation, making our virtual plants look incredibly realistic.

This approach has several benefits. For one, it allows us to generate a wide variety of plants by tweaking the rules and parameters of our L-system. Change the angle between branches, the length of each segment, or the shape of the leaves, and you can create an entirely different species. Secondly, L-systems naturally create fractal-like structures, capturing the self-similarity seen in real plants where similar patterns repeat at different scales. Finally, these systems allow for an organic randomness to be introduced, further enhancing the realism of the plant models.

Our First Tree

When you start creating your own virtual plants, you’ll find it’s much like tending a real garden. You’ll plant the seed of your L-system by defining its initial state and rules, then watch it grow as you iterate the system. You may need to prune it back a bit, tweaking the rules to prevent it from growing too wild. But with patience and care, you can cultivate a virtual garden of beautiful, algorithmically generated plants.

As an example, the first plant that we’ll model together will be a tree. More specifically, we’ll be modeling a binarty tree, which splits itself into two equal branches as you continue going up the stem. We’ll go through the thought process of constructing an L-system representation of this tree, and how we can use code to bring our tree to life.

1. Rules

When constructing an L-system for a binary tree, we need to think about the fundamental features of binary trees and how to represent them with our L-system’s rules.

A binary tree has a root from which two branches sprout; each of these branches can be thought of as smaller binary trees or ‘sub-trees’. This recursive nature is crucial when creating our L-system, and this is where the concept of ‘self-similarity’ comes in. Essentially, the structure of the whole tree is similar to its parts. Our L-system rules should capture this.

A simple set of rules could start with a single line, which we’ll call the ‘stem’. In the next ‘generation’ or iteration, the stem is replaced by a stem with two branches at the top (representing the two branches sprouting from a root in a binary tree). Each of these new branches then becomes a new ‘stem’ in the next generation, repeating the process. In this way, our L-system replicates the growth process of a binary tree, starting with a single root and recursively sprouting two branches at each step. We would continue this process for several iterations until our virtual tree reaches the desired complexity.

2. Language

As we continue to build our L-system, we introduce symbols to represent different elements or actions in our system. These symbols serve as a sort of shorthand, allowing us to write complex rules in a compact and easy-to-understand way. For the case of a binary tree, we could use a symbol like F to represent drawing a line forward, which serves as our ‘stem’, and + and - to signify turns, which will help us create branches.

Now, when it comes to creating branches, we need a way to keep track of where each branch starts so that we can return to that point and create the next branch. This is where the symbols [ and ] can come into play. You can think of them as saying “remember this spot” and “return to the last spot we remembered,” respectively.

So, when our system sees an [, it’s like it makes a mental note of the current position and direction. Then it can move forward and turn to draw a branch. When it later encounters a ], it knows to return to the last position it remembered—to the base of the branch it just drew—and then to proceed in the original direction. This way, we can draw multiple branches from a single point, and these symbols help to give our tree its structure, allowing it to spread out in different directions as it grows.

Our alphabet is now: { F, +, -, [, ] }

3. Process

Now that we have our alphabet, we need an axiom, and a set of composition rules.

Our rules of production could look like the following:

and our axiom would be: F.

With these rules in place, let’s explore an example string for our binary tree L-system. For a binary tree of depth 2, the string might look something like this: F[+F][-F].

Here’s how we read it:

Starting from the root of the tree, F tells us to draw a line forward. This will be the trunk of our tree. Then we come across the [ symbol, which, as we’ve learned, tells us to remember the current position and direction.

Next, we encounter +F, which instructs us to turn to a designated direction (let’s say right for this example) and draw another line. This line is the first branch of our tree.

At this point, we’ve finished the instructions inside the brackets, so we encounter ], our symbol to return to the last remembered position and direction - back to the top of the trunk.

We then proceed to [-F], which, much like the first branch, tells us to remember our position, turn in the opposite direction (this time, to the left), and draw a line, giving us the second branch of our tree. After this, we again encounter ], so we return to the top of the trunk.

With this, we have our binary tree of depth 2. We started with a simple trunk, added a branch to the right, returned to the trunk, and then added another branch to the left. The beauty of the L-system lies in how we can create such a complex shape using a simple string of symbols, building complexity through the process of repeated growth and branching.

4. Demo

Below is an interactive demo that you can play around with, showing what this process looks like for varying “heights” of the binary tree.

And the corresponding code:

function generateBinaryTree(depth: number): string {
  // Base case: If depth is 0, return the axiom or initiator 'F'
  if(depth === 0) {
    return 'F';
  } else {
    // Recursive case: Replace 'F' with the production rule 'F[+F][-F]'
    const subtree: string = generateBinaryTree(depth - 1);
    return subtree.replace(/F/g, 'F[+F][-F]');
  }
}

interface Turtle {
  x: number;
  y: number;
  angle: number;
  stepLength: number;
}

function drawBinaryTree(ctx: CanvasRenderingContext2D, lSystemString: string, initialStepLength: number, angleChange: number, scaleFactor: number) {
  const stack: Turtle[] = [];
  let turtle: Turtle = { x: ctx.canvas.width / 2, y: ctx.canvas.height, angle: -Math.PI / 2, stepLength: initialStepLength };

  for (const char of lSystemString) {
    switch (char) {
      case 'F': // draw a line segment
        const newX = turtle.x + turtle.stepLength * Math.cos(turtle.angle);
        const newY = turtle.y + turtle.stepLength * Math.sin(turtle.angle);
        ctx.beginPath();
        ctx.moveTo(turtle.x, turtle.y);
        ctx.lineTo(newX, newY);
        ctx.stroke();
        turtle = { ...turtle, x: newX, y: newY };
        break;
      case '+': // turn right
        turtle = { ...turtle, angle: turtle.angle - angleChange };
        break;
      case '-': // turn left
        turtle = { ...turtle, angle: turtle.angle + angleChange };
        break;
      case '[': // save the current state
        stack.push(turtle);
        // Reduce the step length for the next state
        turtle = { ...turtle, stepLength: turtle.stepLength * scaleFactor };
        break;
      case ']': // restore the previous state
        turtle = stack.pop()!;
        break;
    }
  }
}

The binary tree is just one of infinitely many shapes that exist in L-systems. I hope that after reading this, you’re inspired to create your own mathematical gardens! The key to learning any skill or concept is repeated study and practice, so I encourage you to try this exercise for yourself: what’s a pattern, shape, or structure that you see in nature? And how can you model it using formal grammar?

The answer may be far more simple than you’d think, and soon enough, you’ll be an algorithmic botanist too.

../

Written and Created by Davis Keene