The beauty of LSystems
Vous pouvez aussi [lire cet article en version française][1].
What are Lsystems?
A Lindenmayer System (commonly referred to as Lsystem) is a recursive algorithmic model inspired by biology invented in 1968 by hungarian biologist Aristid Lindenmayer.
It aims to provide a way to model the growth of plants and bacterias.
The core concept behind Lsystems is rewriting, an effective way to generate complex objects by replacing parts from a simple initial object.
We can see it as cell which divide at each iteration to generate a more complex organism.
If you feel curious, wikipedia offers a more complete description of it.
Ok, but why should you care about it, and most importantly, what can you achieve using it?
Well… a lot of things, even generating some music, but we'll focus on visual applications, the illustrations on the banner of this post were generated using lsystems.
Imagine you want to break the monotony of a page, adding a crazy animated/generated/randomized pattern or you're working on a game and want to add some deco or you're simply interested in getting started with generative art, LSystems will surely be a good start.
The structure of an Lsystem
First let review the structure of an Lsystem (the [formal grammar][2]), it's comprised of:
 V a set of replaceable symbols (variables)
 S a set of non replaceable symbols (constants)
 ω a string of symbols from V defining the initial state of the system (axiom)
 P a set of production rules, defining how symbols from V should be replaced with constants (S) and/or variables (V)
An Lsystem is defined as a tuple and noted {V, S, ω, P}
and sometimes {V, ω, P}
(V and S being merged in V).
First take: the Koch curve
We'll start with a variant of the [Koch curve][3].
 variables V:
F
 constants S:
+
,
 axiom ω:
F
 rules P:
F → F+FFF+F
which will produces:
iteration 0 : F
iteration 1 : F+FFF+F
iteration 2 : F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
The generation is quite easy to implement in javascript:
const lSystem = ({ axiom: ω, rules: P, iterations: N = 1 }) =>
[...Array(N).keys()]
.reduce(acc => acc.split('').map(s => P[s] ? P[s] : s).join(''), ω)
const result = lSystem({
axiom: 'F',
rules: { F: 'F+FFF+F' },
iterations: 2,
})
So, after 2 iterations, you should have this result:
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
not very useful as it is, but we'll now consider each symbol as a drawing instruction using the following rules:
F
draw forward+
turn left 90°
turn right 90°
[][4]
Let's focus on iteration 1, F+FFF+F
, and decompose each step:
[][5]
You can use the following code to generate an array of segments from the lsystem result (for the sake of simplicity, I'll use the victor library for 2D vector):
const { segments } = result.split('').reduce(({ angle, segments }, symbol) => {
if (symbol === '+') return { segments, angle: angle  Math.PI * .5 }
if (symbol === '') return { segments, angle: angle + Math.PI * .5 }
return { angle, segments: [
...segments,
// we create the segment, rotate it by the current angle and add previous position
(new Victor(20, 0)).rotate(angle).add(segments[segments.length  1]),
]}
}, { angle: 0, segments: [new Victor(0, height)] })
Assuming you've got a CanvasRenderingContext2D, you just have to iterate through the array of segments to let the magic happen:
const ctx = canvas.getContext('2d')
ctx.beginPath()
segments.forEach(({ x, y }, i) => ctx[`${i === 0 ? 'move' : 'line'}To`](x, y))
ctx.stroke()
Not bad, in approximately 30 loc, you've got a graphic generated by an algorithm, try to reproduce this in your favorite graphic editor (illustrator, photoshop, krita…), you'll see it's not that simple, you can find the corresponding pen here.
It's quite easy to implement the Sierpinski triangle or the Dragon curve using this technique.
[][6]
Second take: a fractal plant
For this one, we'll add some constants and variables:
 variables V:
X
,F
X
is just a placeholder and won't be interpreted during rendering phase  constants S:
+
,
,[
,]
 axiom ω:
X
 rules P:
F → FF,
X → F[[X]+X]+F[+FX]X
which will produces:
iteration 0 : X
iteration 1 : F[[X]+X]+F[+FX]X
iteration 2 : FF[[F[[X]+X]+F[+FX]X]+F[[X]+X]+F[+FX]X]+FF[+FFF[[X]+X]+F[+FX]X]F[[X]+X]+F[+FX]X
We can keep the same generation code, but we have to change the configuration accordingly:
const result = lSystem({
axiom: 'X',
rules: {
F: 'FF',
X: 'F[[X]+X]+F[+FX]X',
},
iterations: 6,
})
You probably noticed the addition of [
and ]
constants:
[
means save current position and angle]
restore latest saved position and angle
Which gives us a LIFO stack allowing to build non continuous lines, ideal for the branching required to model a plant. Let's see how it works
[][7]
You have to modify the segments generation code to integrate those new instructions and because it's no more a continuous line, the segments are now composed of a start
and end
vectors:
const LENGTH = 6 // segment length
const ANGLE = 25 * Math.PI / 180 // angle used for rotations
const ORIGIN = new Victor(0, height * .95) // initial position
const instructions = {
'': state => ({ ...state, angle: state.angle  ANGLE }), // turn left
'+': state => ({ ...state, angle: state.angle + ANGLE }), // turn right
'[': state => ({ // save position & angle
...state,
stack: [ ...state.stack, _.pick(state, ['position', 'angle']) ],
}),
']': ({ stack, ...state }) => { // restore latest saved position & angle
const last = stack.pop()
return { ...state, stack, ...last }
},
'F': state => { // draw
const end = new Victor(LENGTH, 0)
end.rotate(state.angle).add(state.position)
return {
...state,
position: end,
segments: [
...state.segments,
{ start: state.position, end },
],
}
},
}
const { segments } = result.split('').reduce(
// if the current symbol matches an instruction, use it, otherwise just return current state
(state, symbol) => (instructions[symbol] ? instructions[symbol](state) : state),
// initial state
{
angle: 30 * Math.PI / 180, // used to orient the tree
position: ORIGIN,
stack: [],
segments: [],
}
)
An update is also needed on the canvas code:
const ctx = canvas.getContext('2d')
ctx.beginPath()
segments.forEach(({ start, end }) => {
ctx.moveTo(start.x, start.y)
ctx.lineTo(end.x, end.y)
})
ctx.stroke()
That's it, we now have the required code to build an almost natural organism resulting in the image at the top of this section, you can find the corresponding pen here.
There are infinite possible variations playing with rules/angle/length, if you google for LSystems
, you'll probably find some predefined ones.
Conclusion
Thank you Aristid! I don't think he anticipated the fame to come while conducting his research.
Apart from providing an easy way to get started with creative coding, it illustrates quite well that complex problems can (and should) be tackled with simple elegant solutions. Next time you're having headaches implementing a complex recursive algorithm, don't forget the rewrite trick.
If you liked LSystems or you're just interested in creative coding, you should have a look at the Paul Bourke website, it's a true goldmine!
I'm willing to write an article on how to add some randomness inside your LSystem (using stochastic grammars), so stay in touch!
References
 https://en.wikipedia.org/wiki/Lsystem
 http://algorithmicbotany.org/papers/abop/abopch1.pdf
 http://www.modularbrains.net/support/SteliosManousakisMusical_Lsystems.pdf

http://paulbourke.net/fractals/
[1]: https://www.ekino.com/labeautedeslsystemes/
[2]: https://en.wikipedia.org/wiki/Formal_grammar
[3]: https://en.wikipedia.org/wiki/Koch_snowflake
[4]: //images.ctfassets.net/95wnqgvmhlea/5tBXX7o9pKKYsmEwcOOomc/442b477cf3f98d9d769025e394a4828e/kochcurveblog_en.png?fm=png
[5]: //images.ctfassets.net/95wnqgvmhlea/iMhV55Chjyy4ao8kcYGmw/5a638c2e1d717dd463d529917257adfc/kochcurvedetailblog_en.png?fm=png
[6]: //images.ctfassets.net/95wnqgvmhlea/1oqgiE7lFOS0UY2OiCMMUO/7b1754e453c64e5f105de17c151f9842/fractalplantbanner_blog.png?fm=png
[7]: //images.ctfassets.net/95wnqgvmhlea/1aYh3i6bOCWMIAyEqE88C6/13c0639b481c23a4274101bd8365023f/fractalplantbranchingblogen.png?fm=png