Drawing fractals in the browser with L-systems and ES6

This article is from a recent engineering talk I gave at Qualia.

Here’s what we’ll make! L-systems are great for modeling plants…

Fractals are a beautiful cross between math, visualization, and art. Unfortunately, making computer programs draw pictures can be pretty complicated. Luckily, modern web browsers have powerful graphics features built in, and nearly everyone has a web browser. The browser is actually a pretty good place to start playing around with fractal graphics!

In this post, we will look at one simple approach for modeling fractals, and how to draw them in the web browser. I’ll also cover a cool new feature of JavaScript, called generators, and show how they might come in handy for drawing fractals.

Some theory: modeling fractals with L-systems

To start things off, let’s think about how we might represent a fractal in a computer program. There are many ways to think about fractals, but in this post, I want to focus on one approach, called L-systems, because they are easy to understand and quick to implement.

Aristid Lindenmeyer invented L-systems, or Lindenmeyer systems, as a way to model the growth of bacteria and fungi, and people later used them to model plants and other biological systems. The basic idea of an L-system is to use strings of characters to model the evolution of a living system. Each character symbolizes some part of the creature, like a cell, leaf, or branch. The system starts with an initial string, and by following some rules for manipulating the initial string, we end up modeling the change in the living creature over time by generating progressively more complex strings.

Defining the L-system

An L-system is a formal grammar, which means it is a set of rules for producing strings in a formal language. Mathematically, it’s defined as a tuple,

G = (V, ω, P)

where:

• V is the alphabet of characters, or symbols
• ω is the starting string, also called the axiom, containing symbols from V
• P is a set of production rules, also called “productions,” for evolving the system from one string to the next.

Each production specifies how to convert one input character from the current state of the system into one or more output characters for the next state.

Starting with the axiom, we apply the appropriate production to each character to get the string representing the first generation. To get the second generation, we apply our productions to all of the symbols in the first generation, and so on. We can model generations indefinitely by applying the productions again and again.

Despite the complex-sounding theory, L-systems are really just find-and-replace rules, like you would use in a basic text editor.

Modeling a plant

Let’s look at how to model this tree-like plant:

Three fractal trees

First, we define the three elements of our L-system:

• V (the vocabulary) will contain the characters X and F, and the additional symbols []+-
• ω (the starting string) will just be X

P will contain these two productions:

• X→F[−X][X]F[−X]+FX
• F→FF

In each generation, we will use one string to symbolize the current state of our model, which in this case is the shape of our plant. We begin by setting the state string equal to the axiom. To grow the plant by one generation, we replace the X with F[−X][X]F[−X]+FX. To grow it by another generation, we replace every X with F[−X][X]F[−X]+FX, and every F with FF.

