This site, serving as my final project for PMATH 370, will explore a subset of the Lindenmayer Systems, commonly called L-systems, and present an interactive JavaScript applet that I wrote to visualize the output of such systems.

The applet (explained below) is available here, but you can also view some pre-rendered results.

Originally developed by a twentieth-century Hungarian botanist, L-systems were meant to describe the cellular growth patterns of simple plants and algae. Since then, they have found relevance as a method of visualizing fractals and fractal-like objects, generating recursive music, and automating architectural design, among other things. In fact, there even exists some research on relating recursive music to the corresponding tree image produced by the same L-system.

In all of the above applications, the basic method is exactly the same, but the interpretation of the output is where additional creativity has come in. To use this method, we define the following:

**alphabet**(or**variables**, or**nonterminals**) - set of symbols that can be replaced**constants**(or**terminals**) - set of symbols that will not be replaced**axiom**(or**initiator**, or**start**) - a string of variables and constants serving as the system's initial conditions**rules**(or**productions**) - a set of ordered pairs, the first element being a variable, and the second being a string of constants and variables with which to replace the first element upon each iteration of the system

These components together are what define a particular L-system.

Flexibility from the above definitions sometimes allows wider and more interesting applications. Some variations of the L-system definition allow for multiple rules per variable. One way this can be done is by all such rules being applied in order for one iteration. This is how my applet works, in fact, making it *deterministic*. Another way would be by a single rule being chosen randomly, perhaps using a weight function, per variable per iteration. In this case our system would be called *stochastic*. L-system representations of neurons can be formulated this way.

Another variation is to allow the first element of a rule to be a string of variables, rather than just a single variable. L-systems allowing this are *context-sensitive*. We'll employ that variation below.

To demonstrate computation using an L-system, consider the following:

- alphabet = {A, B, C}
- constants = {}
- axiom = "A"
- rules
- (A, ABCA)
- (BCA, BCABC)

This would produce the following output after each iteration (with spaces inserted between for clarity):

- A
- A BCA
- A BCA BCA BC
- A BCA BCA BC BCA BC BC
- A BCA BCA BC BCA BC BC BCA BC BC BC
- A BCA BCA BC BCA BC BC BCA BC BC BC BCA BC BC BC BC
- ...

This particular example was contrived, albeit not perfectly elegantly, so as to increase the number of symbols by the next odd number every iteration, so the result is that the *n*th iteration outputs *n*^{2} symbols. (The standard textbook example of such a 'counting' L-system is a bit simpler and generates the Fibonacci sequence. Other recursive and non-recursive sequences can similarly be generated using L-systems. Note that this example would have to be done differently if we disallowed context-sensitive systems.)

One application of L-systems arises when we interpret their output as instructions for drawing graphics. A simple, yet powerful, scheme for doing this comes from 'turtle programming', where a cursor (called the turtle) has its location and direction determined by a handful of basic commands, and drawing can only done where the turtle is. The turtle concept comes from the Logo programming language from the 1960's, but interpreting L-systems seems to have stronger roots in the program Fractint from the 1980's. Now one of the oldest open-source programs still apparently under active development, Fractint is a de facto standard (to some extent). It also uses the turtle concept, but its syntax is much different from Logo.

The L-systems we will look at more closely are those where certain symbols are reserved for turtle operations. Similar to other applets (see resources below), my applet uses a selection of commands from Fractint, but doesn't support its full repertoire:

- > increments the current angle by one degree.
- < decrements the current angle by one degree.
- + rotates the turtle by the current angle counter-clockwise.
- - rotates the turtle by the current angle clockwise.
- C rotates the current colour forward. (There are 16 preset colours.)
- D rotates the current colour backward.
- E moves the turtle forward without drawing.
- F moves the turtle forward while drawing.
- } multiplies the current forward-moving distance by a preset amount
*d*. - { divides the current forward-moving distance by
*d*. - [ starts a new sub-drawing (i.e., pushes the current turtle coordinates, angle, and forward-moving distance onto the stack.)
- ] finishes the current sub-drawing (i.e., restores the turtle to where it was at the most recent [ command in memory, then forgets this location.)
- Any other letters may be used (lowercase is recommended) for 'pure' variables that are not commands but will be replaced when the system is iterated. (The applet may have problems with certain non-alphabetic characters.)

I wanted to include a few features in my applet that I wasn't able to find in other similar applets, to make it easier to see what's going on in a given L-system in how it's being drawn, as well as what effects certain variables have on its graphical output. To that end, the applet has some colour features as well as some primitive ability to animate on certain variables.

One technique is to use non-command variables to represent an object drawn via a series of command variables. For instance, we might use a couple of rules like (t, [Csssss]) and (s, +[F]) if we know the current angle is relatively acute to add some random tassle-like decoration wherever we leave a 't' in the output. The '+[F]' increases the angle, draws forward, and returns (essentially, produces a branch.) The 'Csssss' is just shorthand for doing this several times in a new colour.

Most of the non-animating variables should be self-explanatory. Palettes wrap around, so if the turtle encounters CCC on a 3-colour palette, it's the same as if it hadn't encountered any C's, because it's back to the first colour. A note about the stroke width special options: the proportional option uses the distance the turtle will move divided by four as the width, so shorter lines will be thinner. But, if you don't use { and } in your turtle path, stroke width will be constant anyway. The colour-tied option means that 'earlier' colours are thicker, which can lead to some strange results if you have enough C's and iterations that the palette wraparound is encountered (for tree-like objects in particular, the 'trunk' will be thick, then thinner branches, then twigs may be as thick as the trunk again.)

The applet allows one to animate over the starting moving-forward distance and the starting angle to use for the + and - commands (this isn't the starting angle of the turtle itself, but rather the angle the turtle would turn if issued a + command before any < or > commands). If a field says "(can use for animation)" beside it, that means you can use the i loop variable in that field as part of an expression. (Using i in other fields will cause problems.) Expressions must be in valid JavaScript syntax, but mostly one would just use combinations of i, +, -, /, *, and numbers. ^, it should be noted, does not mean "to the power of". It's recommended that you only animate if a single frame can be produced in under a second. See the "Basic Animation" preset for an example.

The applet requires Firefox 1.5.0.8 or newer, since it uses the <canvas> tag. (Tested on Firefox 1.5.0.8 for Windows.) Also, it must have been compiled without disabling the canvas tag. In particular, pre-built binaries of Firefox for BeOS appear not to have canvas capability.

Be careful, since iterating too many times on too complex a structure may crash your browser. Try lower numbers first, especially on new structures. In fact, it's quite easy to break the applet, so make sure your input makes sense. To stop in the middle of rendering, just reload the page, or start another rendering. Another tip, if you're just doing a single frame, is to scroll down so that the rendering occurs off-screen. This will speed up the process.

The origin is in the upper-left corner (positive y = down), and the scale has one pixel as the unit.

The source is available: just view the source of the web page.

Resources used for research and inspiration (and to steal L-systems from) include: