Out of intense complexities intense simplicities emerge…

— A TypeScript implementation of L-systems

2021-01-01

In the first chapter of The Algorithmic Beauty of Plants, the authors describe a set of related systems named L-systems after one of the authors, Lindenmayer. Using simple production rules, a L-system can produce advanced patterns, not so different from the visual patterns of plants. This is my implementation.

A tree generated using a L-system. Starting with a `F`, and `F[+F]F[-F][F]` as substitution rule, recursively called 5 generations.

A tree generated using a L-system. Starting with a F, and F[+F]F[-F][F] as substitution rule, recursively called 5 generations.

These are some signs that describe a potential condition.

F-F-F-F

When transiting from a state to another, then, according to a set of transformation rules, every F would be replaced with the following characters. 

FF-F--F-F

All - characters are skipped.

So, this is the current condition,

F-F-F-F

The first visit to this initial axiom, would generate the first generation. 

FF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-F

A second would transform to:

FF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-
F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F-FFF-F--F
-FFF-F--F-FFF-F--F-FFF-F--F-F

For each generation, the pattern would be more advanced.

There are also a set of rules for how to react to a condition, how each sign should be interpreted as a command and executed.

Assume a two-dimensional plane and a turtle walking about. In addition to a position, the turtle has a direction. Here is a set of rules that indicates how the turtle reacts to characters, a set of instructions for how the turtle navigates the plane. The turtle parses each character as an instruction: 

F → forward and fill the position with a color
f → forward, but do not fill the position
+ → turn 90 degrees to the left
- → turn 90 degrees to the right

What happens when the turtle follows instructions F-F-F-F? If the turtle initially is directed to the north and walks forward it goes to the north, turns to the right, continues forward, heading east, turns, etc. until the turtle finally arrives at the same position from which it originated. The turtle’s “trace” forms a square.

The more times one state advances to another, the more advanced the pattern becomes. From the kind of flatness we experience when seeing simple geometric forms, the turtle moves — parsing and executing instructions — forming shapes like this Gosper Curve,

Two sets of rules: One set of rules takes a number of characters, visits each character, and transforms it, given that the character is covered in the set of rules. A larger set of characters are returned from the transformation. The second set of rules is a list of instructions, rules for how to use the characters, how to execute them. From potentiality we achieve actuality and side-effects.

All patterns are constructed by repetition, and deepening. A larger pattern is similar to, and a repetition of, a smaller pattern. All such patterns are regular in an irregular way, dwelling in the borders between something finite and infinite.

My implementation uses TypeScript, and have utilized a functional style aiming for readability, not performance.

I made a function, makeLSystem, which takes a number of generations to be produced, an initial axiom, and a set of transformation rules.

If makeLSystem does not receive more than 0 generations, it returns the axiom that was taken. No validation of the characters’ authenticity is done because this function does not know what characters have meaning in the set of instructions.

Until the generation of transformations wanted has been completed, makeLSystem is called recursively, for each generation producing a new, transformed axiom. 

type Axiom = string;

type LRules = Map<Axiom, Axiom>;

type Instruction = string;

const makeLSystem = (
    generations = 0,
    axiom:Axiom = '',
    lrules:LRules
):Instruction => {
    if(generations === 0) return axiom;
    const mLS = (generation = 0, newAxiom:Axiom = ''):Axiom =>
        generation === generations
            ? newAxiom
            : generation === 0
                ? mLS(generation + 1, makeGeneration(axiom, lrules))
                : mLS(generation + 1, makeGeneration(newAxiom, lrules));
    return mLS();
};

makeGeneration takes a generations current axiom, the set of rules and return a new axiom after folding it using nextGeneration. If the character examined in nextGeneration is included in the set of rules, the character is replaced according to the taken rules, replacing the character with the character(s) associated with it. This continues until there are no characters left to be examined. A set of instructions are returned. 

const nextGeneration = (rules:LRules) => (
    acc:Axiom,
    str:Axiom
) => acc.concat(rules.get(str) ?? str);

const makeGeneration = (prevGenerations:Axiom, rules:LRules) =>
    prevGenerations
        .split('')
        .reduce(nextGeneration(rules), '');

How does this relate to the set of rules used for instructions? Let’s look at the rules of for the Pentadendrite. For each F, F-F+F+FF-F-F+F. 

const pentadendrite = new Map()
    .set('F', 'F-F-F++F+F-F');

The Pentadendrite starts with F, uses F-F-F++F+F-F as substitution rule, recursively called 4 generations.

The Pentadendrite starts with `F`, uses `F-F-F++F+F-F` as substitution rule, recursively called 4 generations.

If examined, each character will be parsed and execute some command.

No state, in the sense of memory for business data, is necessary. However, we need state of a sort for side-effects. Each rule takes a ‘visualization’, a state holding data for side-effects, and returns a modified. State in this sense is merely the output, generationally built. An area for side-effects. 

interface Visualization {
  ctx: CanvasRenderingContext2D;
  lineLn: number;
  degrees: number;
}

type AxiomHandler = (v:Visualization) => Visualization;

type LRulesInstructions = Map<Instruction, AxiomHandler>;

const parseLSystem:LRulesInstructions = new Map()
    .set('+', (v:Visualization) => ({
        ...v,
        ctx: rotate(v.ctx, v.degrees)
    }))
    .set('-', (v:Visualization) => ({
        ...v,
        ctx: rotate(v.ctx, -v.degrees)
    }))
    .set('F', (v:Visualization) => ({
        ...v,
        ctx: line(v.ctx, v.lineLn)
    }))
    .set('H', (v:Visualization) => ({
        ...v,
        ctx: line(v.ctx, v.lineLn)
    }))
    .set('f', (v:Visualization) => ({
        ...v,
        ctx: move(v.ctx, v.lineLn)
    }))

