Due: Tuesday, April 4, 2017, 11:59 pm

Strings, Grammars, and Trees

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 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 include in our alphabet 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:

• Alphabet: F, +, -
• Base string: F
• Rule: F -> -F+F-F

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---F+F-F+-F+F-F--F+F-F

Tasks

In this lab we're going to create two files: lsystem.py and turtle_interpreter.py. The lsystem file will contain all of the functions necessary to read an L-system from a file and generate a string from the L-system rules. The turtle_interpreter file will contain the code required to convert a string into a sequence of turtle commands. The two files will be completely separate; the L-system file will not know anything about graphics, and the turtle_interpreter file will not know anything about L-systems. 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 project 7 on your personal volume (e.g. Project7). Then begin a new python file called lsystem.py. At the top of the file put your name and version 1 as comments. We will be editing our L-system file for each of the next 4 weeks, so having a version number at the top of your file will be important.

   The goal is to be able to read an L-system from a file and generate strings defined by the base string and the rules. First, we should examine the necessary components of an L-system and determine how to store them in a variable. 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, an L-system with the base 'F-F-F-F' and a rule 'F' -> 'FF-F+F-F-FF' would have this form in memory:

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

   We will write five functions to make it easy to create an internal representation of an L-system and to make it easy to change or access its components. They will be

   • init(): return an empty L-system
   • setBase(lsys,base): set the value of the base of an L-system
   • addRule(lsys,rule): add a rule to an L-system
   • getBase(lsys): return the base of an L-system
   • getRule(lsys,ruleIdx): return a rule in an L-system

   Since all of the functions in this module will take an L-system list with the above format, let's write a comment at the top describing it. That way, we don't need to include too much detail in all of the docstrings. Take the time right now to add a comment at the top of the file describing the format of the list used to represent an L-system. Here are the details regarding the five functions you need to create:

   1. The init function needs to create an empty L-system and return it. Given this representation, an empty L-system would be a list with two elements: the empty string and an empty list. Write this function.
   2. 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.

        def setBase( lsys, base ):
            """ Set the base of L-system list stored in lsys.
            base is a string """
      

   3. The addRule function also takes in two arguments, an L-system and a rule. It appends the rule to its list of rules.

        def addRule( lsys, newrule ):
            """ Add a rule to the L-system list stored in lsys.
            newrule is a list of 2 strings """
            # append newrule to the L-system's rule list
      

   4. Test the functions we have written by adding the following code to your L-system file

        def main():
            my_lsys = init()
            setBase( my_lsys, 'A' )
            addRule( my_lsys, ['A','AB'] )
            print my_lsys
      				
        if __name__ == '__main__':
            main()
      

      It should print out

        ['A', [['A', 'AB']]]
      

   5. The getBase function takes in just one argument -- the L-system. It returns the base string.

        def getBase( lsys ):
            """ Return the base string of this L-system """
      

   6. The getRule functions takes in two argument -- the L-system and the index of the rule that you want to retrieve.

        def getRule( lsys, ruleIdx ):
            """ Return the ruleIdx'th rule of this L-system """
      

   7. Add the following two lines to your main function

        print "the base is ", getBase( my_lsys )
        print "the first rule is ", getRule( my_lsys, 0 )
      

      The new output is now three lines:

        ['A', [['A', 'AB']]]
        the base is  A
        the first rule is  ['A', 'AB']
      

2. We are going to store an L-system's base string and rules in a file. Therefore, we need to decide what format to use to store our L-system in a file. 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 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.

   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 L-system data structure according to the keyword at the beginning of the line.

     def createLsystemFromFile( filename ):
         """ Create an L-system list by reading in the specified file """
         # assign to fp the result of opening the file
         # read all of the lines in the file
         # close the file
         # assign to lsys the result of calling the function init()
         # for each line 
             # assign to words the result of splitting the line on spaces
             # if the first word is 'base'
                 # set the base of the L-system using the function setBase
             # else if the first word is 'rule'
                 # add the rule to the L-system using the function addRule
         # return the L-system list
   

   Something to consider: The above algorithm makes the assumption that there are no empty lines in your text file. Could you improve the code to allow it to ignore empty lines?

3. Write a test function to test createLsystemFromFile. Import the sys package, then add an argv to your main function. Then add the following lines to the end of your main function:

     if len(argv) < 2:
         print "Usage : python lsystem.py <filename>"
         exit()
   
     lsys_filename = argv[1]
     lsys = createLsystemFromFile( lsys_filename )
     print lsys
   

   Update the call to main to provide the sys.argv argument.

     if __name__ == "__main__":
         main(sys.argv)
   

   Download the following three files and test your code.

   • systemA1
   • systemA2
   • systemB

   Test your code with systemA1.txt. The output should print the line:

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

