CS 151: Lab #7

Lab Exercise 7: Strings, Grammars, and Trees

Main course page

The purpose of this lab is to gain familiarity with simple L-system grammars and how we can use them to represent visual shapes. L-systems were designed to allow computer scientists and biologists to model plants and plant development. As with the last few collage labs, we'll represent an L-system as a list of items and enable reading L-systems from a file using a simple syntax.

The fundamental concepts we'll be implementing in the next several labs are based on a set of techniques described in 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 have proven very successful in modeling plant life and form the basis for some commercial plant modeling systems that are used in computer graphics special effects.

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 generating and 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 several 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.

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 as follows.

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.



In this lab we're going to create two files: lsystem.py and interpreter.py. The lsystem file will contain all of the functions necessary to read an lsystem from a file and generate a string from the lsystem rules. The interpeter file will contain the code required to convert a string into a sequence of turtle commands. For the project you'll use both files to create an image that contains shapes built from L-system strings.

  1. Create a working directory for lab 7. Then begin a new python file called lsystem.py. At the top of the file put your name and version 1 as comments.
  2. We're going to start with a test function for the lsystem functions. Import the sys package, then create a function main with argv as its argument. The main function needs the following steps.
    import sys
    def main(argv):
        # get the filename, number of iterations, and output filename from argv
        # assign to a variable (e.g. lsys) the result of createFromFile(filename)
        # assign to a variable the result of buildString(lsys, iterations)
        # open the output file for writing
        # write out the string
        # close the file
    if __name__ == "__main__":

    Finally, put a call to main with sys.argv as its argument inside the usual __name__ conditional test.

  3. If we create placeholder functions for createFromFile and buildString, we can test the code right now. Make a function createFromFile that returns 0 and a function buildString( lsys, iterations) that returns some random string. Then test your code.

  4. There are obviously two functions in the main program we haven't yet built. Let's first write the createFromFile function. Above your main function, create a function createFromFile that takes a filename as an argument. This function should read an L-system's base string and rules from a file, create a data structure to hold the information, and return that data structure.

    The information we need to read from the file is the base string and the set of rules. While we will use only a single rule this week, we need to design our system so it can read in a file with multiple rules.

    We can design our file any way we want. A format that is both human-readable and easy to parse with a program is to have a word at the beginning of the line that indicates what information is on the line and then have the information as the remaining elements of the line. In the case of the base string there will be only a single string, and for a rule there will be two strings (for now).

    An example file is given below

    base F-F-F-F
    rule F FF-F+F-F-FF

    The algorithm for reading the file is to open the file, read the lines of the file, then loop over the lines, putting the information in the appropriate location in the lsystem data structure according to the keyword at the beginning of the line.

    def createFromFile( filename ):
        # open the file, storing the file pointer in a variable
        # read all of the lines in the file
        # close the file
        # call the function init() and assign its output (an empty Lsystem) to lsys
        # for each line 
            # split the line on spaces using the split method
            # if the first word is 'base'
                # set the base of the lsystem using the function setBase
            # else if the first word is 'rule'
                # add the rule to the lsystem using the function addRule
        # return the lsystem list

    Note that we have three functions--init, setBase, and addRule--that we now need to define. Note also that we still have no need to know exactly how we're storing the information in the lsystem data structure.

  5. The init function is the first function that requires us to know how we're going to store the L-system information. The L-system requires two pieces of information: the base string and the list of rules. A simple method of storing this information is in a list with two items; the first item is the base string, the second item is a list of 2-element lists (the rules). For example, the L-system defined in the file above would have the form below in memory.

    ['F-F-F-F', [ [ 'F', 'FF-F+F-F-FF' ] ] ]

    Given this representation, an empty L-system would be a list with two elements: the empty string and an empty list. Have the init function return an empty L-system.

  6. Now we can write the setBase and addRule functions. The setBase function takes in two arguments, an L-system and a base string, and sets the base string field of the L-system list to the new string.

    The addRule function is a little more complex because we need to copy the data from the rule passed into the addRule function. The form of the function is given below.

    def addRule( lsys, newrule ):
        # assign an empty list to a local variable (e.g. rcopy)
        # for each element of newrule
            # append the element to the local copy (rcopy)
        # append the copy (rcopy) to the lsystem's rule list
  7. Now we need to write three more functions and our lsystem.py file will be complete. Make a new function, buildString that takes in two arguments: an lsystem data structure and the number of iterations of replacement to execute.
    def buildString( lsys, iter ):
        # assign to a local variable (e.g. nstring) the result of getBase(lsys)
        # assign to a local variable the result of getRule(lsys, 0)
        # loop iter times
            # assign to nstring, the result of nstring.replace( symbol, replacement )
        # return nstring

    The final piece is to write an accessor getBase that returns the base string of an lsystem structure and an accessor getRule that returns the specified rule of an lsystem structure.

    Download the following two files and test your code.

    First try running systemA with the number of iterations being 1 and see if it creates what you expect. Then set the number of iterations to 3 and save the output for systemA and systemB in separate files.

  8. Create a new file called interpeter.py. Put your name and version 1 at the top in comments. The purpose of this file is to convert a string into an image using simple turtle commands. First, create a test main function for the file that reads in a string from a file and then calls the function drawString.
    import sys
    import turtle
    def main(argv):
        # get the string filename, distance, and angle from argv 
        # open the file
        # assign to a local variable (e.g. lstring) the first line of the file
        # close the file
        # set the turtle tracer to False
        # set the turtle heading to 90
        # call the drawString function with a string, a distance and an angle
        # call the hold() function
    if __name__ == "__main__":
  9. The drawString function is called an interpeter. It converts information in one form into information in another form. In this case, it converts a string of characters into a series of turtle commands.

    The form of the function is to loop through the string and execute a particular action (or nothing) for each character.

    def drawString( dstring, distance, angle ):
        # assign to a local variable (e.g. stack) the empty list
        # for each character c in dstring
            # if c is 'F'
                # go forward by distance
            # else if c is '-'
                # turn right by angle
            # else if c is '+'
                # turn left by angle
            # else if c is '['
                # append to stack the position of the turtle
                # append to stack the heading of the turtle
            # else if c is ']'
                # pick up the turtle pen
                # set the heading of the turtle to the value popped off state
                # set the position of the turtle to the value popped off state
                # put down the turtle pen
        # call turtle.update()
        # return
  10. The function hold() is given below. Copy it and the saveCanvas function and add them to your interpreter.py file. The saveCanvas function takes in either a frameid or a filename and writes out a postscript image of the current turtle canvas.
    def hold():
        turtle.onkey( turtle.bye, 'q' )
    def saveCanvas(frameid=0, filename='' ):
            if filename == '':
                filename = "frame%03d.ps" % frameid

    Now test your interpreter.py program with the strings you created using the lsystem.py file. Use a 90 degree angle for system A and a 22.5 degree angle for system B.

  11. System A System B

Once you have finished the lab, go ahead and get started on project 7.