Using Lindenmayer Systems to Introduce Computer Science Concepts
- How can the growth of a plant be formally described?
- How can a computer be used to model these growth patterns?
- What are the connections to the Ontario Computer Studies curriculum?
Shared by Russell Gordon (@rgordon)
CEMC Summer Institute for Computer Studies Educators
Thursday, August 17, 2017
Outline for Today's Session
- L-system theory
- Apply theory on paper
- Examples of student work
- Implementation in language of your choice
- Discuss curricular connections
- Share our creations
Contents
Background
Hollywood movies are increasingly saturated with computer-generated images, or CGI. Pixar has become a household name. How, though, is such realistic imagery produced?
In 1968, Aristid Lindenmayer, a botanist, developed a system for modelling the growth of plants.
Lindenmayer systems, or L-systems, have an alphabet of acceptable characters.
An axiom, composed of characters from the alphabet, describes the initial state of the system.
Production rules are applied to the axiom to produce a new word.
Each character in a word carries a specific meaning that a computer can use to render an image. (Imagine a metaphorical turtle on the screen, responding to the meaning of each character.)
L-system Theory
Alphabet
Here is the alphabet for a small L-system:
| Character | Meaning |
|---|---|
| F | go forward and draw a line |
| B | go forward and draw a line |
| + | rotate left by 60 degrees |
| - | rotate right by 60 degrees |
| [ | start branch, remember where this branch started |
| ] | end branch, return to where this branch started |
Axiom
The axiom for this system is:
FFF[+B][-B]
It would be rendered like so:
A rendering of the axiom for the L-system described above.
Each character from the axiom has been added to the drawing to clarify the movement of the "turtle" on screen.
This can be considered generation 0 of the drawing.
Production Rules
The following production rules are applied to the axiom.
Each character in the axiom is matched to a predecessor.
In the resulting word, the predecessor is replaced with the successor:
| Production Rules | |
|---|---|
| Predecessor | Successor |
| F | F |
| B | FF[+B][-B] |
Generation 1
After the production rules are applied to the axiom, the resulting word is:
FFF[+FF[+B][-B]][-FF[+B][-B]]
It would be rendered like this:
A rendering of the word for the L-system, after production rules are applied to the axiom to produce a new word. This can be considered generation 1 of the drawing.
Generation 2
In L-systems, production rules can be applied one or more times. This is an example of recursion, an important concept in computer science.
If the production rules are applied to the word from generation 1 of the drawing, the new word is:
FFF[+FF[+FF[+B][-B]][-FF[+B][-B]]][-FF[+FF[+B][-B]][-FF[+B][-B]]]
The resulting image for generation 2 is:
A rendering of the word for the L-system, in generation 2.
Apply the Theory
Now that we've discussed L-system theory, let's try applying it with an exercise.
If you're in this session, I'm distributing paper copies of the exercise now.
If you're reading this online, you can download the exercise. You can download the same exercise in Pages or Word formats, too.
Stochastic L-systems
An L-system is deterministic when it always produces the same output.
Deterministic L-systems do not produce very "natural-looking" results.
After learning the basics with deterministic L-systems, my students worked to create stochastic L-systems that produce different output each time the program runs.
For example, Student D's work below, evocative of a tumbleweed, demonstrates the stochastic nature of her L-system:
| First time program was run | Generation 1 | Generation 2 | Generation 3 | Generation 4 |
|---|---|---|---|---|
 |
 |
 |
 |
|
| Second time program was run | Generation 1 | Generation 2 | Generation 3 | Generation 4 |
| 
| 
| 
|
Stochastic L-systems work by using random numbers, and assigning a probability to each production rule.
Here is the alphabet for Student D's system, illustrated above:
| Character | Meaning |
|---|---|
| F | go forward and draw a line |
| X | go forward and draw a line |
| + | rotate left by 25 degrees |
| - | rotate right by 25 degrees |
| [ | start branch, remember where this branch started |
| ] | end branch, return to where this branch started |
The axiom for her system is:
FFFX
The production rules are:
| Production Rules | ||
|---|---|---|
| Predecessor | Successor | Probability of being applied |
| F | F-F[1+F]F[2-F] | 33% |
| F | F[1+FF]F[--F] | 33% |
| F | FF[1++F]FF[2-F] | 34% |
| X | F-F[3++F]F[1-F] | 100% |
In other words, when an "F" character is found in the axiom (or an existing word) the first two successors for "F" have an equal probability of being applied, where the third successor for "F" has a slightly higher probability of being applied.
When an "X" character is found, it will always be replaced with the successor shown.
The numeric characters noted in the production rules are used to change the colour that successive line segments will be drawn in.
Individual Student Products
Each student created one modified L-system, based on an existing work found from a secondary source.
Each student also created a completely original L-system.
Below, output examples for each student's original L-system is shown.
When an L-system is stochastic, two examples of output are displayed for comparison.
Student A
| First run output | Second run output |
|---|---|
 |
 |
