Martin McBride, 2019-06-30

Tags generativepy generativepy tutorials koch curve turtle recursion l systems

# L Systems - introduction and Koch curves

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`

, `LENGTH`

is 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.