CS 151: Project #5

Turtles Climbing Trees

For this project we'll be re-working the string interpreter from the last project to conform to a system of characters used by the book 'The Algorithmic Beauty of Plants'. You can download the entire book from the algorithmic botany site, if you're interested in learning more. The algorithms in the book form the basis for some commercial plant modeling systems that are used in computer graphics special effects, for example.

The overall concept of the book is that we can represent real plants and how they grow using strings and rules for manipulating them. The theoretical procedure for manipulating the strings is called an L-system, or Lindenmayer-system.

When modeling plants, we can treat each character in the string as equivalent to a physical aspect of a plant. A forward line is like a stem, and a right or left turn is like a junction where a branch forms and grows outwards. In fact, the whole book uses turtle graphics to create models of plants from strings and rules about how to manipulate the strings.

Fortunately, the past two labs have given you the knowledge to build a system that can implement this idea. This project will walk you through the process of building a system that can create some simple plant models, as well as other interesting geometric shapes. For the most part it is a minor modification of the last program from the prior lab. Don't let the nomenclature or different characters confuse you. All we're doing is converting strings into turtle actions.

An L-system has three parts.

  1. An alphabet of characters
  2. A base string
  3. One or more replacement rules that substitute a new string for a character in the old string.

The characters we're going to use are not much diferent than those we've been using.

F is forward by a certain distance
+ is left by an angle
- is right by an angle
[ is save the turtle state
] is restore the turtle state

To give a concrete example, consider the following L-system:

The way to apply a rule is to simultaneously replace all cases of the left side of the rule in the base string with the right side of the rule. If the process is repeated, the string will continue to grow, as shown below.


The basic algorithm you will implement is as follows:

  1. Read in from a file the L-system description that includes the base string, symbol to be replaced, and the string with which to replace it. The file will also specify the number of times to execute the rule, and parameters governing the distance to move forward for the F symbol and the angle to turn for each + or - symbol.
  2. Iteratively replace the symbol with the rule the number of times specified.
  3. Create a window, process the string using turtle graphics commands, and call turtleWait() to hold the image on-screen.


Fortunately, most of the work for this project has already been done. We'll use the linearC.py program from the last project as the basis for this assignment.

  1. Create a new directory for this project. Put a copy of turtleUtils.py into the directory. Make a copy of the stringfun.py file from the lab session. Call it lsystem.py. Then copy the drawShape() function from your linearC.py file from the last project and paste it into lsystem.py. Modify the drawShape() so that it takes a string instead of a character and uses a for loop to go through the characters of the string. The if-elif-else structure should be inside the for loop.
  2. Download this system file and save it in your working directory. Take a look at it in BBEdit or your editor of choice. It should contain six lines. The first line is the base string. The second line is the symbol for replacement. The third line is the rule with which to replace the symbol. The fourth line is the number of times to execute the replacement rule. The fifth line is the distance to travel for each F symbol, and the last line is the angle to turn left on a + or right on a -.
  3. Your program should already ask the user for a filename, open the file, and then use the readlines() function (note the plural) to read in the lines of the file and put them in a variable. Use a variable name that is meaningful to hold the list of lines. Remember, each line of the file will be a string in the list. It's also important to remember that each of the lines will end in a newline character. You already have code to put the first three lines into variables called base, symbol, and rule.
  4. The fourth line of the file is the number of times to apply the replacement rule. Your program should convert the string corresponding to the fourth line into an integer and store it in the variable N. The fifth line of the file should be converted to an integer and stored in the variable distance. The last line of the file should be converted to a floating point value and stored in the variable angle. As in the lab, print out these values after they have been properly converted and stored. Have the print statements be informative about the meaning of the numbers.
  5. The for loop should build the string you want to process using the replace function. Each time through the for loop you should print out the string in base.
  6. After the for loop, you should send the string in base to the drawShapes function. Modify your drawShapes function so it takes two additional parameters: distance and angle. Then add cases for the characters 'F', '+', and '-'. The character 'F' should go forward by distance, '+' should go left by angle, and '-' should go right by angle.
  7. Run your program for the L-system in the systemA file and see what happens. It should look like the image below when run for 3 interations. Copy the systemA file to another file and try editing the various components and see what happens. There are several interesting systems in the first chapter of the ABOP book. Hand in an image of your simple L-system as scene5A.png
  8. Now we want to implement the proper behavior for the '[' and ']' characters in drawShapes. The left bracket should store the current turtle state (heading and position) and the right bracket should restore it. To do this, create a variable memory (or a name of your choice) at the beginning of your drawShapes function. Initialize it to an empty list.

    Each time we see the left bracket character we want to append the turtle heading and turtle position on the end of the list. The append() method takes an argument and appends it on the end of the list. So the behavior for the left bracket '[' should be two calls to append.

    Each time we see the right bracket character we want to remove the last two elements from the list and use them to reset the position and heading. The pop() method removes the last element from a list and returns it. So the behavior for the right bracket should be:

    1. Raise the turtle pen up
    2. Send the turtle to the location returned by the pop() method
    3. Orient the turtle to the heading returned by the pop() method
    4. Put the turtle pen down
  9. Try out systemB, which should look like

  10. Modify systemB or work with a different L-system (ABOP has many). Hand in an image of a tree/bush/plant as scene5B.png.
  11. In drawShapes, add a case for the character 'L' that draws a very simple leaf (start with a short green line). Don't forget to set the color back to black after drawing the line, and make sure you put the turtle back where it started before you drew the leaf. Add a single L character to the replacement rule in systemB. See what happens. Hand in an image of a tree/bush/plant with leaves as scene5C.png.


Below are some suggested extensions.

  1. Add some randomness to the system (angles and/or distances) using a Gaussian distribution.
  2. Create new L-systems that make interesting pictures.
  3. Add colors or add your shapes to the L-system rules.
  4. Pick anything from ABOP to augment the L-systems and run with it.
  5. Have the program run in a loop and let the user dyanmically enter strings for the base string, symbol, and replacement rule.


Create a web page for your writeup. Your writeup should include the following.

Handing in

When your writeup is ready for viewing and linked to your index page, send me an email.

To hand in your python code, place it on the Academics fileserver in the private folder. Do not post it on the web. You may include snippets from your code in your writeup to demonstrate how certain aspects of the function work, but please do not include the whole thing.

To place the code on the fileserver, go to the server fileserver1 and select the Academics volume. Within that there ought to be a CS151 folder, and within that there should be a folder with your username, and within that ought to be a folder labeled private. You can read and write files to the private directory and I can read them, but no one else can access them. Put your python files in that directory to hand them in. Please organize your files into folders by project.