Reading time: about 10 minutes
Lindenmayer systems, or L-systems, can describe how living things develop complex forms by the repeated application of simple rules. Aristid Lindenmayer (1925–1989), the theoretical biologist who proposed L-systems in 1968, first used them to describe the growth patterns of algae. This page is (mostly) algae-free, but it does let you explore Lindenmayer systems by making plant-like structures, classic fractals, and other designs.
The natural world produces amazingly complex systems from simple starting points. In the biology, computational models have played a critical role in helping scientists understand how these complex systems can develop. L-systems are one of the better-known of these models. In L-systems, structures develop through a process of string rewriting. A string of letters is transformed into a new string of letters using simple rules called productions. The process is repeated indefinitely, each time using the string that was just produced as the source for the next string. Because the strings tend to grow with each rewrite, an L-system can become arbitrarily complex, but always guided by a simple process dictated by a fixed set of simple rules.
Before getting into more detail, take a moment to play with the app below. Try changing the Order and drawing the result. Try drawing orders 0, 1, 2, 3, and 4 in order and observe the progression. Then try some other example systems to get a feel for what’s possible (there are over 50!). Feel free to play, just know that behind the scenes, L-system strings can grow very quickly as the order increases. The longer the string, the longer it will take to draw the result! Your browser may even run out of memory, which will “crash” the page—but with no real harm done. Just navigate back to the page and choose different settings!
L-system repeatedly rewrite a string according to some simple rules: You start from a string called the axiom. You can think of it like a seed: it is the starting point that the system grows from. Regulating that growth is a set of rules, called productions. By applying the produtions to the axiom, you will make new strings that represent one “step” of growth. All of the strings you can produce are said to be in the language of the L-system. What’s more, you can take any string that you make in this way, re-apply the same productions to it, and get a new string that is also “in the language” of the L-system.
Let’s look at a simple example:
axiom Y Y → XYX
This system has only production, the rule
Y → XYX. To apply it, you scan a
string that is known to be in the system’s language from left to right, and
anywhere you see the pattern on the left of the
→ symbol, you replace it with
the pattern on the right side. Let’s see how that would work.
To start with, we only know of one string in the language, the axiom
Y. But we
see that we can produce
XYX by applying the production
Y → XYX. So now we know
XYX is also in the language, and we can use it to produce a new string, too.
There is no production with
X on the left side, so those won’t change. But the
Y in the middle
can be changed to
XYX again, giving the string
XXYXX. That’s a new string in the
language, so you can rewrite it, too, and so on.
With this system, you can soon see that each time you apply the production you will get exactly one new string
that is just like the one you started with but with another
X added to either
side of the
Y in the middle. When an L-system can only make one new string
each time it is rewritten, we often talk about the system’s “order n”
string. The order 0 string is the axiom. The order 1 string is made from the
order 0 string. The order 2 string is made from the order 1 string, and so on.
That’s why the app above has a control named Order: it uses
the string of that order to produce the drawing.
Not all L-systems work this way. For example, what would happen if we extend the system above as follows?
axiom Y Y → XYX YX → XY
This system starts the same, producing
Y and then
XYX as before. After that,
you run into a problem: two different rules can be applied at the same spot.
You can replace the
XYX, or you can replace the
Y and the
XY. Which to choose?
There are different ways that this can be handled, but what if you allow
both possibilities? Then instead of having
one definitive string for each generation, you have sets of strings leading
to more sets of strings! As you can imagine, systems that allow rules like these
tend to become very complex, very quickly. On this page we eliminate this
problem by restricting the app to a subtype of L-system called a
d0L-system. A d0L-system has a couple of changes which will guarantee
that our systems are nicely ordered:
The rest of this article deals exclusively with d0L-systems. Don’t feel cheated—they still offer lots of possibilities.
So far we’ve seen that L-systems can grow strings very well. How does that connect to the natural world? We can get a hint that the connection is there by going back to Lindenmayer’s original work with algae growth patterns. Here is a system from his original paper:
axiom B A → AB B → A
If you write the first 8 orders of this system you’ll get
ABAABABAABAABABAABABA. Notice a pattern?
If not, look closely at the length of each of these strings:
1, 1, 2, 3, 5, 8, 13, 21. Can you see why the strings produced by this system
are called Fibostrings? Quite apart from how algae grow, you
probably remember learning that the Fibonacci number sequence shows up
often in the natural world, most famously in the way that
leaves and scales are arranged on plants
Still, as interesting as it is to whip yourself up some Fibostrings, it is still a big leap from that to the images produced by the app above. To get there, we need to give the strings a geometric interpretation. The demo does this using “turtle graphics”, on odd name which comes from the Logo programming language. Turtle graphics work like this: Imagine you’re a turtle on an infinitely large piece of paper. Not just any turtle, but one that can understand simple instructions and that has a basic understanding of angles and distances. Finally, imagine that you (the unusually bright turtle, that is) also have a pen in your mouth.
Have you got that image in mind? Good.
Now suppose I give you instructions like this:
You’ve just drawn a square. What a good turtle you are.
Credit: Valiant Technology Ltd. (CC BY-SA 3.0)
If we associate symbols in our L-system strings with instructions like the ones
above, then a hard-working (virtual) turtle can use those strings to draw pictures. Here is an
example: (Notice that
F produces an empty string. That just means we will
F symbols when we rewrite the string.)
axiom FX X → -FX++FY- Y → +FX--FY+ F →
Now if the turtle interprets the symbol
F to mean “move forward
1 step with pen down”, the symbol
- to mean
“turn right 45°” and the symbol
+ to mean “turn left 45°” then the order 8
string of this system will make the turtle draw this picture:
If you are interested in fractals, you may recognize this as a dragon curve. Pretty neat, but it still doesn’t give us much insight into how plants grow! For that we need to extend the turtle’s capabilities a little. To see why, it is useful to consider this rule for drawing a simple tree:
To draw a tree, draw a trunk with two shorter trees coming out of the top at right angles to each other.
Notice that this definition is self-referential or recursive: part of a tree is two shorter trees! How can we make any sense of that? One step at a time. Start by drawing a trunk: a straight vertical line. Now since a tree has “two shorter trees coming out” of the trunk, start off those trees by drawing two shorter trunks to make a Y shape. But don’t stop there. Since each branch of the Y is the trunk of a new tree, you need to add two shorter trunks to them as well. And since each of those new branches is also the start of a tree, they need trunks… you can continue as many times as you like, each time extending the tree a little in the same way that the next string in an L-system builds on the previous one. After the first few steps, your tree should have progressed through these stages:
And if you keep on going you will end up with something like this:
Which is indeed rather tree-like! So, what new capabilities does our turtle
need to recreate this process? The recursion is no problem: in fact, all
of the L-systems above use recursion! It just means that a symbol on the
left-hand side of a production rule also appears somewhere in the that rule's
right-hand expansion (either immediately or in a later order).
One thing that’s missing is changing the turtle’s step
size so we can make shorter trees on top of our trunks. No problem,
we can add a new symbol,
@, for that.
(You can optionally follow
@ with a number
that you want to mulitply the step size by.)
We will also need a way to give the turtle some kind of memory. Now this one is a little trickier! We need a memory in order to create the two branches: after we draw the first branch, we need a way to get back to where we started so we can draw the second one.
The turtle’s memory will be controlled with two new symbols:
[ symbol tells the turtle
to write down its current state on a note and put that note on top
of a special note stack. The
] symbol tells the turtle to take the
top note off the stack and go back to the same state that is written there.
(The turtle’s state includes its position, direction, step size, and other information:
anything that would change how it draws a line.)
Now, actual plants don’t have a memory, of course, but we only have one
turtle to draw the whole tree. On a real plant each branch starts growing
from a bud that is effectively a new turtle just for that branch. In fact, you might
find it helpful to think of
] as representing
a bud, and everything between those symbols as what grows from it.
Whew! Putting this all together, we can finally recreate our simple tree as an L-system:
axiom FX X → @[+FX][-FX]
Let’s look at each symbol in turn: The axiom is
a line for the trunk) followed by
X (a placeholder that will
be replaced by “two shorter trees”). The production will rewrite the
@ (make the step size shorter),
[ (start a new branch),
+ (turn left 45°),
FX (a new trunk and tree placeholder),
] (finish the branch and go back to where it started),
[ (start a second new branch),
- (turn right 45°),
FX (the second new tree),
] (finish the second branch).
The turtle instructions are an exact analogue of our tree-drawing rule!
By the way, the second
] in that production
are not actually necessary. You will get the same series of drawings with
@[+FX]-FX. I leave it an as exercise for you to figure out why.
Now you are ready to go back to the app and explore more examples or try creating systems
of your own. There are just a couple of things to note: First, when defining a
production, the app uses
= instead of
a lot easier to type!). And second, by default, the turtle will turn in 45° increments.
To change that add a line like this:
where n is the number of turns that should make up a complete circle.
(There are more commands, but that’s enough to get started. When you are ready,
a complete list of them follows below.)
Happy string rewriting!
The commands used by the app have been chosen to be mostly compatible with the fractal software Fractint, though the two systems are not identical. One difference of note is that this system is case sensitive, while Fractint is not.
||Lines that start with a ; are considered comments and are ignored by the computer.|
|Sets the number of turns that make up a complete circle to n. (Each turn will be by 360°/n.)|
|The entire drawing will be rotated by n°. The turtle normally begins pointing to the right.
For example, to start with the turtle pointing up, use
|For the included examples, this sets the initial order used when the system is selected from the list.|
|Provides a hint as to whether the drawing should favour quality or speed. (The exact effect depends on the browser, but the low quality setting typically has no antialiasing.)|
||The string s to use for order 0.|
||When a string is being rewritten, every instance of the letter p will be replaced by string s. The right hand side can be empty, which removes the left-hand letter from the new string.|
||Moves the turtle forward 1 step with the pen down, drawing a line.|
||Moves the turtle forward 1 step with the pen up, leaving no mark.|
||Turns the turtle “left” one notch without moving. The amount of the turn is determined by
||Turns the turtle “right” one notch without moving.|
||Switches the meaning of “left” and “right”.|
||Turns the turtle around (as close to 180° as the
||Multiplies the turtle’s step length by n, changing the distance
moved by each
||Adds the current turtle state to the stack. The current position, angle, step length, colour, and whether left and right are reversed are all recorded.|
||Takes the turtle state off the top of the stack, returning the turtle to
the same state it was in when the most recent
|Pen colours (see below)|
||Changes to the pen colour that is n steps after the current colour. If no number follows the symbol, the colour changes by 1 step.|
||Changes to the pen colour that is n steps before the current colour. If no number follows the symbol, the colour changes by 1 step.|
||Changes to the pen colour to the nth pen in the colour palette. If no number is given, changes to pen 0 (the starting colour).|
The turtle has a palette of 256 different coloured pens. The palette has been
chosen to let you draw a wide variety of designs with nice results. It
blends smoothly from brown to green, cyan, blue, indigo, violet, red, orange, pale yellow, and
finally back to brown. Using
you can move through the palette in either direction; if you move past the
first or last colour, you will wrap back around to the other end of the palette.
256 (same as 0)