L–system II.
11.01.2017

As I promised before, this is the second article concerning L–system topic. This time we will try to cover a little bit theory and also implementation details of L–system web application implemented in JavaScript.

A little theory shouldn't hurt you (or you can skip).

L–system is a formal grammar system, which can be used for modeling grow of plants. What does it mean? As you know, natural languages has grammars – set of rules showing us how to compose words into sentences and so. Besides natural languages (used by people for communication), there are also artificial languages used for example to program computers – all these Java, C, JavaScript, … are the case. Those artificial languages has also grammars and there is classification of the formal grammars called Chomsky hierarchy, which divides formal grammars to the categories or levels. Formal grammar generates, from finite set of symbols and rules, formal language (usually infinite). L–system is a such kind of formal grammar.

We can define: Let G(∑, A, P) be a 3-tuple, where ∑ is a finite, non empty set of symbols, A ∈ ∑⁺ and P is a finite, non empty set of rules in form (a ∈ ∑) → (b ∈ ∑⁺).

∑⁺ is a positive closure on ∑ (∑⁺ = apply[+ on 2^∑ - ∅], where + is a concatenation). We call A as axiom – it is a starter sequence. We defined deterministic (one symbol has just one rewriting rule) and context free (rewriting takes place no matter of surrounding symbols) L–system, because this kind of grammar system is currently (in time of writing) implemented in described web application. It could be extended in future.

Example:

• ∑ = {A, B}
• A = A
• P = {A → AB}

Language, generated by the example, is not very useful, but you get the idea. Now Aristid Lindenmayer comes to our show. He wanted to model grow of (not only) algae, consisting of 2 kinds of cells. It can be easily modeled by L–system:

• ∑ = {A, B}
• A = A
• P = {A → AB, B → A}

Turtle graphics.

Until now, it was nice theory, but I guess, most of people like some graphical output more, than ABAABABAABAAB sequences. Turtle graphics is such mechanism, which is really suitable for our L–system visualisation. It is an alternative to the 'normal' strict coordinate graphics system. Main idea is, that there is a turtle. And turtle, when moving, creates tracks in sands.

Source: https://pixabay.com/en/sea-turtle-kemp-s-ridley-beach-sand-1503473/

Ok, let's be a little bit more formal. A turtle is defined by it's state. Then set of commands exists, which changes state of the turtle and these changes can draw lines. State of turtle is defined by:

• Orientation
• Location

Canvas after interpreting F.

Canvas after interpreting F-F.

Canvas after interpreting F-F++F.

Canvas after interpreting F-F++F-F.

Well, I suppose, it is clear now, how turtle graphics works (at least in our situation). Let's look on complete command set for turtle in L-system application. You can find it in the following table.

All other symbols are just ignored during the interpretation (they can still be important for generating the sentence).

Implementation details.

As said before, L-system web application is implemented in JavaScript and using web browser as user interface. I will omit description of HTML code and JavaScript code for manipulating UI, as those are not interesting from perspective of this article. It is sufficient to know, that I'm using Bootstrap as it provides responsible design with only little effort and for the turtle graphics I'm using HTML canvas element.

Ok, let's see what is happening. After you press Iterate button, function doNextIteration(previous, rules) is called with parameters previous (containing string made in previous step) and rules (array with rewriting rules).

                function doNextIteration(previous, rules) {
                    let result = "";
                    let rul = {};
                    rules.forEach(function (v, i) {            // for every rule: put pattern as key and replace as value
                        rul[v.pattern] = v.replace;
                    });
                    previous.split("").forEach(function (v, i) {    // split sentence to array of letters
                        if (rul[v] == undefined) {        // if letter is not in rules -> copy unchanged
                            result = result + v;
                        } else {                        // else replace letter by replacement
                            result = result + rul[v];
                        }
                    });
                    return result;
                }
            

Simply said, first we transform rewriting rules from array to object (associative array), where keys are patterns to rewrite and values are replacements for those patterns. This is needed because of speed – every sane implementation of JavaScript is using hashtables for associative arrays, therefore it is fast (O(1) in ideal case for retrieve data by key). Then we split input string to the array of letters. If there is no rewrite rule for letter, copy it to the result unchanged. Copy replacement to the result otherwise. And that's it.

Now, when we have final string, we pass it to the turtle graphics module. All functionality is implemented in file turtle.js. First we have to create 'instance' of the turtle like let turtle = Turtle(context, maxx, maxy);, where context is HTML canvas 2d context, maxx, maxy are defining size of the canvas. We can call commands on that turtle object. Main function for perform actual drawing is draw(sentence) defined as:

                this.draw = function (sentence) {
                    let splitted = sentence.split("");    // split to the array of letters
                    context.beginPath();        // start with new drawing path
                    this.init();        
                    splitted.forEach(function (v, i) {
                        let func = fn[v];    // set corresponding function to 'func' variable
                        if (func != undefined) {
                            func();        // if func is defined, call it
                        }
                    });
                };
            

I think the code is quite clear, maybe two things are woth of explaining. Function init() sets state of the turtle to the initial one and clears the canvas. Second, not so obvious thing could be, where the fn object comes from and how it looks like. Let's see the following code:

                fn = {
                    "f": function () {
                        let newState = {
                            "x": state.x + (len * Math.cos(state.angle)),
                            "y": state.y + (len * Math.sin(state.angle)),
                            "originX": state.x,
                            "originY": state.y,
                            "angle" : state.angle
                        };
                        state = newState;
                    },
                    "F": function () {
                        let newState = {
                            "x": state.x + (len * Math.cos(state.angle)),
                            "y": state.y + (len * Math.sin(state.angle)),
                            "originX": state.x,
                            "originY": state.y,
                            "angle" : state.angle
                        };
                        context.beginPath();
                        context.strokeStyle = "#000000";
                        context.moveTo(newState.originX, newState.originY);
                        context.lineTo(newState.x, newState.y);
                        context.stroke();
                        state = newState;
                    },
                    …
            

Code above is only snippet, to see full code, please refer to the repository's code. I'm using one of the basic feature of JavaScript language – higher order functions. In short, it means, that functions in JavaScript are the same as other datatypes. You can assign function to the variable the same way as e.g. a number, or function can return as a result of another function. This is very powerful concept, known mainly from the functional programming languages, allowing us to implement interpretation of turtle symbols in simple, yet efficient way. It is also very easy to extend the command set only by adding new commands to the fn object – no need to change draw function.

Conclusion.

I hope, you now have some overview over such interesting topic, which L–system, with no doubt, is. You can also read first article describing application from the common user point of view. I will be happy as well, when you clone and play with sources from Github repository :). For further reference, search the net. And you can read book The Algorithmic Beauty of Plants by Aristid Lindenmayer and Przemyslaw Prusinkiewicz. It is on my TO-READ list too ;).