Introducing L-Systems

My apologies, I haven't been writing as much these days; I've been having a bit of a blogger's block as to what to write about. I've got a few other statistics articles in mind, however since I enjoy variety I don't really want to write about the same thing all the time. So I'll reach out to the readers, is there any topic in particular you'd like me to write about?

Now that that is taken care of, we can get down to business. I've been doing a lot of reading these days, and one thing that I've stumbled upon are a nifty little computer science topic called L-systems. These things are quite simple to describe, yet are able to produce all sorts of interesting results (have you noticed a common theme to some of my blog posts these days?).

You need 3 things to describe an L-system. The first is an alphabet. An alphabet is very simple, it is just a set of characters that you will use within your alphabet - nothing more, nothing less. This is similar to a programming language where your alphabet is some subset of the ASCII character set unless you're using something more esoteric like APL (which is actually pretty neat, I've been looking at it a bit recently and I might put up a post about it soon - I guess I don't have blogger's block after all! You're still welcome to give requests though :) ).
The next thing you need for an L-system is an axiom. An axiom is simply a finite, non-empty string from your alphabet. You can also call it a seed if you like. The axiom (or seed) serves as the basis for the growth of the system.
The third thing is the most important - the production rules. What these do is map a character in the alphabet to some string. You apply the production rules on the axiom by converting each character in the axiom to whatever the rules say it maps to.

Let's consider an example L-system:

Alphabet: F, +, -
Axiom: F++F++F
Rules:
F -> F-F++F-F
+ -> +
- -> -

It is not necessary to specify the rules for + and -, since if you don't include them it is assumed that they just map to themselves (the identity function).

Let's run this L-system through one iteration. Begin with the axiom:

F++F++F

Then apply the rules:

F-F++F-F++F-F++F-F++F-F++F-F

I'd go for another iteration or two, but as you can see this thing will grow quickly and the text would probably run outside of this div. I'll just let you use your imagination as to what the next iteration would look like.

You may wonder why I picked this specific alphabet, as it looks rather peculiar. It turns out that this alphabet is directions for a turtle. The F means go forward, the + means turn left, and the - means turn right, all the while drawing a line.

Suppose we make the angle that the turtle turns equal to 60 degrees and iterate 4 times, you'll end up with a picture like this:

If you iterated this L-system an infinite number of times and at each iteration divide the distance that the turtle moves on each F by 3, you would end up with a fractal called the Koch snowflake (I made the mistake of saying that name out loud to my girlfriend, which caused her to giggle uncontrollably - perhaps I pronounced it wrong).

The next thing we can do is give our turtle an upgrade. In the current state, the turtle is limited to only drawing convoluted lines. While this is good, there are a great many interesting things to draw that aren't lines. We can change this by adding a powerful new feature to the turtle with these two symbols: [ and ]. The [ will push the current state of the turtle onto a stack (there is only one stack, so I should call it the stack), and ] will pop that state off of the stack and restore the turtle to that state.

This gives us a lot more power to create interesting images. Consider this L-system:

Alphabet: F, [, ], +, -
Axiom: F
Rules:
F -> FF-[-F+F+F]+[+F-F-F]

If you iterate this system 4 times, use an angle of 22.5 degrees and a step size of 6 pixels for your turtle, you get something like this (grabbed from The Algorithmic Beauty of Plants (The Virtual Laboratory)):

That's a bit cooler! And that image is generated by a completely deterministic process (aka no randomness). Which means that unlike my fractal trees, you will get exactly the same picture if you follow the rules above.

You can take these L-system things much much further, however I can see your eyes beginning to glaze over, so I will save that discussion for another day. As for code, you can see the L-system parser here, and the turtle graphics renderer here.