Lab Exercise 7: 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 we did with the last few labs, we'll use a list L-system to hold all of the L-system information.
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 and tree modeling systems that are used in special effects for movies and shows.
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.
Video: L-systems Overview (also in /Volumes/Courses/CS151/Course_Materials/Lab_Videos)
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.
- An alphabet of characters
- A base string
- 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 this week are as follows.
F is forward by a certain distance + is left by an angle - is right by an angle
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
To get from one string to the next, replace each instance of F with the string -F+F-F. Note that the strings can grow very fast.
In this lab we're going to create two files: lsystem.py and turtle_interpreter.py.
The L-system 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.
Create a working directory for project 7 (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 lsystem file is meant to have functions supporting L-system string generation, but not drawing, so do not import the turtle into lsystem.py.
- L-System design and functions
The goal of this step is write code that can read an L-system from a file and generate strings defined by the base string and the rules.
What are the necessary components of an L-system and how can they be stored in a variable?
An L-system requires two pieces of information:
- the base string, and
- the list of rules.
The base string is simply a string. A single rule has two components: the symbol, and its replacement. Both the symbol and the replacement are strings. One way to represent a rule is to use a list with two strings; the first string is the symbol, and the second string is its replacement. To store multiple rules, we can use a list to hold the rule lists (a list of lists).
A complete L-system can be 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 string and single rule:
base 'F-F-F-F' rule 'F' -> 'FF-F+F-F-FF'
would have the following Python representation:
['F-F-F-F', [ [ 'F', 'FF-F+F-F-FF' ] ] ]
Conceptually, the L-system can be thought of as the following.
[ base_string, [ [ symbol, replacement] ] ]
Note that the second item in the L-system list is a list of rules, where each rule is a 2-element list.
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. Write each function without looking at the additional information and then test your code. If your code isn't working, then compare your work.
- init(): return an empty L-system.
The init function needs to create an empty L-system and return it. Using the list representation, an empty L-system would be a list with two elements: the empty string and an empty list. Write this function.
+ (check your code)
# returns an empty L-system def init(): return ['', ]
- getBase( lsys ): return the base string of an L-system.
The getBase function takes in just one argument--the L-system list. It returns the base string, which is the first item in the L-system list.
+ (check your code)
# returns the base string of the L-system def getBase( lsys ): return lsys
- setBase( lsys, base ): set the value of the base of an L-system.
The setBase function takes in two arguments, an L-system list and a base string. It should assign to the base string field of the L-system list the new string provided in the base parameter.
+ (check your code)
# sets the L-system base string def setBase( lsys, base ): lsys = base
- addRule( lsys, rule ): add a rule to an L-system
The addRule function takes in two arguments: an L-system list and a rule. It should append the rule to the list of rules, which is the second item in the L-system list.
+ (check your code)
# adds the rule to the L-system def addRule( lsys, rule ): lsys.append( rule )
- getRule( lsys, index ): return a rule in an L-system.
The getRule functions takes in two argument--the L-system and the index of the rule to retrieve. It should return the rule at position index of the L-systems's list of rules.
+ (check your code)
# returns the rule at position index in the L-system def getRule( lsys, index ): return lsys[index]
All of the functions in this module will take an L-system list with format described above. Write a comment at the top of your lsystem file describing the format. That let's you avoid including 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.
- Test the L-system functions
At the bottom of your L-system file, add a test function.
def main(): my_lsys = init() setBase( my_lsys, 'A' ) addRule( my_lsys, ['A','AB'] ) print(my_lsys) print("the base is ", getBase( my_lsys )) print("the first rule is ", getRule( my_lsys, 0 )) if __name__ == '__main__': main()
The test code should print
['A', [['A', 'AB']]] the base is A the first rule is ['A', 'AB']
- Write a function to read an L-system from a file
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. The base string is F-F-F-F, and the rule is the symbol string F has a replacement string FF-F+F-F-FF.
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. Each comment corresponds to one line of code.
def createLsystemFromFile( filename ): """ Create an L-system list by reading in the specified file """ # assign to lsys the result of calling the function init() # assign to fp the result of opening the file (use open(filename, "r") ) # assign to lines the result of calling fp.readlines() # close the file using the close method of the file object held in fp # for each line in the list lines # assign to line the result of calling line.strip() # assign to words the result of calling line.split(' ') # if the first item in words is equal to 'base' # use the setBase function passing in the second item in words as the new base string # else if the first item in words is equal to 'rule' # use the addRule function passing in all but the first item in words as the new rule # return the L-system list lsys
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?
- Test reading an L-system from a file
Have your lsystem.py file import sys. Then replace your existing main function with the following.
def main(argv): # check if there are enough command-line arguments if len(argv) < 2: print("Usage : python3 lsystem.py
") exit() # code to test reading from a file lsys_filename = argv lsys = createLsystemFromFile( lsys_filename ) print(lsys) if __name__ == '__main__': main(sys.argv)
Download the following two files and test your code.
Test your code with systemA1.txt. It should print the line:
['F-F-F-F', [['F', 'F-FF--F-F']]]
- Write a function to build a string from an L-system
Write the function buildString, which generates a string from an L-system, given a number of iterations. The function takes in two arguments: an L-system list 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, n ): """ Return a string generated by applying the L-system rules n times""" # assign to a local variable (e.g. nstring) 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 rule # assign to a local variable (e.g. replacement) the second element of rule # loop n times # assign to nstring, the result of nstring.replace( symbol, replacement ) # return nstring
Update your main function so it looks like the following.
def main(argv): if len(argv) < 3: print("Usage : python3 lsystem.py <in_filename> <num_iterations>") exit() lsys_filename = argv lsys = createLsystemFromFile( lsys_filename ) print(lsys) num_iter = int( argv ) s = buildString( lsys, num_iter ) print(s) if __name__ == "__main__": main(sys.argv)
Run the file with SystemA1.txt and 1 as the command line arguments. The new line of output should be
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
When you are done with the lab exercises, you may begin the project.
- Test the L-system functions