4. Now we will write the function buildString, which generates a string from an L-system, given a number of iterations. It takes in two arguments: an L-system data structure and the number of iterations of replacement to execute. Copy/paste the following comments into your file and replace the comments with the appropriate code. Note that the code uses only the first rule of the L-system. Next week, we will update this code to handle more complicated L-systems. For now, restrict yourself to 1-rule L-systems.

     def buildString( lsys, iter ):		   
         """ Return a string generated by applying the L-system rules
         for iter iterations """
         # assign to a local variable (e.g. newstring) the result of getBase(lsys) 
         # assign to a local variable (e.g. rule) the result of getRule(lsys, 0)
         # assign to a local variable (e.g. symbol) the first element of the rule
         # assign to a local variable (e.g. replacement) the second element of the rule
         # loop iter times
             # assign to newstring, the result of newstring.replace( symbol, replacement )
         # return newstring
   

   Now update your main function. Replace

     if len(argv) < 2:
         print "Usage : python lsystem.py <filename>"
         exit()
   
     lsys_filename = argv[1]
     lsys = createLsystemFromFile( lsys_filename )
     print lsys
   

   with

     if len(argv) < 3:
         print "Usage : python lsystem.py <in_filename> <num_iterations>"
         exit()
   
     lsys_filename = argv[1]
     lsys = createLsystemFromFile( lsys_filename )
     print lsys
   										 
     num_iter = int( argv[2] )
     s = buildString( lsys, num_iter )
     print s
   

   Run the file with SystemA1.txt and 1 as the command line arguments. The new line of output should

     F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-F
   

   Run the file with SystemA1.txt and 3 as the command line arguments. The new line of output should be (likely with different line breaks)

   F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F
   -F-FF--F-FF-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F
   --F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F
   -FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F
   -F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF-
   -F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF
   --F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F-F-FF--F-FF-FF-
   -F-F--F-FF--F-F-F-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-
   FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F
   -FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F
   -FF--F-F--F-FF--F-F-F-FF--F-FF-FF--F-F--F-FF--F-F-F-FF--F-F-F-FF--F-F-F-FF--F-FF-FF--F-F-
   -F-FF--F-F-F-FF--F-F
   

5. Create a new file called turtle_interpreter.py. Put your name and date at the top in comments. The purpose of this file is to convert a string into an image using simple turtle commands.

   The primary function in this file is drawString. The drawString function is an interpreter. 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 ):
         """ Interpret the characters in string dstring as a series
         of turtle commands. Distance specifies the distance
         to travel for each forward command. Angle specifies the
         angle (in degrees) for each right or left command. The list of 
         turtle supported turtle commands is:
         F : forward
         - : turn right
         + : turn left
         [ : save position, heading
         ] : restore position, heading
         """
   
         # 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 equal to '-'
                 # turn right by angle
             # else if c is equal to '+'
                 # turn left by angle
             # else if c is equal to '['
                 # append to stack the position of the turtle
                 # append to stack the heading of the turtle
             # else if c is equal to ']'
                 # pick up the turtle pen
                 # set the heading of the turtle to the value popped off stack
                 # set the position of the turtle to the value popped off stack
                 # put down the turtle pen
   
         # call turtle.update()
   

6. The function hold() is given below. It sets up the turtle window to quit if you type 'q' or click in the window. Copy it to your turtle_interpreter.py file.

     def hold():
         """ holds the screen open until the user clicks or types 'q' """
   
         # have the turtle listen for events
         turtle.listen()
   
         # hide the turtle and update the screen
         turtle.ht()
         turtle.update()
   
         # have the turtle listen for 'q'
         turtle.onkey( turtle.bye, 'q' )
         # have the turtle listen for a click
         turtle.onscreenclick( lambda x,y: turtle.bye() )
   
         # start the main loop until an event happens, then exit
         turtle.mainloop()
         exit()
   

   Now test your turtle_interpreter.py and lsystem.py programs using testsimple.py. Use a 90 degree angle for systems A1 and A2 and a 22.5 degree angle for system B. Then try a 120 degree angle for system A1 for a different effect.

   System A1 (angle 90)	System A1 (angle 120)	System A2	System B

You can also try a slightly more complex test program testlsystem.py that draws several copies of a pair of lsystems.

When you are done with the lab exercises, you may begin Project 7.

© 2017 Ying Li. Page last modified: .