Drawing Fractals with Lindenmayer Systems

By Monty, 17th June 2015

Hilbert Curve

Hilbert Curve

Lindenmayer systems, or L-systems, provide a very powerful way to construct fractals. Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development. An L-system is a rewriting system and a type of formal grammar. It consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial “axiom” string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.

For a simple example, let’s look at Lindenmayer’s original L-system for modelling the growth of algae. There are 2 ‘variables’, A and B. The rules are that (1) whenever we see A, we replace it with AB, and (2) whenever we see B, we replace it with A. We start with the string ‘A’, so that becomes ‘AB’ by rule 1. There’s nothing more in the original string, so now we scan ‘AB’. Again, the ‘A’ gets replaced by ‘AB’, and we move on to the next character, which is ‘B’; that gets replaced by ‘A’ so now the string has become ‘ABA’. On our third iteration, the string becomes ‘ABAAB’. The next one is ‘ABAABABA’. And so on. (Just as a side note, the lengths of these string are 1, 2, 3, 5, 8… remind you of anything? Hint, put another ‘1’ at the beginning of the sequence, and add it to the next number.)

We can extend this basic system with some drawing instructions, such as ‘-‘ means “turn left by some angle”, and ‘+’ indicates a right turn; ‘F’ could say “go forward”. These instructions can then be implemented very simply using Turtle graphics. For example, the Hilbert curve can be drawn using these rules:

A → − B F + A F A + F B −

B → + A F − B F B − F A +

A note about the implementation: this one is remarkably simple because we do the string replacements ‘on-the-fly’ with mutually recursive function calls. You’ll often see L-systems implemented by scanning the axiom (usually the first production rule) and building up the replacement string, and then scanning that, and so on until the string has been developed as far as needed. Then that string is ‘interpreted’ (like a little programming language!) to draw the picture. I’m not sure why they do that – presumably there’s a good reason? – but my way is much easier to understand!

Here’s a Dragon Curve:

This next one adds a new feature – the ability to save values for future use, by pushing them onto a stack, and popping them off later. Push is indicated by ‘[‘, and pop by ‘]’. I hope you can see that there’s the beginnings of a realistic looking tree when the program has finished! Just add some scenery and textures…?

Wikipedia:

An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures. L-systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist at the University of Utrecht. Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development. L-systems have also been used to model the morphology of a variety of organisms and can be used to generate self-similar fractals such as iterated function systems.

What do you think?

Leave a Reply

%d bloggers like this: