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:
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:
This would produce the following output after each iteration (with spaces inserted between for clarity):
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 nth iteration outputs n2 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:
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: