This article is from a recent engineering talk I gave at Qualia.
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!
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.
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)
- 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.
Let’s look at how to model this tree-like plant:
First, we define the three elements of our L-system:
- V (the vocabulary) will contain the characters
F, and the additional symbols
- ω (the starting string) will just be
P will contain these two productions:
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
F[−X][X]F[−X]+FX. To grow it by another generation, we replace every
F[−X][X]F[−X]+FX, and every
We only have productions corresponding to
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.
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:
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
We can also see that the output of the production rule
F[−X][X]F[−X]+FX is going to produce complex strings inside each set of square brackets. Each time we see
[-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.
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!
Now, we need a way to run the production rules. Here’s a function to apply a single rule:
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
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.
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.
We’ll need to get a little bit of setup out of the way, to create a canvas and configure p5:
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:
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
- 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
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
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.
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:
Let’s animate the drawing to make it more fun to watch. We’ll use ES6 generators to do it.
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
We will do two things to restructure our code:
- First, we will create a generator to yield intermediate fragments of the fractal as we create them
- Second, we will use
requestAnimationFrameto draw each fragment
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
yieldexpression, 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:
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:
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
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 makes 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
Here’s the code to set it all up:
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
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 👋