Student B
| First run output | Second run output |
|---|---|
 |
 |
Student C
| Output |
|---|
 |
Student D
| First run output | Second run output |
|---|---|
 |
 |
Student E
| Output |
|---|
 |
Student F
| First run output | Second run output |
|---|---|
 |
 |
Student G
| First run output | Second run output |
|---|---|
 |
 |
Student H
| First run output | Second run output |
|---|---|
 |
 |
Student I
| First run output | Second run output |
|---|---|
 |
 |
Student J
| Output |
|---|
 |
In a student's words: Evolution of my original L-system
To encourage risk taking and maximize learning for all students, I have been trying to value the process a student employs as much, and sometimes more than, their product(s).
One approach that I have found useful is to have a student document their thinking as they work toward a product.
So long as the student can show what they have learned by describing their process, it is possible for a student to meet or exceed expectations on a given task.
Below, Student J describes her process in creating an original L-system.
| Current image | Description and thoughts |
|---|---|
 |
I came up with this L-system when we were experimenting with making our own L-systems. When I turned it to grow in the direction of 0 degrees (which is to the right), I found that it kind of looked like a palm tree leaf. Number of image generations (word re-writes): 4 Rotation angle: 20 Axiom: F Production rule: F = F[-F]F[-F] |
 |
I decided that I wanted to make a palm tree for my original L-system after producing the image above. To make a palm tree, I needed to put more leafs. At first, I thought that I would have to put many L-systems with the same rule and axiom together around an origin to create the top of my tree. However, after some explanation and guidance, I found that I could use the square brackets to place a leaf as a branch. This way all the leaves could be drawn and all of them would be unaffected by each other. These are the parameters that I came up with at this point — I changed the rotation angle because I thought it helped to make the L-system look more like a palm leaf. Number of image generations (word re-writes): 4 Rotation angle: 15 Axiom: [++++++F][------F]F Production rule: F = F[-F]F[-F] |
 |
The problem with what I came up with in the previous step was that the palm leaf on the left was pointing up, but I needed it to point down. I fixed this problem by using a different character, X, for the left leaf and using the same rule for it [ but with the angle of rotation in the opposite direction ]. I also added colour at this point. Number of image generations (word re-writes): 4 Rotation angle: 15 Axiom: [++++++X][------F]F Production rules: X = X[+X]X[+X] F = F[-F]F[-F] |
 |
After I had found out how to add multiple palm tree leafs, I added in more to create the top of the palm tree. These are the parameters that I came up with at this point: Number of image generations (word re-writes): 4 Rotation angle: 15 Axiom: [++++++X][------F][+++X][---F][+X][-F][+++++X][-----F][------T]F Production Rules: X = X[+X]X[+X] F = F[-F]F[-F] |
 |
After I had created the top of my palm tree, I needed to add a trunk. I decided to do this by adding in a branch with the character "T". The rule for T was going to be a completely drawn trunk out of shapes. After experimenting with shapes, I found that triangles worked best to make the trunk. Number of image generations (word re-writes): 4 Rotation angle: 15 Axiom: [++++++X][------F][+++X][---F][+X][-F][+++++X][-----F]F[------T] Production rules: X = X[+X]X[+X] F = F[-F]F[-F] T = T |
 |
After testing my idea in the previous step, I found that tree trunk was drawing too far up. I tried to fix this by changing the production rule for X, but it did not work. So, I decided to look at my axiom and found that I had put the trunk to draw after the final F without the square brackets — this is the F that draws the palm leaf at the top of the tree. This meant that the turtle was at the top of the tree and so would draw the trunk there as well. I changed the axiom so that the trunk was drawing before the F without square brackets and found success! Number of image generations (word re-writes): 4 Rotation angle: 15 Axiom: [++++++X][------F][+++X][---F][+X][-F][+++++X][-----F][------T]F Rules: X = X[+X]X[+X] F = F[-F]F[-F] T = T |
Student K
| First run output | Second run output |
|---|---|
 |
 |
