4. Turtle Drawing and Strings (LSystems)¶
Quick Overview of Day
Turtle drawing by interpreting strings. LSystems to generate strings. Draw interesting patterns using LSystem strings.
CS20CP1 Apply various problemsolving strategies to solve programming problems throughout Computer Science 20.
CS20FP1 Utilize different data types, including integer, floating point, Boolean and string, to solve programming problems.
CS20FP2 Investigate how control structures affect program flow.
CS20FP3 Construct and utilize functions to create reusable pieces of code.
4.1. Controlling a Turtle With Strings¶
By combining what we know about moving turtles on the screen, and what we have learned about traversing strings, we can now write a program that controls the movement of a turtle based on a string. For example, the string FF+FFF
might make a turtle:
move forward by some distance twice in a row
turn right by some angle
move forward again
turn left by some angle
move forward twice in a row
To turn a string like FF+FFF
into a set of instructions that our turtle can execute, we need to look at each character of the string, one at a time. We can do this easily with a for loop, as you can see in the following example.
4.1.1. Try This¶
In the code above, try:
changing the instruction string to have the turtle draw a different image
adding three additional possible instruction for the turtle. Any
B
in the string should be interpreted as an instruction to move backwards (by the same amount asF
moves forward). AU
should cause the turtle to pick up it’s pen (so it doesn’t draw as it moves). AD
should cause the turtle should put down it’s pen (so that it draws as it moves).increasing the speed of the turtle
After completing the tasks above, try having the turtle use the following instruction string: UBBBBBBDFF++FFFF++FF++FF++FFFF++FF
4.2. Turtles and Strings and LSystems¶
This section describes a much more interesting example of string iteration and the accumulator pattern. Even though it seems like we are doing something that is much more complex, the basic processing is the same as was shown in the previous sections.
In 1968 Aristid Lindenmayer, a biologist, invented a formal system that provides a mathematical description of plant growth known as an Lsystem. Lsystems were designed to model the growth of biological systems. You can think of Lsystems as containing the instructions for how a single cell can grow into a complex organism. Lsystems can be used to specify the rules for all kinds of interesting patterns. In our case, we are going to use them to specify the rules for drawing pictures.
The rules of an Lsystem are really a set of instructions for transforming one string into a new string. After a number of these string transformations are complete, the string contains a set of instructions. Our plan is to let these instructions direct a turtle as it draws a picture.
To begin, we will look at an example set of rules:
Axiom 
A 
Rule 1 Change A to B 
A → B 
Rule 2 Change B to AB 
B → AB 
Each rule set contains an axiom which represents the starting point in the transformations that will follow. The rules are of the form:
left hand side → right hand side
where the left hand side is a single symbol and the right hand side is a sequence of symbols. You can think of both sides as being simple strings. The way the rules are used is to replace occurrences of the left hand side with the corresponding right hand side.
Now let’s look at these simple rules in action, starting with the string A:
A
B Apply Rule 1 (A is replaced by B)
AB Apply Rule 2 (B is replaced by AB)
BAB Apply Rule 1 to A then Rule 2 to B
ABBAB Apply Rule 2 to B, Rule 1 to A, and Rule 2 to B
Notice that each line represents a new transformation for entire string. Each character that matches a lefthand side of a rule in the original has been replaced by the corresponding righthand side of that same rule. After doing the replacement for each character in the original, we have one transformation.
So how would we encode these rules in a Python program? There are a couple of very important things to note here:
Rules are very much like if statements.
We are going to start with a string and iterate over each of its characters.
As we apply the rules to one string we leave that string alone and create a brand new string using the accumulator pattern. When we are all done with the original we replace it with the new string.
Let’s look at a simple Python program that implements the example set of rules described above.
Try running the example above with different values for the number_of_iterations
parameter. You should see that for values 1, 2, 3, and 4, the strings generated follow the
example above exactly.
One of the nice things about the program above is that if you want to
implement a different set of rules, you don’t need to rewrite the entire
program. All you need to do is rewrite the apply_rules
function.
Note
Suppose you had the following rules:
Axiom 
A 
Rule 1 Change A to BAB 
A → BAB 
What kind of a string would these rules create? Modify the program above to implement the rule.
4.3. Drawing With LSystems¶
Now let’s look at a real Lsystem that implements a famous drawing. This Lsystem has just one rule:
Axiom 
F 
Rule 1 
F → FF++FF 
This Lsystem uses symbols that will have special meaning when we use them later with the turtle to draw a picture.
F 
Go forward by some number of units 
B 
Go backward by some number of units 
 
