Modeling L-systems in ECMAScript 5.1

L-systems were introduced by Aristid Lindenmayer in a 1968 paper Mathematical models for cellular interactions in development. II. Simple and branching filaments with two-sided inputs. They are particularly useful for the modeling of evolution of self-similar (fractal) systems, such as growth of plants, or successive approximations of space-filling curves. [Algorithmic Beauty, L-system]

A given L-system is defined by an alphabet, a set of production rules over that alphabet, and an axiom – a non-empty sequence of elements from the alphabet that gives the initial state of the system. On every iteration of the system, all the matching rules are applied to the current state in parallel to produce the next state.

One of the simplest (but non-trivial) systems like that is the one described in the Algae section below.

While simpler systems can be explored with pencil and paper, more complex ones require a computer program to perform successive iterations. Examples of such programs are described below.

This system is defined by two production rules: A → AB, B → A. The axiom can be either A or B. The alphabet is consequently {A, B}.

To model this system, we create a StoLsystem object, passing to its constructor two arguments: the first is our production rules, given as an ECMAscript object, { A: [ "AB" ], B: [ "A" ] }, and the second is the initial state, which we give as "A" (though it can be replaced with "B" with only a slight difference to the result.)

The resulting object is saved in the lsy variable. By calling lsy.once five times in a for loop, we produce five consecutive iterations of this system: AB, ABA, ABAAB, …

Use the eval button to run the code and see the resulting states of the system.

This is the L-system that gives us the classic Koch curve.

In this example, we want not only to produce a sequence of states, but also to interpret the latest state geometrically. Namely, we’ll use turtle graphics (as provided by a TBGIE.Lsy object and the svg_visualize function) and we’re going to interpret our state as a sequence of commands to an imaginary turtle as follows:

F

move forward by one unit of length, while drawing a trailing line;

+

turn left by ⅓ π;

-

turn right by ⅓ π.

The conversion from the symbols above to actual turtle commands is part of the TBGIE.Lsy code. Note that we use −⅓ π as the angle to turn by, which is because in computer graphics, the y axis points down, not up, like in conventional geometry.

Alternatively, with F--F--F used as the axiom in place of F (try it!), the code will produce a Koch snowflake instead. As that results in a closed path, gi.stop (1); should be used in place of gi.stop () (though as it is, that shouldn’t result in any visible changes to the resulting image.)

This L-system produces a Sierpiński arrowhead curve – a curve that approximates the Sierpiński triangle.

This is again a fairly simple system, defined by production rules 1 → 11, 0 → 1[0]0. The axiom is 0, and the constants (the elements of the alphabet that are not changed by the production rules; also known as terminals) are [ and ].

The complexity of the example code below comes from the fact that we’ll use a slightly different interpretation of the symbols than the TBGIE.Lsy default; namely:

0 and 1

move forward by a unit of length, while drawing a trailing line;

[

create a new turtle for use, then turn it left (or right: our figure is symmetric) by ¼ π;

]

stop using this turtle and switch back to a previous one, then turn right (left) by ¼ π.

Now we’re going to specify two possible production rules for 0: 0 → 0 (i. e. no change) and 0 → 1[0]0. Our implementation is coded in such a way that when presented with several choices, it will on every application select one of them at random, with equal probabilities. In effect, our binary tree will now grow a fork (in each of the eligible positions) only half the time, which surely will affect how it looks.

Note that every run of the code will likely produce a different result. The end effect is as if branching happens at different rates for different parts of the tree.

In order to make the probabilities differ, we can provide a list of right hand sides that has duplicate elements in it, such as [ "0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0" ], which will result in the 0 being constant with only 10% probability. Alternatively, the right hand side of the production can be given as a function. For instance, you can use if (1) in place of if (0) in the code below to hot-patch the rules so that the 0 → 0 rule will be applied in 10% (or any other probability – as given in the function’s code) of applications.

To simplify the code, we’re going to cheat a bit and use StoLsystem.Examples.BinTree.prototype.g_i as our geometry engine, which is provided by the code library we use here.

The following code should execute the test suite for the code libraries used in this document and present the result as a TAP document. [TAP-14]

Algorithmic Beauty

Algorithmic Beauty of Plants / Przemyslaw Prusinkiewicz, Aristid Lindenmayer et al. — (archived) URI: https://web.archive.org/web/20240424190550/http://algorithmicbotany.org/papers/#abop

Duktape

Duktape. — URI: http://duktape.org/

ECMA-262

ECMAScript Language Specification: ECMA-262 Edition 5.1. — URI: http://262.ecma-international.org/5.1/

Edbrowse.deb

edbrowse package details // Debian Bookworm. — URI: http://packages.debian.org/bookworm/edbrowse

L-system

L-system // Wikipedia. — URI: http://en.wikipedia.org/wiki/L-system

TAP-14

TAP 14 specification // Test anything protocol. — (archived) URI: http://web.archive.org/web/20240106151003/https://testanything.org/tap-version-14-specification.html

Wget, GNU

Recursive retrieval options: -p // GNU Wget 1.24.5 Manual. — URI: http://gnu.org/s/wget/manual/html_node/Recursive-Retrieval-Options.html#index-page-requisites