Student L
| First run output | Second run output |
|---|---|
 |
 |
Collaborative Student Products
If you ask students to create a couple of L-systems each, at the conclusion of that assignment, you will have a wide variety of plant-like forms.
A fun extension can be to ask students to create a combined scene using each other's L-systems.
Depending on how you choose to approach curriculum, and what course you are using L-systems in, there is clear potential here to make use of object-oriented programming concepts, as well as project management and source control software.
So, I asked students to create a combined "naturalistic image" that made use of as many different plant-like forms as possible.
At various checkpoints, students conducted critique sessions as a large group. Specific, kind, and helpful feedback was shared so that each student could extend and improve their individual work.
What follows are a few examples of combined sketches that demonstrate:
- effective use of mathematical functions to control the placement of many instances of plant-like forms on a Cartesian plane
- good use of size variation to create a sense of depth
- creative use of shapes to suggest the existence of additional forms, such as mountains or bridges
Student H
Note the many small instances of plants on the hills.
Those plant instances were placed on the Cartesian plane of the image through the use of quadratic functions.
Student B
Student B's combined image makes nice use of variation in the size of plant instances to create the illusion of depth.
Student D
In this image, Student D has used additional shapes, such as triangles, to create mountain-like forms.
In a student's words: Evolution of my combined landscape scene
| Current image | Description and thoughts |
|---|---|
 |
I first chose to start with the template provided because I like how the scaling decreased in order to create depth in the drawing. |
 |
I replaced the line of trees with some small plants. Then I added the vines/tumbleweeds along the bottom by slightly modifying the example array code so that the plant would only be repeated on the x-axis. After I thought it would look nice to add some flowers to the corner with similar looking grass below it. |
 |
The ground was looking plain, so I decided to draw some mountains, using triangles. I placed the third point of the triangles off of canvas to make the mountains look more stretched out and natural. |
 |
I added another line of trees, this time they are taller to accompany the smaller plants around their base. The x and y placement for the two lines of plants are the same, except the x value for the new plants are a little lower to make sure that the plants are not on top of each other. On the bottom of the drawing I also wanted to add some greenery since the trees looked very dry and desert-like. |
 |
Since all the trees were so short I also wanted to draw big trees, so I added another line of trees using the same points as the others, but again just changing the x value a little bit. All the lines of trees were looking so repetitive so I added another line that went up the mountain. I was also starting to experiment with changing the number of image generations for the flower. |
 |
The big green trees were too big, merging with each other and covering one of the mountains, so I experimented with dividing their scale until the branches were spaced out nicely. After experimenting with the flowers I decided to replace them with the greenery on the bottom because it had very small detailed pieces, similar to the vines/ tumbleweeds. |
 |
Last I realized how bare the mountain was looking, so I placed the trees all over the mountain to try and also add a field of depth to the mountain. Then I added a palm tree onto the horizon because let's face it, who doesn't love palm trees! |
Animations
A further extension is to ask students to try rendering the L-systems not just as a static image, but on a symbol-by-symbol basis.
In other words, once a given L-system has had it's word re-written the required number of times, set the renderer up to show each individual symbol being rendered on-screen.
For additional challenge, have students render multiple individual L-systems in parallel on screen.
Examples of student work with animation are below; click the image to view a video of each rendering.
Student M
A student renders multiple stochastic L-systems in parallel.
Student N
Student N renders a classic fractal image.
Student N uses stochastic L-systems, rendered in parallel, to create a 'dark and stormy night' scene.
Student O
This student worked hard to develop his own version of a stochastic L-system that resembles a palm tree.
Implementation
The bulk of our time together today will be spent digging in to L-system concepts and looking at implementations in code.
I suggest that we group up based on the language we use with our students.
You can download this set of L-systems to work from as you produce an implementation. You can download the same exercise in Pages or Word formats, too.
References
Prusinkiewicz, Przemyslaw, and Aristid Lindenmayer. The Algorithmic Beauty of Plants. New York: Springer-Verlag, 1990. Print.
Shiffman, Daniel. "The Nature of Code." The Nature of Code. N.p., 6 Dec. 2012. Web. 14 July 2014. <http://natureofcode.com>.