In the introduction we stated that a fractal is an infinitely complex pattern. Clearly, if the right side of each transformation rule is longer than the left side, the length of the axiom will increase with each iteration. As the number of iterations performed approaches infinity, so does the axiom length. In addition, because the process involves applying the same transformations, iteration after iteration, we might intuitively expect patterns to emerge in the axiom as we perform the iterations, so that we end up with an infinitely long pattern. Keeping these rough ideas in mind, it might not be surprising that fractals can be produced using Lindenmayer grammars, provided we somehow define a way to transform an axiom into a fractal image. That is, we use a string of characters to describe a fractal.
The method for doing this is simple. We will draw fractals using a "turtle". A turtle starts at an initial point on the screen, pointing in a given direction (its initial heading, where 0° means facing right, and 90° means facing straight up). The turtle can then be told to move to any point on the screen, either with pen up or pen down. When the turtle moves from point A to point B with the pen down, it will draw a line between A and B as it moves. If the pen is up, it will simply move to point B without drawing anything. The turtle can also be told to change its heading to any given direction. Now, we want the turtle to understand an axiom as movement and rotation commands, so we give some characters a special meaning. For example, the program I wrote assigns the following meanings:
|
All other characters have no special meaning, but are still useful, as will be seen later.
The turtle can now translate an axiom into a fractal by reading the axiom's characters from left to right. If a character has a special meaning, the turtle performs the corresponding command. If the character has no special meaning, the turtle does nothing and moves on to the next character. There are two pieces of information the turtle must know, in addition to the initial axiom and transformation rules. One is the initial heading. The other is the angle of one rotation unit. For example, assume the initial heading is 90° (straight up) and the rotation unit is -30°, and the first character of the initial axiom is a +. The + means rotate one unit counter-clockwise, so the turtle will rotate 30° clockwise and its next heading will be 60°. Note that the length of one unit of movement is not needed as this will simply scale the drawing, and likewise the initial point on the screen is irrelevant as the drawing can simply be scaled and centered on the screen once the turtle has produced it.
For a simple example, let us choose our initial axiom to be simply F. We will have on transformation rule: F > F+F. Finally, we choose an initial heading of 0° (facing right) and a rotation unit of 90°. The axioms and images of the first 3 iterations of this grammar are given below.
 |
 |
 |
|
 |
1st iteration Axiom: F Translation: draw a line forward |
2nd iteration Axiom: F+F Translation: draw forward, turn left 90°, draw forward |
3rd iteration Axiom: F+F+F+F Translation: draw forward, turn left, draw forward, turn left, draw forward, turn left, draw forward |
My program for automating this process has two functions: Iterate() and Output(). The Iterate() function transforms the current axiom according to the given rules. The Output() function produces a PostScript file which is the translation of the current axiom into a fractal, using the method described above. When the program is first loaded, it takes as input the initial axiom, the transformation rules, the initial heading, and the rotation unit.
The Iterate() function uses a built-in Replace() function to replace certain parts of the axiom with other characters. During this process, it must keep track of which parts of the axiom have been transformed and which have not, because each rule applies only to those parts of the axiom that have not yet been transformed.
The Output() function examines each character of the current axiom from left to right. If the character is + or -, the heading is changed appropriately. The program keeps a stack of remembered positions. A stack is a collection of items with the property that the last item added to the stack is the first item removed from it. This is ideal for remembering positions. If the character being examined is [, then the current position is added to the stack. If the character being examined is ], then an item is taken from the stack (which will be the most recently remembered position). Then the program outputs a PostScript moveto command to move the turtle to this position.
If the character being examined is an F, G, f, or g, then the program must determine where to move the turtle to. If the current position is A, the program calculates the point B such that its distance from A is one unit, in the direction of the turtle's current heading. Then the program outputs a PostScript moveto command if the character is f or g, or a PostScript lineto command if the character is F or G, and moves the turtle to point B.
Aside from a couple of bookkeeping matters, that is entirely how the program works. One of these matters is path length. As the number of iterations increases, the path gets longer. In order to prevent problems with PostScript, the program introduces a cutoff length for paths. If the path exceeds this length, the program outputs a stroke, and then a newpath, followed by a A moveto command, where A is the current turtle position. This is repeated every time the cutoff length is exceeded.
The other bookkeeping matter involves visibility. The program keeps track of the largest and smallest x and y position values of the turtle during fractal generation. Once the generation is complete, the program calculates appropriate scale and translate values in order that the resulting image is centered on the page, and occupies as much of the page as possible. It then outputs these two commands at the start of the PostScript file it has generated.
Upon loading the program, calling Output() will produce the first iteration of the fractal image. Calling Iterate() will then generate the next iteration, and now Output() will produce the second iteration of the fractal image. By successively calling Iterate() and Output() in this way, a slide show of the consecutive iterations of the fractal image are produced.