CS 151: Lab #8

Lab Exercise 8: 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.

F
-F+F-F
--F+F-F+-F+F-F--F+F-F
---F+F-F+-F+F-F--F+F-F+--F+F-F+-F+F-F-Y---F+F-F+-F+F-F--F+F-F

Tasks

In lab you'll implement a three step process to 1) read in a file containing a description of an L-system, 2) iterate the L-system a certain number of times to create a string, 3) interpret the string as a set of turtle graphics commands.

  1. On the Desktop, make a folder called lab8.
  2. Create a new file called lsystem.py. All of the L-system functions will be located in this file. For this lab, represent an L-system as a 5-element list. The first element is the distance to move forward, the second element is the angle to turn left or right, the third element is the number of iterations of string substitution to make, the fourth element is the base string, and the fifth element is the rule.

    The rule field should be a list that contains a list for each rule in the L-system. We will use only single-rule L-systems this week, so the field should be a list that contains a single list with two elements: the symbol and its replacement. For example:

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

    Define a function createEmpty() that takes no arguments and returns a list that has zero in the first three locations, an empty string in the fourth, and an empty list in the fifth.

  3. To make your life easier, at the top of the lsystem.py file define five constants that are mnemonics for the five list indices. For example, the following assigns 0 to the variable LS_DistanceIndex. Creating variables for each of the indices means you don't have to remember which index has which meaning.

    LS_DistanceIndex = 0

  4. Create accessor functions that let you set each field of the list. The functions should be setDistance, setAngle, setIterations, setBase, and setRule. Each function should take an lsystem list as the first argument and a value as the second argument. Note that the first four set functions each take a number or a string (immutable values) so all you have to do is assign the value to the appropriate location in the list.

    The setRule function, however, will take a list as its value argument. You can't just assign the list to the appropriate field, because it would copy the reference to the list, not the actual data in the list. You need to make sure you are copying the actual data (strings) from the source list into the list field storing the L-system rules.

    After the copy step your rule field should be a single two-element list inside a list, as shown above in step 2. It's probably worth writing this out on a piece of paper first to makes sure you understand. You can assume, for this week, that there is only a single rule for an L-system.

    Once you have completed your accessor functions, start python in a Terminal, import your lsystem module and test your accessor functions. Create an empty lsystem using your function, then use the accessor functions to set the fields and make sure the resulting lsystem is correct by printing it out.

  5. Define a function createFromFile( filename ) that takes in the filename of an L-system file, reads the contents, and returns an L-system list. We'll go over how to do this together, but the pseudo-code is below.
    def createFromFile( filename ):
      # open the file
      # read all the lines of the file
      # close the file
      #
      # create an empty Lsystem (use your function)
      # for each line of the file
        # interpret the line and fill in the proper field of the lsystem
      #
      # return the lsystem
    

    Once you have completed this function, start python in a Terminal, import your lsystem module and test the createFromFile function.

  6. Define a function buildString( lsystem ) that takes in an lsystem as its argument and returns the string built by the L-system after the number of iterations specified in the lsystem structure. The algorithm is as follows.
    def buildString( lsystem ):
      # assign the base string to a local variable (e.g. curstring)
      # for the number of iterations
        # assign to curstring the output of the replace method called on curstring
      # return curstring
    
  7. Define a function test() that asks the user for a filename, reads in the L-system from the file, builds the string, asks the user for an output filename, and writes the string to the output file.
    def test():
      # get an input filename from the user with the raw_input() function
      # read in the L-system from the file
      # build the output string
      # get an output filename from the user with the raw_input() function
      # open the output file
      # write out the string
    

    Once you finish the test function, put the following lines at the bottom of the lsystem.py file.

    if __name__ == "__main__":
      test()
    

    Now if you run the file using the command python lsystem.py the test() function will execute. If you import the lsystem.py file into another python file, however, the test() function will not execute.

    Run the file on the following example L-systems.

  8. Create a new file called transformer.py. You will want to import the turtle package into this file.

    In addition, grab the turtle utilities python file and save it in your lab 8 folder. The turtle utilities module contains two useful functions.

    • setup( dx, dy ): creates a turtle window of the specified size. You must call setup before calling any turtle command or you may get two separate windows.
    • wait(): goes into a loop until the user hits cmd-Q to quit.

    Import the turtleUtils package into yoru transformer.py file.

  9. Define a function init(dx, dy) that takes two arguments that describe a window size. The function should call the turtleUtils.setup() function with the window size arguments.
  10. Define a function wait() that calls the turtleUtils.wait() function.
  11. Define a function drawString( distance, angle, string ) that takes in a distance, an angle, and a string and interprets the string into a set of turtle actions. The algorithm is as follows.
    def drawString( distance, angle, string ):
      # create a local variable initialized to an empty list
      # for each character in the string
        # if the character is an F
          # move the turtle forward by distance
        # if the character is a -
          # turn the turtle right by angle
        # if the character is a +
          # turn the turtle left by angle
        # if the character is a [
          # add the turtle's position to the end of the local list
          # add the turtle's heading to the end of the local list
        # if the character is a ]
          # pick up the turtle pen
          # set the heading of the turtle to the last item of the list and remove it
          # set the position of the turtle to the last item of the list and remove it
          # put down the turtle pen
    
  12. In the transformer.py file, write a function test() that asks the user for the name of a file that contains a string, reads the file, creates a turtle window using the init function, draws the string using the drawString function, and then calls the wait function.

    Use the same if statement at the bottom of the file to call the test function when the program is run on the command line. Run your transformer test program using the systemA and systemB L-systems given above.

    System A System B

When you are done with the lab exercises, go ahead and get started on the assignment.