July 29 2017
Visualization Morphogenesis Strings Languages STEM

Lindenmayer systems

Natural processes as computation

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.

Introduction

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!

  

Examples

How L-systems work

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 that 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.

Ordered L-systems

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 Y with XYX, or you can replace the Y and the following X with 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:

  1. the left hand side of a production can only be a single letter; and
  2. no two productions can have the same left-hand side.

The rest of this article deals exclusively with d0L-systems. Don’t feel cheated—they still offer lots of possibilities.

From strings to nature

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 B, A, AB, ABA, ABAAB, ABAABABA, ABAABABAABAAB and 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 (phyllotaxis).

Enter the turtle

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:

  1. Touch the pen to the paper.
  2. Move forward 1 step, turn left 90°.
  3. Move forward 1 step, turn left 90°
  4. Move forward 1 step, turn left 90°
  5. Move forward 1 step.

You’ve just drawn a square. What a good turtle you are.

Photo of a turtle robot that has made a design on a sheet of paper

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 delete any 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:

Trees and branches

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: [ and ]. The [ 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 [ and ] 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 F (draw a line for the trunk) followed by X (a placeholder that will be replaced by “two shorter trees”). The production will rewrite the X as @ (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 [ and ] 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.

Playtime!

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 (it’s a lot easier to type!). And second, by default, the turtle will turn in 45° increments. To change that add a line like this: angle n, 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!

Command reference

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.

Preamble directives

Commands that affect how systems are drawn
Command Effect
; ... Lines that start with a ; are considered comments and are ignored by the computer.
angle n or
turns n
Default: 8
Sets the number of turns that make up a complete circle to n. (Each turn will be by 360°/n.)
rotate n
Default: 0
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 rotate 90.
order n
Default: 4
For the included examples, this sets the initial order used when the system is selected from the list.
quality low|high
Default: high
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.)

Productions

Commands that determine which d0L-system is produced
Command Effect
axiom s The string s to use for order 0.
p = s 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.

Drawing

Symbols that have special meaning to the turtle when drawing a string
Symbol Effect
F Moves the turtle forward 1 step with the pen down, drawing a line.
G Moves the turtle forward 1 step with the pen up, leaving no mark.
Turning
+ Turns the turtle “left” one notch without moving. The amount of the turn is determined by angle.
- 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 angle value allows).
Line length
@n Multiplies the turtle’s step length by n, changing the distance moved by each F or G command. If no number is given, the length is multipled by 0.6. The value n may be preceded by the letter I to use 1/n. It may be preceded by Q to use √n.
Branching
[ 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 [ was processed. Note that, like brackets in math, the number of [ and ] symbols in a string should match.
Pen colours (see below)
>n 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.
<n 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.
%n 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).

Colour palette

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 > and < 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.

0

32

64

96

128

160

192

224

256 (same as 0)

Bibliography

  1. Aristid Lindenmayer. Mathematical models for cellular interaction in development. Journal of Theoretical Biology, 18:280–315, 1968.
  2. Prusinkiewicz, Przemysław and Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990.