L-Systems: Rewrite a String, Then Let a Turtle Draw It

The idea: rewrite a string, then let a turtle draw it

An L-system (Lindenmayer system, after the biologist Aristid Lindenmayer, 1968) has two halves. The first half only works with text: start from a short string, the axiom, and apply rules such as F → F[+F]F to get a longer string. Do it again and again; each pass is a generation. The second half gives the string a meaning: a turtle reads it one symbol at a time and draws. A one-line rule is enough to grow a plant.

The page has six presets. Rewrite applies the rules once and then draws the new string; Turtle step reads one symbol and says what it did; Draw all reads the rest. The string panel shows the generation before and after, with matching tints: each tinted group below came from the symbol with the same tint above.

Rewriting: every symbol at the same time

One generation replaces all symbols in parallel, not one after the other. A symbol with a rule is replaced by the rule's right side; a symbol without a rule (+, −, [, ]) is copied unchanged. So with F → F[+F]F:

generation 0:  F
generation 1:  F[+F]F
generation 2:  F[+F]F[+F[+F]F]F[+F]F
generation 3:  66 symbols, 27 of them F

This parallel rewriting is the difference from a grammar in a compiler, which replaces one symbol at a time to parse a sentence. In a plant, every cell grows at once, and that is what Lindenmayer wanted to model. Because every F becomes 3 F's, generation n has 3ⁿ lines; the string length is 1 + 5·(3ⁿ − 1)/2, since each F also brings 5 other symbols. (Demo: simple plant F → F[+F]F, rewrite 0 → 4.)

The turtle: forward, turn, push, pop

The turtle has a position (x, y), a heading and a stack. It starts at (0, 0), heading up for the plants and to the right for the curves, and reads the string left to right:

symbol	the turtle
F (and A, B)	moves forward 1 and draws a line
+ / −	turns left / right by the angle δ, without moving
[	pushes its state (x, y, heading) on the stack
]	pops the stack and jumps back to that state, drawing nothing
X, Y	does nothing; these symbols only steer the rewriting

The stack is what makes branches. [ marks the fork, the symbols up to the matching ] draw the side branch, and ] returns to the fork with the old heading. Brackets nest, so a branch can have branches of its own: the stack is as deep as the nesting, which is the same last-in-first-out idea as a stack or the call stack in recursion. The page colours each line by its bracket depth: brown for the trunk, greener for deeper branches. (Demo: the turtle reads F[+F]F, one symbol a step, Demo: generation 2, branches inside branches.)

Plants

The three plant presets are from The Algorithmic Beauty of Plants (Prusinkiewicz and Lindenmayer, 1990), with δ = 25.7° or 22.5°:

preset	axiom	rules	lines at the last generation
Simple plant	F	F → F[+F]F	3⁶ = 729
Bush	F	F → F[+F]F[−F]F	5⁵ = 3 125
Fractal plant	X	X → F−[[X]+X]+F[+FX]−X, F → FF	1 488

In the fractal plant the axiom X draws nothing at all: X is a bud. Each rewrite turns a bud into stems and four new buds, while F → FF makes the old stems twice as long, so older parts of the plant are longer, as in a real one. (Demo: bush F → F[+F]F[−F]F, 0 → 5, Demo: Lindenmayer's fractal plant.)

Curves from the same machine

Without brackets the turtle draws one unbroken path, and the classic fractal curves are short L-systems. The page colours them by position along the path, red at the start to violet at the end, as on Fractal Curves.

curve	axiom	rules	δ
Koch curve	F	F → F+F−−F+F	60°
Sierpinski arrowhead	A	A → B−A−B, B → A+B+A	60°
Dragon curve	FX	X → X+YF+, Y → −FX−Y	90°

The Koch rule is the bump on the middle third written as turtle moves: forward, left 60°, forward, right 120°, forward, left 60°, forward. The arrowhead needs two drawing symbols, A and B, because the copies alternate direction. In the dragon only F draws; X and Y never draw but decide where the next turns go, which is the paper-folding sequence. (Demo: the same machine draws the Koch curve, Demo: dragon curve: X and Y draw nothing.)

How fast the string grows

The number of drawing symbols is multiplied by the same factor every generation: 3 for the simple plant, 5 for the bush, 4 for Koch, 3 for the arrowhead, 2 for the dragon. So the string grows geometrically and the page stops at a few thousand lines, where each line is about a pixel. The view is fitted to each generation, so the picture keeps its size while the lines shrink; it looks almost the same from one generation to the next because it is made of scaled copies of the previous one. Other fractals on this site: the Barnsley fern, a plant drawn by random affine maps instead of rewriting, and the chaos game.

What the page leaves out

Stochastic L-systems (a rule picked at random, so every plant differs), context-sensitive rules (a symbol rewritten by its neighbours), parametric L-systems (F(length) with arithmetic), line width and leaves, 3-D turtles with roll and pitch, Hilbert and Gosper curves as L-systems, and the formal language theory of D0L systems.

References

Prusinkiewicz & Lindenmayer — The Algorithmic Beauty of Plants (free PDF)

Wikipedia — L-system

Wikipedia — Turtle graphics