L-Systems
Jessica Shepherd,
CS 433, Spring 1997
L-systems, introduced by A. Lindenmayer in 1968, produce character
strings that are graphically interpreted. They are been especially
useful in modelling plants and basic fractal curves. This page
explains the basics behind L-systems through simple Java applets.
The Most Basic Basics:
Some info on strings
Let's start out with the alphabet. Associated with an L-system is an
alphabet of letters with meaning. Most L-systems have the basic
letters in common. For example, the letter "F" means "go forward one
unit and draw a line." If you are familiar with LOGO, L-systems use a
turtle interpretation system similar to that of LOGO-writer.
Turtle Interpretation
Picture a turle sitting in the bottom left-hand corner of the screen
facing the bottom right-hand corner of the screen. You give the
turtle a set of commands, for example, "turn right", "go forward",
"turn left". The turtle moves across the screen following your
commands. This is what's going on in an L-system. Each letter of the
alphabet is a different command to the turtle.
The following applet illustrates this idea. Press a button to give
the turtle a new command. The string generated by these commands is
printed in the text area at the base of the applet.
|
|
Note the automatic scaling applied to lines in the above applet. This
becomes important when strings grow especially long.
Basic L-system Basics:
Simple Structure
Every L-system needs two things: and axiom and a set of production
rules. The axiom is the initial string. It tells the system
where to start. In the simplest case, the production rules are
functions that send letters to different strings.
Simple Example
As an example, the following is an L-system:
| axiom: |
F |
| production rules: |
F->F-F++F |
The system starts out with the string "F". During the first
iteration, the production rules are applied. In this case, the rules
say to replace every instance of "F" in the given string with the
string "F-F++F". Hence after one iteration we have:
F-F++F
During the second iteration, instances of "F" are again replaced by
the string "F-F++F" to produce the string:
F-F++F-F-F++F++F-F++F
And so on. After a sufficient number of iterations (specified by the
user), string production stops and the final string is drawn into the
window. Try typing the above string into the applet above to see what
resulting image appears.
Another Example
Axioms and replacement strings do not only have to consist of strings
with the the letters in the above applet. You can also include other
variables. These are interpreted by the turtle as "stay in the same
place facing the same direction." However, during iterations they can
be useful tools for inserting more complexity into the string.
Consider the following system:
| axiom: |
FXF--FF--FF |
| production rules: |
F->FF
X->--FXF++FXF++FXF-- |
If the axiom is drawn, the turtle ignores the letter "X" and follows
the commands specified by the other letters to create a triangle.
During the next iteration, however, the "X" is replaced by the string
"--FXF++FXF++FXF--". Again the turtle draws this as a triangle.
However, now we have a triangle within our initial triangle!
Your Turn
Below is an applet that allows you to design your own simple L-systems
using techniques described above. You are allowed to add, delete, and
modify production rules and the axiom. Also, you determine the number
of iterations through which the string will be sent ("number of
cycles") and the angle the turtle rotates when you tell it to turn
right or left ("rotation angle"). If you don't know where to begin,
also included are a number of examples. Try decreasing and increasing
the number of cycles per example to watch the image build itself up.
|
|
For More Information:
A more comprehensive example of L-systems, including some features not
implemented in this system, can be found
here.
Future Plans:
- Someday I will make the applet draw each cycle separately as
you watch, instead of taking the time to compute all the cycles
before drawing to the screen.
Jessica Shepherd
(jshepher@cs.utah.edu)
Sep 24, 1997