We only have productions corresponding to X and F, so when we encounter any other character in the system state, like [, we just copy it over to the new state string. Symbols like [, for which there are no productions, are called constants.

The strings look complicated, but the process we follow is always the same: we replace each character in the current state string with the right-hand-side of its corresponding production rule.

Evolving the model

We’ve defined all we need for our L-system. Let’s evolve it for a few generations and see what happens!

To watch our model of a plant grow, we start with the axiom and run each rule on it:

X

F[−X][X]F[−X]+FX

FF[-F[-X][X]F[-X]+FX][F[-X][X]F[-X]+FX]FF[-F[-X][X]F[-X]+FX]+FFF[-X][X]F[-X]+FX

FFFF[-FF[-F[-X][X]F[-X]+FX][F[-X][X]F[-X]+FX]FF[-F[-X][X]F[-X]+FX]+FFF[-X][X]F[-X]+FX][FF[-F[-X][X]F[-X]+FX][F[-X][X]F[-X]+FX]FF[-F[-X][X]F[-X]+FX]+FFF[-X][X]F[-X]+FX]FFFF[-FF[-F[-X][X]F[-X]+FX][F[-X][X]F[-X]+FX]FF[-F[-X][X]F[-X]+FX]+FFF[-X][X]F[-X]+FX]+FFFFFF[-F[-X][X]F[-X]+FX][F[-X][X]F[-X]+FX]FF[-F[-X][X]F[-X]+FX]+FFF[-X][X]F[-X]+FX

After only four generations, this system already looks pretty complex! We can see a sequence of F characters collecting at the beginning of the state string. Those characters represent the initial trunk or stem of our plant. In each generation, the trunk gets twice as long because of our production F→FF.

We can also see that the output of the production rule X→F[−X][X]F[−X]+FX is going to produce complex strings inside each set of square brackets. Each time we see [X] or [-X] in subsequent generations, we will end up substituting the output of the rule again between the square brackets. These parenthetical asides will represent the branches coming off the trunk of our tree, and each will grow fractally more complex in subsequent generations. We’ll soon see how to translate them into pictures, but first, let’s write some code to run the production rules automatically.

Writing the L-system in code

It’s perfectly possible to run the production rules of the L-system with pen and paper, but computers are really good at storing and manipulating strings, so we should have no trouble expressing L-systems in code!

Let’s set up a simple JavaScript file to model our tree fractal. We will start by declaring the axiom and production rules:

const tree = {
  axiom: 'X',
  rules: {
    X: 'F[-X][X]F[-X]+FX',
    F: 'FF',
  },
}

Here we represent the production rules with a simple JavaScript object, where each key is the input symbol for the production, and each value is the output string for that production. We don’t need to list the vocabulary explicitly, so we have fully defined our system.

Now, we need a way to run the production rules. Here’s a function to apply a single rule:

function applyRule(rules, char) {
  return rules[char] || char;
}

Given the rules and a character in the current system state, applyRule returns the output of the rule if there is one, or the original character if there is no rule for it. Now, to get from one generation to the next, we just apply rules for every character in the current state, called previousGeneration below:

function renderAGeneration(system, previousGeneration) {
  let nextGeneration = '';
  for (const character of previousGeneration) {
    nextGeneration += applyRule(system.rules, character);
  }
  return nextGeneration;
}

Try it out!

Putting it all together, we have a way to simulate the L-system. Check out the “Result” tab in this JSFiddle to see the L-system evolve through several generations. If you “Edit in JSFiddle”, you can tweak numIters to change how many generations the script simulates.

Drawing the fractal

Now we have an L-system to model our plant, but the raw strings don’t look much like a tree. To draw a fractal from the strings, we need to map each symbol to a drawing rule.

Defining the drawing rules

We’ll use an HTML canvas with p5.js to handle the drawing. It’s possible to draw on a canvas without using a library, but p5 will make this a lot easier.

We’ll need to get a little bit of setup out of the way, to create a canvas and configure p5:

function setup() {
  createCanvas(CANVAS_BOUNDS.x, CANVAS_BOUNDS.y);
  angleMode(DEGREES);
  noLoop();
}

Now we need to map the symbols in the vocabulary of our L-system to functions that draw on the canvas. Let’s add a new property, commands, to our system, to hold drawing functions:

const tree = {
  params: {
    angle: 25,
    length: 2,
  },
  axiom: 'X',
  rules: {
    X: 'F[-X][X]F[-X]+FX',
    F: 'FF',
  },
  commands: {
    'F': drawForward,
    '-'(drawingState, params) {
      drawingState.state.direction -= params.angle;
    },
    '+'(drawingState, params) {
      drawingState.state.direction += params.angle;
    },
    '['(drawingState, params) {
      drawingState.push();
    },
    ']'(drawingState, params) {
      drawingState.pop();
    },
  }
}

Each command is a function. Its name corresponds to a symbol in the system state string. When we encounter the symbol, we run the function. For example, for every F we see in the L-system’s state, we will call drawForward (not yet defined) to draw a line straight forward. We’ve also added a few other concepts:

• We have some drawing parameters for our system in params. We can add arbitrary configuration values here and then use them in our drawing functions. In this case, we configure the angle of the tree’s branches, and the length of each straight segment corresponding to an F.
• We give each drawing function access to the drawing params, and to a drawingState, which tracks the current drawing position and direction, and maintains a stack. We can push the position and direction of the drawing context to the stack, then later pop them to restore them as the current drawing state.

If you’ve used Logo’s turtle graphics, this drawing style should feel familiar. We will imagine a pen that drags across the canvas, and when we pop a position off the stack of the drawingState, we jump to the new location without drawing as though we lifted the pen.

Now we just need to call our drawing functions within renderAGeneration:

function renderAGeneration (system, previousGeneration, drawingState, draw=true) {
  let nextGeneration = '';
  for (const character of previousGeneration) {
    const nextCharacters = applyRule(system.rules, character);
    nextGeneration += nextCharacters;
    if (draw) {
      for (const character of nextCharacters) {
        if (system.commands[character]) {
         system.commands[character](drawingState, system.params);
       }
      }
    }
  }
  return nextGeneration;
}

Each time we apply a rule to one character in the previousGeneration, we get a string of one or more characters in nextCharacters, which we append to the string we’re building to represent the next generation of the L-system. For each of those characters, we look for a drawing function and call it if it exists. We also have a new boolean argument, draw, which signals whether we should in fact draw something to the canvas. We’ll use it below.

We’re going to render the fractals when the user clicks the mouse. p5 comes out of the box with a mouse-click listener, so we just need to wrap our previous loop in a mouseClicked function:

numIters = 4;
system = tree;

function mouseClicked() {
  const origin = new Point(mouseX, mouseY);
  let systemState = system.axiom;
  console.log(systemState);

  for (let i = 1; i < numIters; i++) {
    const drawingState = new DrawingState(origin, -90);
    const shouldDraw = i === numIters - 1;
    systemState = renderAGeneration(system, systemState, drawingState, shouldDraw);
    console.log(systemState);
  }
}

When the user clicks the canvas, we store the location of their click as the origin of the new drawing. We initialize system state to the axiom (X), and then iterate through numIters generations of the L-system. After each iteration, systemState contains the new, more complex description of the fractal.

We wait to draw the fractal until it’s fully formed. The boolean shouldDraw becomes true on the final iteration of the loop, signaling that renderAGeneration should draw to the canvas.

Try it out!

You can play with the result in the “Result” tab below. Try clicking on the blank canvas!

Now we’re drawing the fractal to the canvas, but we’re drawing the whole thing at once instead of gradually enhancing the drawing as we compute the new state of the L-system:

The fractals look right, but they need more animation!

Let’s animate the drawing to make it more fun to watch. We’ll use ES6 generators to do it.

Animating the fractals

So far, we have used synchronous code to generate our fractal descriptions and render them to the canvas. From the time the user clicks the mouse, triggering the mouseClicked function, until the mouseClicked function finishes running all of the functions it calls and returns, our code never yields the main thread of the browser’s JavaScript engine. Meanwhile, there is no way for the browser to update the drawing we see on the canvas!

To get the intermediate steps of the drawing to show up on the canvas, we need to design our code to yield the JavaScript thread to other code the browser is trying to run.

We will do two things to restructure our code:

1. First, we will create a generator to yield intermediate fragments of the fractal as we create them
2. Second, we will use requestAnimationFrame to draw each fragment

Using a generator to yield intermediate fragments

Generators are a new feature in JavaScript as of ES6. If you’ve used coroutines in other languages, they should feel familiar to you. MDN describes generators like this:

Generators are functions which can be exited and later re-entered. Their context (variable bindings) will be saved across re-entrances. […]

Calling a generator function does not execute its body immediately; an iterator object for the function is returned instead. When the iterator’s next() method is called, the generator function’s body is executed until the first yield expression, which specifies the value to be returned from the iterator […] (from MDN)

To create a generator, we declare a generator function, which returns an iterator. We can call next() on the iterator repeatedly to get its values.

Let’s create a generator function that takes an L-system and its current state and produces an iterator for the L-system’s next state string:

function *fragmentGenerator(system, string) {
  for (const char of string) {
    yield applyRule(system.rules, char);
  }
}

We iterate through the characters of the string like before, but this time, instead of calling the corresponding drawing functions inside the loop, we yield the fragment of characters that results from applying the rule.

To consume the generated fragments of the system state, first we invoke the generator function to get an iterator. Then, we call next() on the iterator repeatedly, checking whether it is done after each call:

// Create an iterator from our generator function
const fragmentIterator = fragmentGenerator(system, systemState);

let iter;
while (iter = fragmentIterator.next(), !iter.done) {
  const fragment = iter.value;
  for (const character of fragment) {
    // draw characters like before
  }
}

Using a generator for the fragments allows us to observe the progress of applying each rule from the outside, in this case from our while loop. We’re on to something powerful, but so far, the effect is not different from what we had before.

We’re still looping through all of the fragments synchronously; we’ve just moved the synchronous iteration to a while loop. For the final step, we will stop iterating in a loop at all and use requestAnimationFrame instead.

Rendering with requestAnimationFrame

Instead of rendering the fractal within a loop, we need a way to render a frame, then yield the thread, then render another frame, yield the thread, and so on, giving the browser a chance to update the canvas each time our code stops running.

Our strategy will be to write a new function, drawFrame, responsible for drawing just one frame of the animation. drawFrame will make its changes to the canvas quickly, then return, allowing the browser to update the image of the canvas.

We won’t invoke drawFrame directly; instead, we will pass it as a callback to requestAnimationFrame, a function provided by the browser. The browser will call drawFrame when it’s time to update the canvas (usually about 60 times per second). After we draw each frame, we will request another call to drawFrame by calling requestAnimationFrame again.

Here’s the code to set it all up:

function drawSystem(system, fragmentIterator, drawingState) {
  const drawFrame = () => {
    const iter = fragmentIterator.next();
    if (iter.done) {
      return;
    }
    const fragment = iter.value;
    for (const character of fragment) {
      const drawingFunction = system.commands[character];
      if (drawingFunction) {
        drawingFunction(drawingState, system.params);
      }
    }
    requestAnimationFrame(drawFrame);
  };
  requestAnimationFrame(drawFrame);
}

We define drawFrame as a closure within drawSystem so it will have access to the variables describing our L-system.

The core of drawFrame is identical to the drawing code we’ve already seen. The big difference is that now, we iterate through the fragments of the L-system without using a loop! Between each run of drawFrame, none of our JavaScript functions is running, and the browser has a chance to update the canvas.

Try it out!

Here’s the final code, showing everything we’ve covered working together to animate the fractals. Click on the canvas in the “Result” tab to kick off the animations, and try playing around with the parameters in JSFiddle! Have fun!

Thanks for reading! If you enjoyed this post, you might also enjoy working at Qualia! See you next time 👋

Comments