- How can the growth of a plant be formally described?
- How can a computer be used to model these growth patterns?
- How do we organize our work to create a whole that is greater than the sum of its parts?
In the winter and spring of 2014, the Grade 11 Computer Science class explored these questions.
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.)
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 |
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.
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] |
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.
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.
To write a computer program that generates the words for an L-system based on an axiom and production rules, and to render that result on screen, students in the class developed an understanding of:
An L-system is deterministic when it always produces the same output.
Deterministic L-systems do not produce very "natural-looking" results.
Students in the class worked to create stochastic L-systems that produce different output each time the program runs.
For example, Athena Foo'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 Athena'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 number characters noted in the production rules are used to change the colour that successive line segments will be drawn in.
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.
| First run output | Second run output |
|---|---|
 |
 |
| First run output | Second run output |
|---|---|
 |
 |
| Output |
|---|
 |
| First run output | Second run output |
|---|---|
 |
 |
| Output |
|---|
 |
| First run output | Second run output |
|---|---|
 |
 |
| First run output | Second run output |
|---|---|
 |
 |
| First run output | Second run output |
|---|---|
 |
 |
| First run output | Second run output |
|---|---|
 |
 |
| Output |
|---|
 |
| 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: 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: 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: 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: 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: 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: 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 |
| First run output | Second run output |
|---|---|
 |
 |
| First run output | Second run output |
|---|---|
 |
 |
Having created at least two L-systems each, the Grade 11 Computer Science students had created a wide variety of plant-like forms:
By this point in the school year, students had been using a collaborative source-code control system — GitHub — for some time.
Following an introduction to object-oriented programming principles — students were ready to extend their learning.
Each student was asked to create their own version of 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.
On a technical level, to allow for the creation of these combined scenes, the L-systems that produced each student's plant-like forms had to be separated into individual classes.
One way to think about a class, as a concept in object-oriented programming, is to imagine it as a blueprint. A class can be instantiated to create an object, or instance, based on that blueprint.
In fact, a class can be instantiated as many times as the programmer desires, subject only to the memory limitations of the computer being used.
What follows are a few examples of combined sketches that demonstrate:
Patrica Munro's combined image — 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.
Emily Cho's combined image makes nice use of variation in the size of plant instances to create the illusion of depth.
In this image, Athena Foo has used additional shapes, such as triangles, to create mountain-like forms.
| 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! |
The following overall expectations were addressed and assessed in this project:
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>.