Lindenmayer Systems

Don't get freaked out by the long name - "Lindenmayer" is just the name of the person who came up with the idea. We call them "L-systems" for short.

Background Information

Lindenmayer systems are actually quite straightforward, but the terminology can be pretty complicated to wade through. This page is nice and complete, although here is a simpler description:

A specific L-system has an alphabet, an initial state, and a set of rules. (There are a few other details as well, but this is the most important part.) The alphabet is basically this:

Letter	Turtle Graphics Representation
`A`	Choose color 1 (e.g. red)
`B`	Choose color 2 (e.g. green)
`C`	Choose color 3
`D`	Choose color 4
`E`	Choose color 5
`F`	Move forward N pixels
`G`	Move forward N pixels, without drawing a line
`H`	Same as F
`+`	Turn right angle degrees.
`-`	Turn left angle degrees.
`[`	Save the current turtle state (position + heading)
`]`	Restore the most recently saved turtle state (position + heading)

Other characters can appear in both rules and in the initial or current state, but they don't affect the turtle graphics output.

The "initial state" just specifies the starting string for the L-system, and the "rules" specify how the current string is modified each step of the system. For example, the Dragon Curve has the initial state 'FX' and the following rules:

'X' is replaced with 'X+YF+'
'Y' is replaced with '-FX-Y'

So, the L-system would unfold like this:

Initial state is 'FX'
Second generation is 'FX+YF+' (replace 'X' with 'X+YF+')
Third generation is 'FX+YF++-FX-YF+' (replace the 'X' with 'X+YF+', and the 'Y' with '-FX-Y')

...and so forth. Note that you should generate the next state into a new string, because if you try to modify the current state directly then you will generate invalid results.

When this string is rendered, only the F, + and - characters affect the turtle; the X and Y characters are ignored.

Additional Inputs

Besides the inital state and the rules, an L-system must also specify what angle is for the system (see this page for examples of how angle can affect the rendering output), and also how many iterations should be applied before rendering the system. These values will be different for each L-system you simulate and render.

Turtle-State Stack

You can make some particularly interesting L-systems with the '[' and ']' characters, but they require more advanced rendering code. Basically, when the '[' character is encountered, the current turtle position and heading need to be saved, and when ']' is encountered, the last saved turtle state should be restored. This can be implemented with a stack, which is effectively just a list with special ways of interacting with it. In other words, represent the saved turtle state as a list, and update it as follows:

When a '[' character is encountered, push the turtle state onto the stack with the list.append(...) method. This will save the state onto the end of the stack.
When a ']' character is encountered, pop the last saved turtle-state off of the stack with the list.pop() method, and set the turtle's position and heading with this information. The pop method will retrieve and remove the last value from the list.

This should make it pretty straightforward to handle the saving and restoring of turtle state.

Division of Tasks

Here is a rough outline of what major tasks this project will involve. The first point is the most critical one, since all other tasks depend on this one working properly. You must agree quickly on a design so that the remaining tasks can be completed in parallel.

Implement a data representation for how an L-system should be represented. For example: a class that stores the initial state, the list of production rules, the current state, how many iterations to apply, etc. The "initial state" and "current state" can simply be strings, and production rules might be represented as tuples of strings: (from, to).
Implement the code to load an L-system from an input text-file. (Also need to devise a file-format for specifying the system.)
Implement code that applies the production rules to the current string, to generate the next string.
Implement code that traverses a string, to render the turtle graphics for that string. Decide exactly what each character will mean when drawing turtle graphics. Handle more advanced characters like the '[' and ']' characters. Handle appropriate scaling of the results so that they can be displayed in the turtle window.

The last task - displaying the result of the L-system - is a more involved task that will probably involve the most advanced coding effort. Getting an initial version of the display code will probably be straightforward, but implementing the turtle-stack and the scaling will likely be more advanced.

Additional Features

An interesting feature would be to draw multiple stages of a particular L-system on the same canvas, next to each other, so that the development of the L-system is very obvious.

Another feature would be to allow an L-system to be specified in a graphical user interface, similar to this web page.