Lindenmayer systems (or L-systems for short) are based on the idea that the growth of organisms, particularly plants, can be modeled by string manipulations. L-systems provide rules for repeatedly rewriting strings. Characters in the string can be rendered via a method called turtle graphics (which you may be familiar with from the programming language Logo). See the wikipedia articles on L-systems and turtle graphics for more background information.

Turtle Graphics

Turtle graphics is an alternative way to render think about drawing graphics to what we discussed in class. In turtle graphics a turtle exists in a graphics window. The turtle has certain attributes including location, orientation. The turtle also has a pen which may either be up or down. When the turtle moves it draws a line between its old location and its new location if the pen is down. (If the pen is up nothing is drawn but the turtles location is updated). Typically, turtles only move forward or backward which are defined by their orientation.

For the first part of this project, you will create a turtle graphics module in a file called turtle.py. You may implement your code any way you want but it must support the following functionality.

Create a graphics window with a specified title, width, and height
Set the position of the turtle
Rotate the turtle by a given angle (in degrees). A negative angle is counter clockwise. (Rotating means adding to the orientation)
Move the turtle by a given length (in pixels). A negative length moves the turtle backwards. If the pen is down a line should be drawn between the old location and the new location. If the pen is up nothing should be drawn.
Set the pen to the up or down position
Set the width of the lines being drawn by the turtle
Set the color of the lines being drawn by the turtle (in r,g,and b)
Add to the color
Add to the width
Push the current turtle state onto a stack. The state of turtle should include the current location, orientation, line color, and line width. For the purpose of this exam you may consider pushing an item onto a stack as synonymous with appending an item to a list.
Pop the turtle state from the stack/list and set the turtles current state to that of the popped value.

As stated above, you may implement turtle.py anyway you want so long as it has the functionally outlined above. You should document your module in a way that would allow a programmer to import and use your module as a software library. Someone should be able to import your module (import turtle) into python and call help(turtle) and get all the information they need to start using your module. In other words, a competent python programmer should not have to open your code in a text editor to figure out how to use it. (That said, your program should be properly commented too.)

If you are still having trouble with proper documentation see Introducing Docstrings (don't worry about anything after the section heading "Documentation Generation").

A bit of trig

If the turtle is at location x,y with an orientation a in degrees its new location, x2,y2, after moving d pixels would be:

 
	x2 = x + d * cos(a * π / 180)
	y2 = y + d * sin(a * π / 180)

L-Systems

An L-system is a string and rules for repeatedly modifying the string. Formally, L-systems are defined by three components:

An alphabet: a set of symbol (or for the sake of this assignment characters which are legal in our string)
Production rules: a set of rules that define how symbols in the alphabet should be replaced with strings.
A start string: the initial string to which the production rules are applied

For example, the following example (from wikipedia) was used to model the growth of algae:

alphabet

start state

production rules

A ? AB
B ? A

The rule "A ? AB" means replace the character 'A' with the string 'AB'. The rule "B ? A" means replace the character 'B' with the string 'A'. If the production rules are repeatedly applied to the string starting with "A" you produce the following:

 
n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Create a module called lsystem. Inside lsystem.py implement a function called generate Generate should take 4 arguments: an alphabet, a start string, production rules, and n (the number of times the rules should be applied to the string).

The alphabet is a string. Each character in the string represents a valid symbol in the L-system. The start string is a string made up of characters in the alphabet. The production rules are a list of strings representing production rules. Each rule looks like the ones listed above except " ? " is replaced by ":" so "A ? AB" would be "A:AB".

The algae example would look like:

 
>>> generate('AB', 'A', ['A:AB','B:A'], 7)
'ABAABABAABAABABAABABAABAABABAABAAB'

If you find a character that does not appear in the alphabet your function should return the boolean False.

Like turtle you may implement generate anyway you want so long as it meets the specification above. Hint - you may want to parse and store the production rules in a different format than the initial list of strings passed in to the function.

Putting it together

The by mapping symbols in the L-system to operations on the turtle a L-system can be used to draw a graphic. See the wikipedia article for examples.

Inside lsystem.py implement a function called render. render should take a file name (a string) as an argument. The specified file will be a text file which describes how to generate and draw a particular L-system. After drawing the L-system with your turtle module the function should wait for a mouse click before closing the window. Each line of the text will be for the form:

 
setting, value

The settings included in the file are:

windowWidth - the width of the graphics window
windowHeight - the height of the graphics window
windowTitle - the title display on the graphics window title bar
x - the initial x position of the turtle
y - the initial y position of the turtle
orientation - the initial angle for the turtle
r - the initial red value for the line color
g - the initial green value for the line color
b - the initial blue value for the line color
width - the initial line width
stepSize - the amount to move the turtle forward (or backward)
da - the amount to rotate the turtle left (or right)
dr - the amount to increment (or decrement) the red value
dg - the amount to increment (or decrement) the green value
db - the amount to increment (or decrement) the blue value
dWidth - the amount to increment (or decrement) the line width
alphabet - the alphabet
startString - the start string
rules - production rules
n - the number of times the production rules should be applied to the string

Your program should accept settings in any order and ignore capitalization of setting names. Capitalization of setting values is important. White space should be ignored. Each production rule listed in rules is formatted as described the previous section and separated by commas. You may assume that commas and spaces are not allowed in an alphabet. Here is an example of file for a Koch curve (as described in wikipedia):

 
alphabet,  >+-
startString, >
rules, >:>+>->->+>
n, 3
windowWidth, 500
windowHeight, 300
windowTitle, Koch Curve
x, 100
y, 200
a, 0
r, 0
g, 0
b, 255
width, 1
stepSize, 10
dr, 1
dg, 1
db, 1
dWidth, 1
da, 90

For our project, symbols/characters will control the turtle as follows:

> moves the turtle forward by the stepSize
< moves the turtle backward by the stepSize
+ turns the turtle left by da
- turns the turtle right by da
^ lifts the pen up
v lowers the pen down
W increase the line width by dWidth
w decrease the line width by dWidth
R increments the red value by dr
r decrements the red value by dr
G increments the green value by dg
g decrements the green value by dg
B increments the blue value by db
b decrements the blue value by db
[ pushes the turtle state
] pops the turtle state
Any symbol not listed above should be ignored by the renderer.

Color values should be restricted to the range 0-255 inclusive.

The example file listed above should result in a graphics window that looks like this:

The following file:

 
windowWidth, 500
windowHeight, 500
windowTitle, Fractal Plant
x, 200
y, 475
a, -90
r, 0
g, 0
b, 0
width, 1
stepSize, 2
dr, 1
dg, .25
db, 1
dWidth, 1
da, 25
alphabet,  >+-G[]X
startString, >
rules, X:>-[[X]+X]+>[+>X]-X,  >:>>G
n, 6

should generate the following window:

Like turtle.py, lsystem.py should be properly documented and commented and, except for the required functions you may implement your code as you see fit.

Think carefully about how to break up the final into smaller programs. Much of this project is similar to previous homework assignments and labs.

Extra Credit

Submit a L-system specification file that creates an original an compelling image when rendered. You may add features to your rendering engine if you wish. The extra credit is worth up to %5. Call your file extraCredit.txt

Submit

Submit this assignment electronically from beowulf.

 
chmod 640 turtle.py
chmod 640 lsystem.py
submit final turtle.py
submit final lsystem.py

If you did the extra credit submit it too.

 
chmod 640 extraCredit.txt
submit final extraCredit.py