I’ve used the HTML5 Canvas API for graphics. Most methods are quite intuitive here. A note on rotate: rotate takes a radian, and I use an implementation suggested at MDN for translating between degrees and radians.

Rather than changing the direction (by rotation) of an imagined turtle, we rotate the “map” an imagined turtle, holding a position, operates on. Therefore the turtle always moves “up” (-y), with a tracing line or not. Every action ends with a re-positioning of the “map”. 

const rotate = (
  ctx:CanvasRenderingContext2D,
  degrees:number
):CanvasRenderingContext2D => {
    ctx.rotate(degrees * Math.PI / 180);
    return ctx;
};

const line = (
  ctx:CanvasRenderingContext2D,
  lineLn:number
):CanvasRenderingContext2D => {
    ctx.beginPath();
    ctx.moveTo(0, 0);
    ctx.lineTo(0, -lineLn);
    ctx.stroke();
    ctx.translate(0, -lineLn);
    return ctx;
};

const move = (
  ctx:CanvasRenderingContext2D,
  lineLn:number
):CanvasRenderingContext2D => {
    ctx.moveTo(0, -lineLn);
    ctx.translate(0, -lineLn);
    return ctx;
};

I parse and execute the instructions in createLSystemVisualization. createLSystemVisualization takes an axiom (the initial value), a canvas context and a set of rules, stating instructions. First, I split the axiom and recursively examine each character of the axiom, building a “state” for side-effects. Each character is “transformed” from something potential to an actuality; first parsed as an instruction, and if included, executed, changing the state for side-effects. createLSystemVisualization returns a canvas context. 

import { Canvas, createCanvas } from 'canvas';
import { writeFileSync } from 'fs';

const id = <T>(v:T):T => v;
const transformCharacter = (
    instructions:LRulesInstructions
) => (axiom: Axiom) => (v:Visualization) => (instructions.get(axiom) ?? id)(v);

const transformReducer = (
    instructions:LRulesInstructions
) => (acc:Visualization, v:Axiom) => transformCharacter(instructions)(v)(acc);

const createLSystemVisualization = (
    axiom:Axiom,
    v:Visualization,
    instructions:LRulesInstructions
):CanvasRenderingContext2D => axiom
    .split('')
    .reduce(transformReducer(instructions), v)
    .ctx;

Before executing a set of “instructions”, an axiom is taken by calling makeLSystem (quoted above) in drawLSystem. drawLSystem takes a filename, some rules, what number generations wanted, an initial axiom (the axiom passed to makeLSystem), the length of a “line”, how many degrees to rotate, a starting position as well as the width and height of the outputted png image. 

function drawLSystem(
    filename:string,
    rules:LRules,
    generations:number,
    initialAxiom:Axiom,
    lineLn:number,
    degrees:number,
    x = 1024/2,
    y = 768/2,
    width = 1024,
    height = 768
):void {
    const canvas:Canvas = createCanvas(width, height);
    const ctx = <CanvasRenderingContext2D>canvas.getContext('2d');
    if(!ctx) return;
    ctx.fillStyle = '#fffff8';
    ctx.fillRect(0, 0, width, height);
    ctx.strokeStyle ='#6A0917';
    ctx.translate(x, y);
    const axioms = makeLSystem(generations, initialAxiom, rules);
    const visualization:Visualization = {
        ctx,
        lineLn,
        degrees
    };
    const img:CanvasRenderingContext2D = createLSystemVisualization(
        axioms,
        visualization,
        parseLSystem
    );
    img.stroke();
    const buffer = canvas.toBuffer('image/png');
    writeFileSync(`./output/${filename}.png`, buffer);
}

Here I generate a pattern, similar to a snow-flake. All patterns shown in the gallery below and at GitHub. 

const outputParams = {
  name: 'snow-flake-modified',
  rules: snowflakeModified,
  generations: 4,
  initialAxiom: '-F',
  lineLn: 10,
  degrees: 90,
  x: 900,
  y: 500 
};
drawLSystem(...outputParams);

So far, all patterns are “simple”. More advanced pattern such as trees require a state for “depth”, a context for position. [ is used for pushing a context to the “stack”, ] for popping a context.

Just as before, I take a state for side-effects and return a new,

    .set('[', (visualization:Visualization) => ({
        ...visualization,
        ctx: pushContext(visualization.ctx)
    }))
    .set(']', (visualization:Visualization) => ({
        ...visualization,
        ctx: popContext(visualization.ctx)
    }));

I use the save method of the canvas API for pushing and restore for popping a context from the “stack”. 

const pushContext = (
  ctx:CanvasRenderingContext2D
):CanvasRenderingContext2D => {
    ctx.save();
    return ctx;
};

const popContext = (
  ctx:CanvasRenderingContext2D
):CanvasRenderingContext2D => {
    ctx.restore();
    return ctx;
};

This tree is generated using two rules,

const tree4 = new Map()
    .set('F', 'FF')
    .set('X', 'F[+X][-X]FX');

Axiom: X; production rules: F → FF, X → F[+X][-X]FX; generations: 7

Axiom: `X`; production rules: `F → FF`, `X → F[+X][-X]FX`; generations: 7

About | Archive