Lindenmayer Systems

11 Dec 2014

Charnia

I was watching the First Life documentary which chronicles the origins and evolution of life. In the documentary, they make a mention of Charnia a frond-like primitive organism. It lived deep underwater and fed of nutrients in the water. Sadly, it went extinct and has no extant descendants. Since it is one of the oldest known multicellular organisms it provides great insights into the origins of such beings.

This is what they supposedly looked like,

Now, you may be wondering why I’m talking about something that hasn’t been around for over 500 million years. Well, I was struck by the beauty and simplicity of the organization of it’s cells. These organisms adopted fractal branching to generate their body structure.

Since this organism had to absorb its sustenance from the ocean, it needed a very high surface area and compact packing. Fractal arrangements were perfect for this. It’s truly amazing how resourceful these organisms were to use relatively simple instructions can give rise to amazingly beautiful patterns. They necessarily couldn’t be too elaborate in their designs.

Lindenmayer systems

Digging deeper into this topic is where I found Lindenmayer Systems or L-systems for short. Developed by Astrid Lindenmayer, a Hungarian biologist in 1968, they provide a clear and simple way to model fractal growth.

An L-system is basically a type of formal grammar, in other words, it defines a language – basically a set of acceptable strings. It has three basic components,

Set of alphabets used to compose the strings
An axiom (starting string)
Rewrite rules

The set of strings belonging to this language is generated by first starting out with a set containing the axiom. Then we generate new strings by applying all applicable rewrite rules to the strings in the set.

Rewrite rules or production rules as you may have heard of them consist of a left-hand side and a right-hand side. Any substring matching the left side can be substituted with the string on the right side. As with any formal grammar, an L-system is context-free if there is only a single symbol in the left hand side of the production.

L-system models are greatly suited to generate self-similar or fractal patterns because the rewrite rules can be recursively expanded.

Logo

I remember back in school when we were first introduced to computers and programming, we were taught the Logo Programming Language. I thought this was just one of those things you were taught in school and never had to use later. Well, turns out I was wrong, the little turtle wasn’t dead yet. Most L-systems use a Logo-like paradigm to implement graphics.

In a relatively simple model, the turtle’s state encapsulates of four parameters,

x co-ordinate.
y co-ordinate.
Angle of orientation
Color of line drawn.

Stateful drawing commands help us generate graphics for every derived string. Each symbol is associated with a Logo command and every string is interpreted as a sequence of commands that is executed by the interpreter to generate the final pattern.

Mechanism

Consider, a relatively simple grammar.

The set of symbols is, {A, B, C, R}

Production rules are,

A : A B A C A B A

Now, I must mention here that for any symbol (X) lacking any rewrite rule, we assume an identity expansion, i.e.

X : X

The axiom is R A. The R symbol is just used to get the orientation correct.

Consider these draw rules for the symbols,

A = FD 10
B = RT 60
C = LT 120
R = RT 90

Initially, the string representing the state of the system is,

R A

Substituting the symbols' logo equivalents we get the sequence,

RT 90
FD 10

The graphical representation of the system looks like,

On iterating once, we apply the production to expand all the symbols we can. Our string becomes,

R A B A C A B A

Logo sequence equivalent,

RT 90
FD 10
RT 60
FD 10
LT 120
FD 10
RT 60
FD 10

Evaluating these commands in an interpreter, we get the graphical representation,

Iterating again, we continue to expand and our string becomes,

R A B A C B A B A B A C B A C A B A C B A B A B A C B A

OK, that’s big. As you may have probably guessed, the string size grows exponentially.

It looks like,

If you look at what this system is actually doing in simple terms, it’s simply replacing every straight line in the figure with a small triangular bump. This substitution is recursively applied to any lines in the resulting figure to give rise to self-similarity.

Another iteration and we get something looking like this,