Fiddling with L-System (part 1)

The class of grammar-based fractals known as Lindenmayer system allows generating an interesting variety of geometrical and botanical visuals.

To the right is a representation of a “Fractal Plant”, which is generated from just two simple (if cryptic-looking) rules applied recursively.

In simple terms, L-System starts from a string (called an axiom), to which rules are applied recursively. Rules are a set of substitution strings for characters in the original string.

Classic Algae

For illustration,the classic example (named “Algae”), has two rules:

A -> AB  (each A becomes AB)
B -> A (each B becomes A)

And when you start from “A” as axiom, that gives the following recursive sequence:

n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA

Obtaining graphics

When you couple the above system with Turtle graphics, these strings can be used as the basis of a vector drawing. Combine a well chosen grammar with a bit of coloring, and you can obtain visually pleasing fractals.

Lindenmayer started from a botanical perspective, but the grammar system can be applied to a variety of mathematical entities, like the Peano-Gosper curve you can see to the left.

A variety of tilings and Kolams can also be achieved.

Coloring can be handled via turtle language commands directly, but also by coloring the lines from start to finish, such as in the Peano-Gosper curve here, where the colors are taken form a rainbow 1D texture.

 

Finally, L-System fractals also are an interesting way to stress-test a graphics UI line-rendering capabilities 😉

Start Fiddling Now!

I’ve made a small SmartMS app where you can fiddle with L-System right from any browser (desktop or mobile), along with a few classic presets to get you started:

L-System Fiddle

For the curious ones, timings are listed in the JavaScript console, f.i. hit ctrl+shift+J in Chrome to bring it up.

Now let’s get under the hood!

Applying L-System grammar

Below is the source code for applying a set of grammar rules to an axiom. They’re implemented as a simple set of  helper methods to an array of L-System rules.

Let’s suppose you want to generate the Heighway Dragon up to iteration 12, that can be done with just

var rules : TLSystemRules;
rules.Add('X', 'X+YF+');
rules.Add('X', '-FX-Y');
var dragon := rules.Apply('FX', 12);

As you see the helper approach allows to keep the code very simple. As to what can be done with the “dragon” string that’ll be topic for part 2 😉

I’ll leave you with the unit that allows the above code to work it magic.

unit LSystem;

interface

type

   TLSystemRule = record
      Predecessor : String;
      Successor : String;
   end;

   TLSystemRules = array of TLSystemRule;

   TLSystemRulesHelper = helper for TLSystemRules
      procedure AddRule(const predecessor, successor : String);

      function Apply(const axiom : String) : String; overload;
      function Apply(const axiom : String; iterations : Integer) : String; overload;
   end;

implementation

{ TLSystemRulesHelper }

procedure TLSystemRulesHelper.AddRule(const predecessor, successor : String);
var
   r : TLSystemRule;
begin
   r.Predecessor := predecessor;
   r.Successor := successor;
   Self.Add(r);
end;

function TLSystemRulesHelper.Apply(const axiom : String) : String;
var
   i : Integer;
   s : String;
   rule : TLSystemRule;
begin
   for i := Low(axiom) to High(axiom) do begin
      s := axiom[i];
      for rule in Self do begin
         if s = rule.Predecessor then begin
            s := rule.Successor;
            break;
         end;
      end;
      Result += s;
   end;
end;

function TLSystemRulesHelper.Apply(const axiom : String; iterations : Integer) : String;
begin
   Result := axiom;
   while iterations > 0 do begin
      Result := Apply(Result);
      Dec(iterations);
   end;
end;

 

7 thoughts on “Fiddling with L-System (part 1)

  1. Very interesting. Higher numbers of iterations tend to take an excessively long time to render, though. Might you be able to make them faster by doing something like this?

    * Scan the input string for patterns that get repeated multiple times. (http://stackoverflow.com/questions/11853668/)
    * Render the pattern once to a render target with a clear (0 alpha) background. Keep a value associated with this that tracks angle changes between beginning and end.
    * When the pattern occurs in the input string, render it to the canvas, rotated by the appropriate angle, and reset the “turtle’s” current drawing angle appropriately.

  2. BTW here’s a pretty new pattern I worked out:

    Rainbow: True
    Angle: 36
    Iterations: 5
    Axiom: X
    Rule 1: X -> [F+X]++[F+X]++[F+X]++[F+X]++[F+X]
    Rule 2: F -> FF

  3. Mason Wheeler :
    Higher numbers of iterations tend to take an excessively long time to render, though.

    I guess I need to add a length & stack overflow limiter too, currently those will just error in the JS, which can happen when fiddling and you forget an ‘]’ f.i.

    Might you be able to make them faster by doing something like this?

    Possibly, but this might introduce some aliasing issues, and restrict the coloring possibilities. Also the turtle language is fairly basic currently, but common extensions are to support pen-width, step size and other state controls in the turtle language, which means the same patterns can render very differently.

    BTW here’s a pretty new pattern I worked out:

    Nice one 🙂 Looks good for 7 iterations too!
    In the next version, you’ll have a button to “publish” a fractal to Imgur, picture & rules.

  4. Nice. I basically figured that out by saying “I wonder what the thing on the bottom of my office chair would look like if I made it grow into a Lindenmayer fractal.” 😛

    Good point about the pre-rendering issues. But there has to be *some* way to make this faster, I would think…

  5. @Mason Wheeler
    FWIW, The current “rainbow” mode is sacrificing quite a bit of per to anti-aliasing and actually renders the fractal twice (once for a shadow, once for the colored lines). Also tweaking joints and miter limits could also yeld speed ups (they’re at their default options, which are probably overkill). Rendering via WebGL directly would thus be faster (if maybe lower quality, but that may not be noticeable in practice).
    That said, Chrome seems to render the monochrome version 4 times faster than FMX on my machine, so it’s not all that bad, and iOS Safari does a great job at it too.

Comments are closed.