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-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 lsystem from a file and generate a string from the lsystem 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 lsystem 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. Proj7). 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 lsystem file for each of the next 4 weeks, so having a version number at the top of your file will be important.
2. We're going to do top-down design and start with a test function for the lsystem functions. 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. Import the sys package, then create a function main with commandStrings as its parameter. The main function needs the following steps.

   import sys
   
   def main(commandStrings):
       """ Generate a string using an L-system, and write the string
           to a file.  commandStrings should have the form:
           ["lsystem.py", sourceFilename, numberOfIterations] """
       # get the source filename from the oneth element of commandStrings
       # get the number of iterations from the twoeth element of commandStrings
       # assign to a variable (e.g. lSystem) the result of createFromFile(filename)
       # print out the result of buildString(lSystem, numberOfIterations)
   
   if __name__ == "__main__":
       main(sys.argv)
   

   The final two lines put a call to main with sys.argv as its argument inside the usual __name__ conditional test.

   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 that returns some string. Then test your code:

   $ python lsystem.py beluga.txt 2

   (The last two command line arguments can be anything, since we aren't actually reading the file yet.)

3. There are obviously two functions in the main program we haven't yet built. Let's modify the placeholder function createFromFile. Above your main function, define 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 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 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 createFromFile( filename ):
       """ Create an L-system list by reading in the specified file """
       # open the file, storing the file pointer in a variable
       # read all of the lines in the file
       # close the file
       # call the function initialize() and assign its output (an empty L-system) to lSystem
       # for each line 
           # split the line on spaces using line's split method
           # if the first word is 'base'
               # set the base of lSystem using the function setBase
           # else if the first word is 'rule'
               # add the rule to lSystem using the function addRule
       # return the L-system list
   

   Note that we have three functions--initialize, 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 L-system data structure.

4. The initialize 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 initialize return an empty L-system.

   Since all of the functions in this module will take an L-system list with the above format, let's describe some of this in the docstring header for the file. That way, we don't need to include too much detail in all of the individual function docstrings. Take the time right now to add an explanation at the top of the file describing the format of the list used to represent an L-system.

5. 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( lSystem, newRule ):
       """ Add a rule to the L-system list stored in lSystem.
       newRule is a list of 2 strings """
       # append newRule to the L-system's rule list
   

6. Now we need to write three more functions and our lsystem.py file will be complete. Update the placeholder buildString function. It takes in two arguments: an L-system data structure and the number of iterations of replacement to execute.

   def buildString( lSystem, iterations ):
       """ Return a string generated by applying the L-system rules
           for the given number of iterations """
       # assign to a local variable (e.g. lString) the result of getBase(lSystem) 
       # assign to a local variable (e.g. rule) the result of getRule(lSystem, 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 iterations times
           # assign to lString, the result of lString.replace( symbol, replacement )
       # return lString
   

   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. See if you can do this on your own.

   Download the following three files and test your code.

   • systemA1
   • systemA2
   • systemB

   First try running systemA1 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 outputs for systemA1, systemA2, and systemB in separate files.

7. Create a new file called turtle_interpreter.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.

   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 do nothing) for each character.

   def drawString( drawableString, distance, angle ):
       """ Interpret the characters in string drawableString 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. turtleStateStack) the empty list
       # for each character, char, in drawableString
           # if char is 'F'
               # go forward by distance
           # else if char is equal to '-'
               # turn right by angle
           # else if char is equal to '+'
               # turn left by angle
           # else if char is equal to '['
               # append to your list variable the position of the turtle
               # append to your list variable the heading of the turtle
           # else if char is equal to ']'
               # pick up the turtle pen
               # set the heading of the turtle to the value popped off the list variable
               # set the position of the turtle to the value popped off the list variable
               # put down the turtle pen
       # call turtle.update()
   

8. 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 testlsimple.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 L-systems.

The assignment is to bring together the lsystem and turtle_interpreter pieces to make a scene that consists of fractal shapes, trees, and other turtle graphics (think back to projects 1, 2 and 3). Your top-level program will include both the lsystem and turtle_interpreter modules.

---

Tasks

1. Create a file called abstract.py. The file will need to import sys, turtle, lsystem, and turtle_interpreter. Write a function that creates an abstract image using L-systems. This image should be constructed to take advantage of your Python programming skills -- don't rely wholly on the random package and a loop. Your goal should be complexity, yet order in your image and simplicity in your code. One idea is to make an interesting pattern.

   Your image should include at least three different L-systems, with at least one of them using brackets. Don't feel beholden to use the suggested number of iterations or angles for any L-system. You can get the filenames for the L-system files from the command line, by asking the user for them, or by hard-coding them into your code.

   In your image function, you can use turtle commands to pick up the pen, move it to a new location, change colors, change pen widths, and put down the pen before drawing a new shape.

   A picture with 3 different L-systems is required image 1.

2. Make a new file grid.py that contains a function that draws a set of 9 trees based on the systemB L-system, or some variation of it that has brackets. Order the 9 trees as a 3x3 grid. From left to right the number of iterations of the L-system should go from 1 to 3. From top to bottom, the angle of the L-system should be 22.5, 45, and 60. Use a double for-loop to create the grid.

   A picture with a grid of L-systems is required image 2.

3. Make a new file scene.py that makes a non-abstract scene with two or more objects generated using L-systems. The scene must include at least one new L-system with brackets (e.g. a tree) that you haven't used yet. You can use one of the L-systems from ABOP (look at pages 9, 10, and 25 for single-rule L-systems) or make up one of your own. The scene does not need to be complex, but your code should exhibit modularity and good design.

   A scene that includes 2 different L-systems is required image 3.

---

Extensions

Each assignment will have a set of suggested extensions. The required tasks constitute about 85% of the assignment, and if you do only the required tasks and do them well you will earn a B+. To earn a higher grade, you need to undertake one or more extensions. The difficulty and quality of the extension or extensions will determine your final grade for the assignment. One complex extension, done well, or 2-3 simple extensions are typical.

• Import one of your scenes from project 2 or 3 and add trees or fractal shapes to them. It's all turtle graphics, after all.
• Make your abstract image function take in (x, y, scale) as parameters and demonstrate you can properly translate and scale the abstract image by including multiple copies, at different locations and scales, in one scene.
• Make task 2 more interesting by adding additional elements to the image that also change across the grid. For example, make the trees move from summer to fall to winter along the horizontal or vertical axis.
• Give the function for task 2 the parameters (x, y, scale) and demonstrate you can properly translate and scale the grid.
• Create an L-system of your own that draws something interesting.
• Add leaves, berries, or color to your trees by adding new alphabet symbols to the rules and cases to your turtle_interpreter. For each new symbol you use in a rule, you will need another elif case in your drawString function.
• Use a Python language feature new to you (not just a new library feature or function)

---

Writeup and Hand-In

Before handing in your code, double check that it is well-styled:

• All variable names and function names use either camelCase or snake_case.
• All files and functions have docstrings.
• Comments are added to explain complicated code blocks.
• All variable and function names are appropriately descriptive.
• Functions are defined before any other code is added at the top level of each file.
• In a file with any functions defined, top level code is wrapped so that it won't execute if that file is imported by another.

Make a new wiki page for your assignment. Put the label cs151s14project7 on the page. Each of you needs to make your own writeup.

In addition to making the wiki page writeup, put the python files you wrote on the Academics server in your private handin directory.

Colby Wiki

In general, your writeup should follow the outline below.

• A brief summary of the task, in your own words. This should be no more than a few sentences. Give the reader context and identify the key purpose of the assignment.
• A description of your solution to the tasks, including any images you created. (Make sure your images are appropriately sized to fit onto the wiki page.) This should be a description of the form and functionality of your final code. You may want to incorporate code snippets in your description to point out relevant features. Note any unique computational solutions you developed.
• A description of any extensions you undertook, including images demonstrating those extensions. If you added any modules, functions, or other design components, note their structure and the algorithms you used.
• A brief description (1-3 sentences) of what you learned.
• A list of people you worked with, including students who took the course in previous semesters, TAs, and professors. Include in this list anyone whose code you may have seen. If you didn't work with anyone, please say so.
• Don't forget to label your writeup so that it is easy for others to find. For this lab, use cs151s14project7