L-Systems

In these notes you will learn:

• How to draw simple turtle graphics using a string of commands.
• What an L-system is.
• How to use an L-system to draw pictures.

Introduction

In this note we will see a remarkable way of creating a wide variety of patterns using sets of rules called L-systems. For instance, L-systems can be used to generate realistic looking trees and plants.

Turtle Graphics String

Recall this program for drawing a square using turtle graphics:

Turtle t = new Turtle();

t.forward(10);
t.right(90);
t.forward(10);
t.right(90);
t.forward(10);
t.right(90);
t.forward(10);

This is a lot of typing! We could simplify it using a code, e.g.:

• F means t.forward(10)
• + means t.right(90)

Then the drawing for the square is the string "F+F+F+F". We’ll call this a turtle string, or a turtle program. Treating the string "F+F+F+F" as a program may seem strange at first, but it makes sense. It’s just a very compact encoding of the instructions for drawing a square.

We can write a function takes a turtle string as input and runs it:

void drawTurtle(String prog) {
  int i = 0;
  while (i < prog.length()) {
    char c = prog.charAt(i);
    if (c == 'F') {
      t.forward(10);
    } else if (c == '+') {
      t.right(90);
    }
    ++i;
  }
}

The idea here is that the while-loop examines the characters in prog one character at a time. If it sees an F, then it makes the turtle move forward 10 pixels, and if it sees a + it makes the turtle turn 90 degrees to the right.

In general, we don’t always want to move forward 10 pixels, or turn right 90 degrees. So a useful improvement to this function is to also pass in the step size and the turn amount:

void drawTurtle(String prog, float stepSize, float turnAmount) {
  int i = 0;
  while (i < prog.length()) {
    char c = prog.charAt(i);
    if (c == 'F') {
      t.forward(stepSize);
    } else if (c == '+') {
      t.right(turnAmount);
    }
    ++i;
  }
}

This makes the drawTurtle much more flexible, e.g.:

drawTurtle("F+F+F+F", 10, 90);   // a square
drawTurtle("F+F+F+F", 100, 90);  // a bigger square

We can also use it to draw other shapes:

drawTurtle("F+F+F", 100, 120);           // an equilateral triangle
drawTurtle("F+F+F+F+F", 100, 72);        // a pentagon (5 sides)
drawTurtle("F+F+F+F+F+F+F+F", 100, 45);  // an octagon (8 sides)
drawTurtle("F+F+F+F+F", 100, 144);       // a 5-pointed star

One more convenient change to make drawTurtle is to allow the symbol '-', which means a left turn, i.e. the opposite of '+'. So let’s add that:

void drawTurtle(String prog, float stepSize, float turnAmount) {
  int i = 0;
  while (i < prog.length()) {
    char c = prog.charAt(i);
    if (c == 'F') {
      t.forward(stepSize);
    } else if (c == '+') {
      t.right(turnAmount);
    } else if (c == '-') {
      t.left(turnAmount);
    }
    ++i;
  }
}

L-Systems

An L-system is a set of rules system for re-writing strings. For example, here is a simple L-system:

• Starting string: “F”
• Replacement rule: replace “F” with “F+F−F−F+F”

The idea is to start with “F”, and then to repeatedly apply the replacement rule, e.g.:

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+F+F+F−F−F+F
...

Each string is created by applying the replacement rule to the previous string. To get things started we are simply told that the first string is F, but after that each new string comes from the previous one. Note also that the non-F characters are copied into the next string without any change.

Now, if you interpret the output these as turtle strings, then we can draw them, e.g.:

drawTurtle("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", 30, 120);

This draws a tree-like shape with, perhaps, a bird on top. Try re-running this with angles other than 120 and you will see many different shapes.

The strings get long pretty quickly, and so they are impractical to generate by hand. So lets write a function to create the strings for us:

String makeString(int n) {
  if (n <= 1) {
    return "F";
  } else {
    String prev = makeString(n - 1);  // recursive call
    String result = "";
    int i = 0;
    while (i < prev.length ()) {
      char c = prev.charAt(i);
      if (c == 'F') {
        result += "F+F-F-F+F";
      } else {
        result += c;
      }
      ++i;
    }
    return result;
  }
}

An interesting feature of this function is that it calls itself at this line:

String prev = makeString(n - 1);  // recursive call

A function that calls itself is a recursive function, and it is quite useful in this case. The idea is that to generate the string n, you first (recursively) generate string n - 1 and then apply the replacement rule to it. The only exception is the case where n is 1, and then we immediately return "F".

This is just one example of an L-system. There are many others that generate a wide range of interesting pictures of things like Sierpinski triangles, Hilbert curves, dragon curves, and even fractal plants.

Questions

1. Suppose s is a String variable with at least 100 characters in it. Write a fragment of code that prints the first character of s.
2. What is a recursive function?

Example Program

Turtle t;

void setup() {
  size(500, 500);
  noLoop();
  t = new Turtle();
}

void draw() {
  background(255);
  String prog = makeString(4);
  drawTurtle(prog, 20, 90);
}

void drawTurtle(String prog, float stepSize, float turnAmount) {
  int i = 0;
  while (i < prog.length()) {
    char c = prog.charAt(i);
    if (c == 'F') {
      t.forward(stepSize);
    } else if (c == '+') {
      t.right(turnAmount);
    } else if (c == '-') {
      t.left(turnAmount);
    }
    ++i;
  }
}

String makeString(int n) {
  if (n <= 1) {
    return "F";
  } else {
    String prev = makeString(n - 1);
    String result = "";
    int i = 0;
    while (i < prev.length ()) {
      char c = prev.charAt(i);
      if (c == 'F') {
        result += "F+F-F-F+F";
      } else {
        result += c;
      }
      ++i;
    }
    return result;
  }
}

class Turtle {
  float x;
  float y;
  float angle;
  boolean penUp;
  color penColor;

  Turtle() {
    x = width / 2;
    y = height / 2;
    angle = 0.0;
    penUp = false;
    penColor = color(0);
  }

  void penDown() {
    penUp = false;
  }

  void penUp() {
    penUp = true;
  }

  void setColor(color c) {
    penColor = c;
  }

  void left(float degrees) {
    right(-degrees);
  }

  void right(float degrees) {
    angle += degrees;
  }

  void forward(float dist) {
    float dx = dist * cos(radians(angle));
    float dy = dist * sin(radians(angle));
    if (!penUp) {
      stroke(penColor);
      line(x, y, x + dx, y + dy);
    }
    x += dx;
    y += dy;
  }
} // class Turtle