A Project Outline:
L-systems in Python

by Kirby Urner
First posted: July 7, 2000
Last modified: July 8, 2000

I was exploring in ActiveWorlds Education Universe today, and went again to Bonnie DeVarco's Virtual High School (VHS), a fave location in TheU, one of 133 worlds in Education Universe.

At 21N 54W facing North, you have this amazing wall of bioforms, with a link to the Lsystems website by Lauren Lapré.

This guy has done some trully amazing ray tracings. For example, check this out.

Anyway, the Lsystem is the formal language that grew up in the space between fractal and turtle geometries, and is used to develop fairly realistic bioforms on the computer. This seems a useful and rich area in which to anchor some educational "math through programming" Python projects.

Virtual High School in TheU: 21N 54W facing North

First, for an example of what Lsystems can do, check out some of these images:

Where to find more background on Lsystems? Everyone refers to a groundbreaking text: The Algorithmic Beauty of Plants by P. Prusinkiewicz and A. Lindenmayer (the Lindenmayer's name providing the L in Lsystems).

Prusinkiewicz and colleagues, based in Canada, have put quite a bit of material on the web. http://www.cpsc.ucalgary.ca/projects/bmv/vmm/JPEG/production.jpg would make a good PowerPoint slide (make sure you get permission), and starts to explain the notation.

Especially useful is Hung-Wen Chen's explanation of his 1995 master project in computer graphics. Here we find the turtle language spelled out, along with ideas about how to implement in code, including the rotation matrices. Excerpt:

The basic idea of turtle interpretation described by Prusinkiewicz[2] is given below. A state of the turtle is defined as a triplet state (X,Y,Alfa), where the Cartesian coorfinates(x,y) represent the turtle's position , and the angle Alfa, called the heading, is interpreted as the direction in which the turtle is facing. Given the step size N and the angle increment angle Delta, the turtle can respond to commands represented by the symbols : F , + , and -.

However, the three symbols can only generate 2 dimensional graphic trees. If we want to generate 3 dimensional graphics, these two operators are not enough. Therefore, for 3D graphics, we have to change the turtle's state to (X,Y,Z,Angle_U,Angle_L,Angle_H).

In addition, there are seven operators to deal with the freedom of the 3 dimensions graphics space, such as turn left or right, pitch down or up, and roll left or right, and turn around. All these operators are used to generate the graphics not only in a flat plane but also in 3D space.

   "F": Move forward a step of length d. A line segment between
        points (X,Y,Z) and (X',Y',Z') is drawn.
   "]": bracket - push and pop the current state, in this project
        it is used to generate the tree branches
   "+": Turn left by angle Delta, Using rotation matrix R_U(Delta)
   "-": Turn right by angle Delta, Using rotation matrix R_U(-Delta)
   "&": Pitch down by angle Delta, Using rotation matrix R_L(Delta)
   "+": Pitch up by angle Delta, Using rotation matrix R_L(-Delta)
   "<": Roll left by angle Delta, Using rotation matrix R_H(Delta)
   ">": Roll right by angle Delta, Using rotation matrix R_H(-Delta)
   "|": Turn around, Using rotation matrix R_H(180)

The above information is giving us the outlines of a Python Lturtle class. We'd need a current state list, saved state, and rotation methods. The heading, up and left members of the state tuple are unit vectors. So we need a vector class -- something like this:

from coords import Vector

class Lturtle:

   stackstate = []    # remembers saved state
   delta      = 0     # angle of rotation
   length     = 0.5   # full length of turtle move
   thickness  = 0.02  # default thickness of cylinder
   def __init__(self,vPos=Vector((0,0,0)),
                     vH  =Vector((0,0,1)),
                     vL  =Vector((0,1,0)),
                     vU  =Vector((1,0,0))):
       """The turtle will start at the origin with the
       Z-axis as forward direction and Y-axis as left
       direction. (lparser.txt)"""
       self.vPos,self.vH,self.vL,self.vU = vPos,vH,vL,vU
   def turnleft(self):
       print "Turn Left by delta"

   def turnright(self):
       print "Turn Right by delta"

We also need a way to parse Lsystem files, meaning we iterate through a set of rules (e.g. substitions) a specified number of times, and feed the resulting string to the Lturtle as a series of commands e.g. [+F+F+F+F][-F-F-F-F]. We should probably read these in as text files (.ls) in order to be compatible with a lot of the work already done.

More information on Lsystems:

In the shoptalk of Lsystems, you start with axioms and rules of production. An axiom is a string like:

 >>> axiom = 'F--F--F'

and your rules of production define substitions, such as:

 >>> rules = {}
 >>> rules['F'] = 'F+F--F+F'

To apply the rules to an axiom is to scan a string, and substitute wherever appropriate, e.g. every occurance of 'F' in the above axiom would be replaced by 'F+F--F+F'.

Since the '-' symbol is not associated with a substition rule, it would simply pass through as is:

 >>> def produce(axiom,rules):
         output = ""
         for i in axiom:
             output = output + rules.get(i,i)
         return output

Notice that the dictionary.get() method takes 2 arguments, the 2nd being what to return if the 1st is not a key. For example, if i = 'F', then the rule for 'F' will be invoked, but if i = '-', then '-' will simply pass through to the growing output string.

 >>> produce(axiom,rules)
 >>> newaxiom = produce(axiom,rules)
 >>> produce(newaxiom,rules)
Another example:
 >>> rules = {}
 >>> rules['A'] = 'B'
 >>> rules['B'] = 'AB'
 >>> axiom = 'A'

This sets up the example used at: http://www.csu.edu.au/complex_systems/tutorial2.html

We'll define iterate as a recursive function:

 >>> def iterate(n,axiom,rules):
         print axiom
         if n>0:
            axiom = produce(axiom,rules)
            return iterate(n-1,axiom,rules)
 >>> iterate(7,axiom,rules)

Basically, our Lparser class needs to read in a file consisting of an axiom and some rules, plus other parameters such as how many times to recursively apply the rules, what the default angle of rotation is and so on.

Let's look at a real example of an .ls file, included with the downloadable DOS version of Lparser at http://www.xs4all.nl/~ljlapre/lparser.htm:

#  Crystals.ls         (c) C.J. van der Mark      
#      Questions about Lparser files to:          
#        Internet  cvdmark@xs4all.nl              
#           Fido      2:283/203.11                
#           PCG       9:526/464.3                 
Rules are defined by equal signs. The axiom is given by a letter alone, after some numbers, in this case I. As per http://www.xs4all.nl/~cvdmark/tutor.html, the first 3 numbers represent:
15    # recursion depth 
20    # angle 
20    # thickness as % of length 
In Python:
 >>> rules = {}
 >>> rules['I']='+(40)ffHccI'
 >>> rules['H']='[+fffG]c[-fffG]c[^fffG]c[&fffG]G'
 >>> rules['G']='[dS]e[d]e[d]e[d]e[d]e[d]e[d]e[d]'
 >>> rules['e']='+(90)f-(90)>(-45)'
 >>> rules['d']=('{[f+(90)f+(90)f+(90)f>(+38)-(105)ff-(151)ff]'
 >>> axiom = 'I'
 >>> iterate(2,axiom,rules)

And that's only 2 iterations. After 15, we'd have a very long string of commands to feed to our Lturtle.

Let's use the DOS lparser.exe to generate a Povray file corresponding to Crystals.ls:

          lparser -vc -g Crystals
Running in a DOS box, I get the following output in response to the above input:
L-System Parser/Mutator v4.0
Copyright (C)  : RenderStar Technology BV. 1992-1995
Release date   : Dec 27 1995 (386+/DOS)
Sizing memory
L-system file  : .\crystals.ls
Recursion depth: 15
Basic angle    : 20
Thickness      : 20
Axiom          : I
Rule           : I=+(40)ffHccI
Rule           : H=[+fffG]c[-fffG]c[^fffG]c[&fffG]G
Rule           : G=[dS]e[d]e[d]e[d]e[d]e[d]e[d]e[d]
Rule           : e=+(90)f-(90)>(-45)
Rule           : d={[f+(90)f+(90)f+(90)f>(+38)-(105)ff-
Size of string : 41480 chars
Pov file       : output.inc
Objects        : 5761

Then the instructions tell me:

The file 'setup1.pov' can be used to connect to the output.inc file created with lparser -vc. The first 8 colors in the pov rendering will then match the ones in the viewer.

imageBut I didn't get a very good rendering after all that. Had to tweak it quite a bit (monkey around with lighting and camera angle). The result is shown at left.

As outlined in previous posts, the Lsystem formalism provides long strings of single-letter turtle commands, e.g. 'FF--FF++&^FF'

In Lapré's version, commands may be followed by a parameter enclosed in parentheses, e.g. 'F(10)F--(90)FF++(100)'

In Lapré's C implementation, you find a long set of case-break statements for parsing through these command strings i.e. we check for:

     case item='F' {

     case item='-' {

and so forth.

Given the long list of single letter commands (about 30 of them), it makes sense to use a Python dictionary construct coupled with eval. To each symbol there corresponds the name of a turtle method, saved as a string. The turtle knows how to convert returned strings to method names at runtime. Also, the turtle knows to hold off evaluating a command until it has checked for the optional following parameter.

Above, I provided the skeletal outline of an Lturtle class. The Lturtle class below goes a step further, by accepting long instruction strings via its chomp method. chomp "eats its way through" the instructions, turning switches on and off as it tests for "(" and ")" -- the parameter symbols. It looks up symbols (other than parentheses) in the instrudict class variable (a dictionary), and builds a command to evaluate -- e.g. self.turnleft(30) -- once parameter checking is complete.

Others will likely come up with simpler versions of chomp -- some won't like my switch-based approach.

I've only coded stub functions for command symbols f + and - (even though the dictionary is somewhat more complete). The point is to test the design. With all of these pieces in place, we've set the stage to write an Lsystem parser in Python, i.e. to read in the same files Lapré's lparser.exe accepts, and to have the output go to Povray for rendering (or other formats, depending how ambitious we are -- how many wheels we want to reinvent).

I've got more turtle-related code, in connection with Povray in particular, in Part 4 of my Numeracy + Computer Literacy series -- lots more clues about how to proceed with this project.

Whether or not I'll go further down this road myself I don't know right now. If I do, I'll post further details to the web.

In the meantime, this might be an interesting project for others to continue and/or adapt to classroom situations. There's lots of Lsystems literature, positively reinforcing bioform graphical output, plus a synergy of two topics already covered at the high school level in many curricula: fractal patterns and turtle graphics.

In addition, the recursive production rules are good for reinforcing that algorithms may be alpha-numeric, not just numeric -- i.e. string and symbol processing is every bit as "mathematical" (potentially), as anything to do with "raw number crunching" (as algebraic manipulation so well demonstrates).


    stackstate = []    # remembers saved state
    delta      = 0     # angle of rotation
    length     = 0.5   # full length of turtle move
    thickness  = 0.02  # default thickness of cylinder
    instrudict = {'+':'turnleft',
                     vH  =Vector((0,0,1)),
                     vL  =Vector((0,1,0)),
                     vU  =Vector((1,0,0))):
       """The turtle will start at the origin with the
       Z-axis as forward direction and Y-axis as left
       direction. (lparser.txt)"""
       self.vPos,self.vH,self.vL,self.vU = vPos,vH,vL,vU


        getparam   = 0
        checkparam = 0
        param = ""
        for item in instructions:

           if getparam:          # getting parameter?
               if item == ")":
                   getparam = 0  # done getting
                   command = command + "(" + param + ")"
                   param = param + item  # building parameter
           if checkparam:        # checking for parameter?
               checkparam = 0
               if item == "(":
                   param = ""
                   getparam = 1  # parameter exists
                   command = command + "()" # no parameter

           # initializing command string
           command = "self." + self.instrudict.get(item)
           checkparam = 1    # set flag

        else:  # dealing with last item
           if checkparam:
              command = command + "()" # no parameter
        print "Forward %s (no draw)" % n

        print "Turn Left around vU %s" % n

        print "Turn Right around vU %s" % n

For further reading:

oregon.gif - 8.3 K
Oregon Curriculum Network