Turn left by some degrees 
+ 
Turn right by some degrees 
Here is the apply_rules
function for this Lsystem.
def apply_rules(letter):
"""Apply rules to an individual letter, and return the result."""
# Rule 1
if letter == 'F':
new_string = 'FF++FF'
# no rules apply so keep the character
else:
new_string = letter
return new_string
Pretty simple so far. As you can imagine this string will get pretty long with a few applications of the rules. You might try to expand the string a couple of times on your own just to see.
The last step is to take the final string and turn it into a picture. Let’s
assume that we are always going to go forward or backward by 5 units. In
addition we will also assume that when the turtle turns left or right we’ll
turn by 60 degrees. Now look at the string FF++FF
. This is the string we used to draw a simple image at the start of this section! At this point its not a very exciting
drawing, but once we expand it a few times it will get a lot more interesting.
To create a Python function to draw a string we will write a function called
draw_l_system
The function will take four parameters:
A turtle to do the drawing
An expanded string that contains the results of expanding the rules above.
An angle to turn
A distance to move forward or backward
def draw_l_system(some_turtle, instructions, angle, distance):
for task in instructions:
if task == 'F':
some_turtle.forward(distance)
elif task == 'B':
some_turtle.backward(distance)
elif task == '+':
some_turtle.right(angle)
elif task == '':
some_turtle.left(angle)
Here is the complete program, which combines generating the LSystem string, and then using it to draw with the turtle.
Note
Try some different angles and segment lengths to see how the drawing changes. Start with 90 degrees, and experiment from there. You might want to use Thonny when experimenting, since Thonny makes it easy to end a program at any point. Using window.tracer(10)
will also greatly speed up your programs.
4.4. Practice Problems¶
Adapt the template code given above to create drawings of other famous LSystems.
4.4.1. Hilbert Curve¶
Use the following axiom and rules to create the Hilbert curve.
Angle 
90 degrees 
Axiom 

Rule 1 
L → 
Rule 2 
R → 
4.4.2. Dragon Curve¶
Use the following axiom and rules to create the dragon curve.
Angle 
90 degrees 
Axiom 

Rule 1 
X → 
Rule 2 
Y → 
4.4.3. Arrowhead Curve¶
Use the following axiom and rules to create the arrowhead curve.
Angle 
60 degrees 
Axiom 

Rule 1 
X → 
Rule 2 
Y → 
4.4.4. PeanoGosper Curve¶
Use the following axiom and rules to create the PeanoGosper curve.
Angle 
60 degrees 
Axiom 

Rule 1 
X → 
Rule 2 
Y → 
4.4.5. Sierpinski Triangle¶
Use the following axiom and rules to create the Sierpinski Triangle.
Angle 
60 degrees 
Axiom 

Rule 1 
F → 
Rule 2 
X → 
4.4.6. Snowflake¶
Use the following axiom and rules to create a snowflake shape.
Angle 
72 degrees 
Axiom 

Rule 1 
F → 
4.4.7. Unnamed Shape¶
If you know the name of this shape, please tell me!
Use the following axiom and rules to create an interesting shape.
Angle 
45 degrees 
Axiom 

Rule 1 
L → 
Rule 2 
R → 
4.4.8. Making Your Own Shapes¶
Note
If you have experimented with all of the shapes above, and are thinking about creating your own, look for symmetry in the rules given above…