Turtles and Grammar

The first program that I wrote solo and self-motivated was a creative project. I wanted to draw a tree. I placed some squares on a grid and assigned them various colours. The squares that were in the middle third of the image were painted various shades of brown for the trunk and the squares in the top half were painted various shades of green for leaves. It wasn't overly complicated, but it also did not need to be.

Although a lot has changed since I first wrote that tree program in Visual Basic, it was retrospectively very impactful and one of my early inflection points. Creative coding is expressive, fun, and meaningful. I want to revisit "drawing a tree" with a handful of different techniques (spoilers: it was just as fun as the first time).

Grammars

Formal Language Theory defines a language's Grammar as a ruleset for forming a string of characters from that language's alphabet. Grammars are effectively descriptions of allowed structures and shapes within the language without prescribing meaning (semantics) to the created strings.

Grammars are represented as transformations from symbols to other symbols. Symbols that can be transformed into other symbols are non-terminal symbols and are represented with capital letters. Terminal symbols are represented as lowercase letters and cannot be transformed further. In an ambiguous language there are multiple ways to transform non-terminal strings, resulting in different final strings.

Consider the grammar example:

Because it's an ambiguous grammar with multiple rules for the non-terminal E symbol, there are different possible outcomes. Consider one example derivation from the starting $S$ string:

L-Systems

One especially interesting type of grammar is the Lindenmayer system. Aristid Lindenmayer described plant development and behaviour of plant cells with his L-Systems. Plants and trees are examples of well-known L-Systems in two dimensions.

We can use L-Systems to model the growth of a tree (and how to draw it)! One such grammar for drawing a fractal plant can be described as follows.

Each of the symbols in the language has a meaning for when we draw our tree. The X is a non-terminal symbol, but the other symbols are constants described in the following table.

Examining the first derivation of the starting string fX, we can see that applying $X → [-fX]+fX$ would end up with f[-fX]+fX. Ignoring the non-terminal X symbols, this translates to:

• Draw a line forward
• Remember this position
• Turn left and draw forward
• Return to the previous position
• Turn right and draw forward

We can now create a function to derive n iterations (or steps) of our grammar. Luckily, our grammar is not ambiguous and we can just recursively apply the same single transformation rule over and over.

1
    function grammarParser(input: string, iterations: number) {
2
        while (iterations > 0) {
3
            iterations--;
4
5
            input = input.replaceAll("X", "[-fX]+fX");
6
        }
7
        return input;
8
    }
9

We now have our drawing instructions. But how do we actually represent this as a tree?

Drawing with Turtles

Turtle graphics describe a simple digital drawing technique that is based around a paintbrush's (referred to as a Turtle) movements relative to its current position. Imagine drawing a line without lifting the pen or... a turtle walking across your canvas. So far, we have described our tree language's grammar (syntax), and now our turtle will draw the tree based on the meaning (semantics) of the language's alphabet.

A turtle will be represented by its current position and angle. The turtle also needs to remember the previous positions and angles as requested by the derived instruction set.

1
    interface Location {
2
        x: number;
3
        y: number;
4
        angle: number; // in radians
5
        length: number; // length of the next segment
6
    }
7
8
    interface Turtle {
9
        location: Location;
10
        history: Location[]; // to be treated as a stack
11
    }
12

Now our turtle needs to interpret each instruction and perform the required paint stroke. I have chosen to use the HTML5 Canvas API to draw to the page. The majority of the code is telling the turtle what to do when encountering each symbol from our grammar.

1
    function turtleWalk(instructions: string) {
2
        const draw = document.getElementById('canvas').getContext('2d');
3
4
        const turtle: Turtle = {
5
            // start the turtle at the bottom-middle position pointing up
6
            location: {
7
                x: draw.canvas.width / 2,
8
                y: draw.canvas.height,
9
                angle: Math.PI / 2,
10
                length: draw.canvas.height / 3,
11
            },
12
            history: [],
13
        }
14
15
        for (const instr of instructions) {
16
            draw.beginPath();
17
            draw.moveTo(turtle.location.x, turtle.location.y);
18
19
            if (instruction === 'f') {
20
                // move the turtle based on its angle
21
                turtle.location.y -= turtle.location.length * Math.sin(turtle.location.angle);
22
                turtle.location.x += turtle.location.length * Math.cos(turtle.location.angle);
23
                turtle.location.length /= 2;
24
                // draw our line!
25
                draw.lineTo(turtle.location.x, turtle.location.y);
26
            } else if (instruction === '+') {
27
                turtle.location.angle -= Math.PI / 4;
28
            } else if (instruction === '-') {
29
                turtle.location.angle += Math.PI / 4;
30
            } else if (instruction === '[') {
31
                // store our current location in the history
32
                turtle.history.push({...turtle.location});
33
            } else if (instruction === ']') {
34
                // restore our most recent location
35
                turtle.location = turtle.history.pop();
36
            }
37
38
            draw.closePath();
39
            draw.stroke();
40
        }
41
    }
42

If we run that code we can produce a tree! I have applied some colours to the canvas, but you should see a result very similar to below.

Interactive

Finally, I built an interactive version of our turtle and grammar! Feel free to experiment with your own grammar rules and angle delta!

I hope that you had fun learning a little bit about Turtles and Grammars. The cross-domain usage of Grammars has always fascinated me and I love that it extends into the realm of graphics. Plus, I had a ton of fun revisiting one my earliest inspirations to program.

Thank you for reading. Thank you for exploring ideas with me.