Generating L-systems

An L-system is a mathematical notation that allows for generating beautiful self-repeating structures from a set of symbols and rules that apply to them. Suppose we want to mathematically model a fractal, we define an L-system as a tuple

\[G=(V, \omega, P)\]

in which \(V\) is our alphabet: all possible symbols that can exist within our system. The \(\omega\) is the initial set of symbols from which we can start applying our rewrite rules: our previously mentioned axiom. Finally we have \(P\), which consists of all rules that determine how a string of symbols needs to be rewritten to form the next iteration of symbols.

The rewrite rules can be defined as

\[p_i = v_i \rightarrow v_1 \Vert \dots \Vert v_N,\]

where every rule \(p_i\) is contained in \(P\), and every symbol \(v_i\) is contained in \(V\). The symbols before the arrow are called the antecedent, whereas symbols after the arrow are called the consequent. We use the \(\Vert\) sign to denote a binary operator which concatenates its left and right symbols. For instance, \(A \Vert B = AB\). The total number of symbols which are concatenated in the consequent is equal to \(N\).

In short, a rule declares that all symbols that match the antecedent must be rewritten to represent the consequent. Not all \(v_i\) need to exist as an antecedent, such symbols are constants. Symbols that are rewritten are called variables.

Let us now generate a Sierpinski arrowhead. This fractal can be generated by interpreting the iterations of the L-system

\[G_{s} = (V_s, \omega_s, P_s),\]

where

\[V_s = \{ A, B, -, + \},\] \[\omega_s = A,\] \[P_s = \{ A \rightarrow B-A-B, B \rightarrow A+B+A \},\]

which define the instructions for a turtle graphics renderer. Turtle graphics are generated by moving a virtual paintbrush (the turtle) across a virtual canvas by interpreting a series of commands. In this instance both \(A\) and \(B\) require the turtle to move forward, whilst \(+\) and \(-\) require the turtle to rotate \(60^{\circ}\) left and right, respectively. The result can be seen below: the Sierpinski arrowhead generated for multiple iterations i.

The generating code

Now that we know what an L-system is and how it should be generated in theory, we can start creating an simple l-system generator in code. Our approach will be simple and sequential, which is more than adequate for most implementations of L-system generators. There are more advanced parallel solutions, which we will discuss in the future. First though, like many algorithms, it is important to learn how to solve the problem sequentially.

Let’s translate our L-system’s tuple to a simple set of structures:

typedef struct {
    const char antecedent;
    const char * consequent;
    size_t rewrite_length;
} Rule;

typedef struct {
    char * symbols;
    size_t length;
    size_t space;
} SymbolList;

typedef struct {
    Rule * rules;
    size_t length;
    size_t space;
} RuleList;

typedef struct {
    const SymbolList axiom;
    const RuleList rules;
} LSystem;

I’m sorry for those who don’t like C very much (I understand why, I just tend to enjoy the clear view of memory it provides, please bear with me). You should look primarily at lines 19 to 22 in any case. We have our axiom representing \(\omega\) and our rules representing \(P\). Once we have loaded any given L-system into our structure above (using, for example bool try_load_system(LSystem * system, const char * file_path)), we can start applying the rules for \(N\) interactions.

const size_t MAX_SYMBOLS 1e15;

void generate_system(LSystem * system, unsigned int num_iterations) {
    for (unsigned int iteration = 0; iteration < num_iterations; iteration++) {
        apply_rules_to_symbols(system.rules, &system.axiom);
        if (system.axiom.length > MAX_SYMBOLS) {
            printf("The axiom is too large, try decreasing the iterations.");
            return;
        }
    }
}

You will notice a two things.

• MAX_SYMBOLS is there to prevent a memory overflow. The same holds for lines 6-9, we check the size of the current iterations’s axiom and exit the current iteration if it is too large. Decrease or increase the maximum depending on the amount of CPU memory available on your machine. One symbol requires 1 byte of memory, so if you have 6 GB of free memory you will have space for about just a bit more than \(6*10^9\) symbols.
• apply_rules_to_symbols is called for num_iterations times (\(N\)). This is the crux of our implementation, simple repeated rewriting.

Let’s look at the implementation of this repeated rewrite method.

void apply_rules_to_symbols(RuleList rule_list, SymbolList * symbol_list) {
    SymbolList next_symbol_list = copy_symbol_list(symbol_list);
    // Loop over all symbols in the axiom
    for (unsigned int symbol_index = 0; symbol_index < symbol_list->length; symbol_index++) {
        const char symbol = symbol_list->symbols[symbol_index];
        
        // Find a rule that applies to the current symbol
        unsigned int rule_index = 0;
        for (; rule_index < rule_list.length; rule_index++) {
            Rule rule = rule_list.rules[rule_index];
            if (rule.antecedent == symbol) {
                // Matching rule found, apply the rule.
                add_symbols_to_list(rule.consequent, &next_symbol_list);
                break;
            }
        }

        // If we did not break, we did not find an applicable rule.
        if (rule_index == rule_list.length)
            add_symbol_to_list(symbol, &next_symbol_list);
    }

    // Swap the axiom with our new list and free the memory.
    swap_symbol_list(symbol_list, &next_symbol_list);
    free_symbol_list(&next_symbol_list);
}

Hopefully the comments make it pretty clear what is happening: we loop over all symbols, search for an antecedent that matches the current symbol, and if so we place the consequent in the next_symbol_list. If no applicable rule is found, the current symbol must be a constant, and thus we simply copy the same symbol to the next list.

The rendering code

We briefly touched upon rendering a generated set of symbols, and luckily for us it’s not that difficult to implement. Our list of requirements is short:

• Have a virtual paintbrush that draws contiguous lines wherever it moves.
• This paintbrush can move move forward when parsing \(A\) or \(B\).
• This paintbrush can rotate \(60^{\circ}\) to the left when parsing a \(+\).
• This paintbrush can rotate \(60^{\circ}\) to the right when parsing a \(-\).

If we implement a simple rendering library on top of, let’s say SDL2, our rendering code will thus look like:

const int MOVE_SIZE 1;
const int ROTATE_ANGLE_DEG 60;

void render_symbols(SymbolList symbol_list) {
    // Init start position and add to the list.
    int current_rotation = 0;
    Point current_position = { 0, 0 };
    PointList point_list = init_point_list();
    add_point_to_list(&point_list, current_position);

    // Build a polyline based on the symbols and movement rules
    for (unsigned int symbol_index = 0; symbol_index < symbol_list->length; symbol_index++) {
        const char symbol = symbol_list->symbols[symbol_index];
        if (symbol == 'A' || symbol == 'B') {
            current_position = move_point(current_position, current_rotation, 1);
            add_point_to_list(&point_list, current_position);
        }
        else if (symbol == '+')  {
            current_rotation += ROTATE_ANGLE_DEG;
        }
        else if (symbol == '-') {
            current_rotation -= ROTATE_ANGLE_DEG;
        }
    }

    // Render the build polyline
    render_polyline(point_list);
}

We simply walk through the symbols and add points to a poly-line (the point_list) whenever we move the cursor forward. Once the poly-line is build we render it using our rendering library of choice.

Feel free to take these pieces of code and build your own L-system renderer! Or, if you want to have a solid piece of code to work with, take the sources to my little L-system generator I wrote for the Floppy Challenge.

As I said before, there are more advanced parallel solutions I’ll discuss. I do want to stress that the speed-up is less useful than you think, and maybe I’ll make a post about that one day. For now, let’s have a look at some other L-systems my little program rendered.

Ah, never let people say programmer-art cannot be nice (even if it is deterministically created).