Overview
As a biologist, Aristid Lindenmayer studied growth patterns various types of algae.
In 1968 he developed Lindenmayer systems (or L-systems) as a mathematical
formalism for describing the growth of simple multicellular organisms.
More recently, L-systems have found several applications
in computer graphics. Two principal areas include generation of fractals and
realistic modeling of plants.
Basically, a Lindenmayer system begins with a string of symbols called the axiom, and applies to the axiom a set of production rules which are used to rewrite the axiom.
For example, let the axiom of a Lindenmayer system be the string of three symbols 'peg', and let the set of production rules be the single rule: 'e=i'. This is summarized in the following table:
axiom: | peg |
rules: | e = i |
When the rule is applied to the axiom, each 'e' symbols in the axiom is replaced with an 'i' symbol. Thus, the axiom 'peg' becomes 'pig'. This new string 'pig' is called the first generation of the L-system since it is the result of applying the rules to the axiom one time.
The second generation of this L-system is the result of applying the rules to the first generation. Since there are no 'e' symbols in the first generation, there is nothing for the rule to replace. Thus the second generation is also the string 'pig'. This rather boring L-system is summarized below:
Boring L-System | |
axiom: | peg |
rules: | e = i |
generation 1: | pig |
generation 2: | pig |
generation 3: | pig |
L-systems are more interesting when the rules are recursive. A recursive rule is a rule that replaces a symbol with a copy of itself plus something extra. An example of a recursive rule is 'e = eie'. The table below shows the first three generations of an L-system with this recursive rule:
Recursive L-System | |
axiom: | peg |
rules: | e = eie |
generation 1: | peieg |
generation 2: | peieieieg |
generation 3: | peieieieieieieieg |
In the first generation, the single 'e' symbol in the axiom was replaced with 'eie' creating the string 'peieg'. Since the rule in this L-system is recursive, the first generation string has two new 'e' symbols, each of which get replaced with 'eie' in the second generation...and so it goes.
The next section summarizes the definition of an L-system more formally.
The most common graphical interpretation applied to L-Systems is based on turtle graphics which is the best known future of the Logo programming language. Logo was invented in 1967 by Wally Feurzeig and Seymorur Papert as a kid friendly way of teaching computer science. The turtle in turtle graphics is an on-screen cursor (or on-floor robot) which can be given drawing (or movement) instructions such as move forward by a specified distance or turn right or left by a specified angle. Traditionally the cursor in turtle graphics is represented pictorially as a turtle icon.
When applying turtle graphics to L-systems, a state of the turtle is defined as a quadruple (x, y, a, c). The Cartesian coordinates (x, y) represent the turtle's position. The angle a, called the heading, is interpreted as the direction in which the turtle is facing. The color c is interpreted as the color pen that the turtle currently has pressed to the floor so that any movement of the turtle will create a line of that color. Given the step size d and the angle increment b, the turtle can respond to symbols in an L-system string according to the following instructions:
f | Move forward (in the direction of the current heading) a distance
d while drawing a line of color c.
The state of the turtle changes to (x', y', a, c), where x' = x + d cos(a) and y' = y + d sin(a). |
h | Same as f. |
g | Same as f except no line is drawn. |
! | Like the f and h symbols, the ! symbol moves the turtle forward. Unlike the f and h symbols, the distance that
the ! symbol moves the turtle is a function of the symbol's age.
The ! symbol is a constant, so once it is added to a string,
it remains in the string for all future generations. The color of the ! symbol is also a function of its age. The default color scheme causes new ! symbols to draw in light greens. Older ! symbols are drawn with darker greens and the oldest ! symbols are drawn in browns.
The state of the turtle changes to |
+ | Turn right by angle b. The next state of the turtle becomes (x', y', a+b, c). |
- | Turn left by angle b. The next state of the turtle becomes (x', y', a-b, c). |
[ | Save the current state of the turtle by pushing it onto a stack. |
] | Restore the turtle to the state of the last ] by popping the state from a stack. |
a | Change the color of the turtle to color a. |
b | Change the color of the turtle to color b. |
c | Change the color of the turtle to color c. |
d | Change the color of the turtle to color d. |
e | Change the color of the turtle to color e. |
Some of the presets in the Fractal Grower software use other symbols such as x, y and z. While these symbols are ignored by the turtle, they are still useful in the L-system grammar for building string structures containing symbols not ignored by the turtle.
Note on color: the variables 'a' through 'e' only effect the color when the 'color f and h segments by imbedded variables' radio button is selected on the color tab of the L-System control panel. If this radio button is not selected, then the turtle ignores the 'a' through 'e' symbols, and the color of each line segment is determined by the location of each f or h in the string: f and h symbols at the beginning of the string draw red segments, in the middle of the string draw green segments, and at the end of the string draw purple segments.
Note on step length: In L-systems that do not use the '!' symbol, the step length has no effect on the appearance of drawing. This is because, all 'f' and 'h' symbols are drawn with the same step length, then the complete drawing is scaled so as to fill the drawing window. A large step size will just cause the software to scale down the final drawing more. However, when the '!' is used, then the step length has a great effect on the drawing since 'f' and 'h' symbols always move forward a distance equal to the step length whereas '!' symbols move forward a distance equal to the step length raised to the power equal to the symbol's age.
The dragon curve is one such fractal, and its finite approximation can be created with an L-System:
Dragon Curve L-System | |
variables: | f h |
constants: | + - |
axiom: | f |
rules: | f = f-h h = f+h |
angle increment: | 90 degrees |
generation 1: | f-h |
generation 2: | f-h - f+h |
generation 3: | f-h - f+h - f-h + f+h |
generation 4: | f-h - f+h - f-h + f+h - f-h - f+h + f-h + f+h |
This L-System has two rules: one for replacing 'f' symbols and one for replacing 'h' symbols. Therefore, both 'f' and 'g' are variables of the L-System. The '+' and '-' symbols are considered constants because there are no rules in the system for replacing these two symbols. The axiom of the system is a single 'f' symbol. Therefore, when creating the first generation, the rule for replacing 'h' symbols is not used.
The red and green colors in the table help make the substitution process easier to perceive. At each generation, the new symbols that result from replacing an 'f' symbol are shown in green, and the new symbols that result from replacing an 'h' symbol are shown in red. Each symbol that is more then one generation old is shown in black. Only constants can be more then one generation old, because variables are always replaced at each generation. Only some of the '+' and '-' symbols are shown in black because only these are more then one generation old.
Let's take a step by step examination of the second generation of this L-System.
The generation 2 string is:
'f - h -
f + h'.
Assuming that the initial heading of the turtle is upward on the screen, then the
first 'f' will draw a line straight up. The '-' causes the
turtle to change its heading by 90 degrees to be pointed directly to the left.
The 'h' draws a line directly to the left of the screen.
The second '-' symbol again turns the turtle 90 degrees to its left which is directly down
on the screen. The f symbol draws a unit length line in
the down direction. The last turn symbol in the string is a '+' which turns the turtle to
its right by 90 degrees. However, since current heading of the turtle is pointed downward,
its right is the screen's left, so again the turtle's heading is to the left of the screen.
Finally, the h symbol draws a unit length line to the
screen's left. The resulting image is shown is figure 1 with line segment colors
matching the 'f' and 'h' colors in the description above.