L Systems - introduction and Koch curves

Martin McBride

2019-06-30

In this post we will look at simple L Systems and how they can be used to create fractal images in generativepy. We will make use of the simple turtle system developed in a previous post.

What is an L System?

An L System is primarily a way of manipulating strings of characters. It starts with an initial string, and applies a set of rules repeatedly to generate more complex strings.

L Systems were developed by Aristid Lindenmayer, a biologist, to model plant growth. But L Systems can also be used to describe fractals. And, not surprisingly given its origins, it is very good at creating natural looking fractals such as tree and fern like structures.

Although L Systems work on character strings, we can convert them into images by treating each character in the string as a drawing instruction. In this post we will treat the characters as instructions for the turtle system we introduced in the post mentioned above.

A simple L System - algae

To define an L System, we first define the alphabet (or set of symbols) it uses. To keep things simple, we will use an alphabet that consists of just two letters, A and B.

We then have to define a set of rules. The rules are used to transform a string of symbols into a different string. In an L System, there is one rule for each symbol, and it determines how that symbol is transformed. The tow rules we will use are:

A becomes B
B becomes BA

Finally we define our initial string, sometimes called the axiom. We will start with the string A.

Iteration 1

On each iteration we take each character in the current string, and apply the rules to create a new string.

Our current string is A, so we apply the rule A becomes B, giving us a new string B.

Iteration 2

Our current string is now B, so we apply the rule B becomes BA, giving us a new string BA.

Iteration 3

Our current string is now BA. Applying the same rules, the first character, B becomes BA and the second character A becomes B. We join these together to form the new string BAB.

Iteration 4

Our current string is now BAB. The first B becomes BA, the A becomes B, and the second B becomes BA. The new string is therefore BABBA

If you continue this, the next string will be BABBABAB, and then BABBABABBABBA and so on.

This system is meant to give a very crude model of how algae grows. One thing you might notice is that the lengths of the strings are 1, 1, 2, 3, 5, 8, 13 ... the Fibonacci series.

Algae in Python

Before attempting to draw anything, lets implement this system as a simple Python program:

AXIOM = 'A'
RULES = { 'A' : 'B',
          'B' : 'BA'}
ITERATIONS = 6


def lsystem(start, rules):
    out = ''
    for c in start:
        s = rules[c]
        out += s

    return out


s = AXIOM
print(s)
for i in range(ITERATIONS):
    s = lsystem(s, RULES)
    print(s)

We have defined our AXIOM (the initial string), and our set of RULES. The rules are implemented as a Python dictionary. For each input symbol, the dictionary supplies the string that the symbol will be replaced with.

The lsystem function accepts parameters start (the string to be converted) and rules (the rules dictionary). It loops over every character in the string, converting it via the rules dictionary, and adding it to the end of the output string.

Finally the main loop iterates 6 times, printing the output string at each stage.

Creating a drawing with an L System

So how do we use L Systems to create drawings?

A simple way is to make each letter represent an operation using the turtle graphics system mentioned above (article here). We could use:

F to represent the turtle moving forward by a certain distance (we will call it LENGTH)
+ to represent the turtle turning left by a certain angle (we will call it ANGLE)
- to represent the turtle turning right by the same angle

Now lets set our rules:

F becomes F+F-F-F+F
+ becomes +
- becomes -

Symbols like + or - that are always replaced with themselves are called constants in a L System.

Our axiom (starting string) will be F, LENGTHis 10 and ANGLE is 90 degrees (pi/2 radians).

After one iteration, the initial F will be replaced with F+F-F-F+F. This string can be interpreted as:

Forward 10
Left pi/2
Forward 10
Right pi/2
Forward 10
Right pi/2
Forward 10
Left pi/2
Forward 10

This draws a shape like this:

You might recognise this shape from the article on Koch curves. This is the basis for the rectangular Koch curve.

On the second iteration, each F is replaced with F+F-F-F+F, which means each line is replaced with the figure above.

On the third iteration, each F is replaced again, giving F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F. On the 4th and 5th iterations the string gets longer and longer. Here is what we get if we draw the curve represented by each string:

There are two things to notice about this curve. The first thing is that as the number of iterations grows, the curve gets bigger and bigger. We need to scale down the 4th and 5th iteration because they are too big to draw at the same scale. If you think about it, this is also how most plants grow. They start off small and simple, and as they grow they get bigger and more complex.

The other thing to notice is that the string contains a full description of the curve. The drawing code just needs to follow the drawing instructions, one after another. The recursive nature of the shape in encoded into the string itself.

Koch curve L System in Python

Here is the Python code to draw the shape above:

from generativepy import drawing
from generativepy.drawing import makeSvg
from generativepy.color import Color
from turtle import Turtle
import math

AXIOM = 'F'
RULES = { 'F' : 'F+F-F-F+F',
          '+' : '+',
          '-' : '-' }
ITERATIONS = 2
ANGLE = math.pi/2
LENGTH = 10
SIZE=800


def lsystem(start, rules):
    out = ''
    for c in start:
        s = rules[c]
        out += s

    return out

def draw(canvas):
    s = AXIOM
    print(s)
    for i in range(ITERATIONS):
        s = lsystem(s, RULES)

    turtle = Turtle(canvas)
    canvas.stroke(Color('darkblue'))
    canvas.strokeWeight(2)
    turtle.moveTo(10, SIZE-10)
    for c in s:
        if c=='F':
            turtle.forward(LENGTH)
        elif c=='+':
            turtle.left(ANGLE)
        elif c=='-':
            turtle.right(ANGLE)


makeSvg("lsystem-koch-curve.svg", draw, pixelSize=(SIZE, SIZE))

The lsystem function is the same as defined above, but with a different set of rules.

The draw function is a standard drawing function used in generativepy. It has three main parts.

The first part of the draw function executes the L System:

    s = AXIOM
    print(s)
    for i in range(ITERATIONS):
        s = lsystem(s, RULES)

This runs the L System ITERATIONS times, to create the final string.

The second part sets up the Turtle system with a suitable stroke colour and weight. It also moves the current turtle position to the bottom left of the canvas:

    turtle = Turtle(canvas)
    canvas.stroke(Color('darkblue'))
    canvas.strokeWeight(2)
    turtle.moveTo(10, SIZE-10)

Finally we loop through every character in the string created by the L System. For each character we perform the required operation:

    for c in s:
        if c=='F':
            turtle.forward(LENGTH)
        elif c=='+':
            turtle.left(ANGLE)
        elif c=='-':
            turtle.right(ANGLE)

Notice that we use makeSvg to create an SVG image rather than a PNG image. The SVG can be opened ib an SVG editor, such as Inkscape, and is scalable. You can use makeImage to create a PNG image if you prefer.

Things to try

You can try varying the number of ITERATIONS to create different levels of Koch curves like the ones shown in the diagram above. The more iterations, the bigger the image. You will probably need to adjust the SIZE of the image, but you could also try adjusting the LENGTH of the lines used, to create a smaller image.

Koch curve variants

There are several variants of the Koch curve. One, probably more familiar, variant is the triangular form.

We use the rules:

F becomes F+F--F+F
+ becomes +
- becomes -

And set ANGLE to pi/3 (that is, 60 degrees, the angle inside an equilateral triangle).

With the new rule for F, the basic shape is now:

Notice that the rule contains a double -. This creates the point at the top of the triangular shape. It also ensures that the basic shape sits of a straight line, because the number of left turns and the number of right turns are the same. Here are the first 5 iterations:

You can explore these by altering the rule and angle in the previous code.