La beauté des L-Systèmes

Actualité ekino -

Lorsque la biologie rencontre le code créatif

Article paru le :
The beauty of L-Systems
Article paru le :

You can also read this article in english.

De quoi s’agit-il ?

Un système de Lindenmayer (communément appelé L-système) est un modèle algorithmique récursif inspiré par la biologie et inventé en 1968 par le biologiste hongrois Aristid Lindenmayer.
Il vise à fournir un moyen de modéliser la croissance de plantes et bactéries.

Le concept fondamental des L-Systèmes est la réécriture, un procédé efficace permettant de générer des objets complexes en remplaçant simplement tout ou partie d’un objet initial.
Nous pouvons envisager cela comme une cellule qui se divise à chaque itération afin de générer un organisme plus abouti.
Si vous êtes curieux, wikipedia en fourni une description plus détaillée.

Très bien, mais en quoi cela peut-il vous intéresser et, plus important encore, que peut-on en faire ?
Il existe une multitude de cas d’usages, certains se sont même amusés à générer de la musique à partir de ceux-là, mais nous allons nous concentrer sur des applications visuelles. Imaginez que vous souhaitez casser la monotonie d’une page web en y ajoutant un motif aléatoire/animé/auto-généré ou bien que vous travailliez sur un jeu et souhaitez y ajouter un décor sans avoir à en pré-générer chaque pixel, ou encore que vous êtes simplement intéressés par le code créatif, les L-Systèmes constituent un excellent point de départ.

La structure d’un L-Système

Premièrement, analysons la structure d’un L-Système (sa grammaire formelle), elle est définie par :

  • V un ensemble de symboles remplaçables (variables)
  • S un ensemble de symboles non remplaçables (constantes)
  • ω une chaîne de caractères constituées de symboles provenant de V, l’état initial du système (axiome)
  • P un ensemble de règles de production, définissant comment les symboles provenant de V doivent être interprétés, remplacés par des constantes (S) et/ou des variables (V)

 

Un L-Système est un tuple, noté {V, S, ω, P} et parfois {V, ω, P} (V et S étant regroupés au sein de V).

Première prise : le flocon de Koch

Nous allons débuter avec une variante du flocon de Koch.

  • variables V: F
  • constantes S: +, -
  • axiome ω: F
  • règles P: F → F+F-F-F+F

 

Qui va produire :

La génération est relativement aisée à implémenter en javascript :

Donc, après 2 itérations, nous obtenons la chaîne de caractères suivante:
  F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

pas très utile en l’état je vous l’accorde, mais considérons maintenant chaque symbole comme une instruction de tracé en utilisant les règles suivantes :

  • F dessiner tout droit
  • + tourner à gauche de 90°
  • - tourner à droite de 90°

 

Itérations du flocon de Koch

 

Attardons nous quelque peu sur l’itération 1, F+F-F-F+F, et décomposons en chaque étape :

Détail du flocon de Koch

Vous pouvez utiliser le code suivant afin de générer un tableau de segments à partir du résultat du L-Système (pour des raisons de simplicité, nous utiliserons la librairie victor pour nos vecteurs 2D) :

En assumant que vous disposez d’un CanvasRenderingContext2D, vous allez simplement devoir itérer sur ce tableau pour que la magie opère :

Pas mal ! En approximativement 30 loc vous avez une illustration générée à partir d’un algorithme, tentez de reproduire celle-ci dans votre éditeur graphique préféré (illustrator, photoshop, krita…), vous constaterez que ce n’est pas si trivial que ça.

Vous pouvez retrouver un exemple de ce code sur codepen.

Il est assez simple d’implémenter le triangle de Sierpinski ou encore la courbe du Dragon en ayant recours à cette technique.

 

L-System fractal plant

Deuxième prise : une plante fractale

Pour celle-ci nous allons rajouter quelques constantes et variables :

  • variables V: X, F X est juste un espace réservé et ne sera pas interprété durant la phase de rendu
  • constantes S: +, -, [, ]
  • axiome ω: X
  • règles P: F → FF, X → F-[[X]+X]+F[+FX]-X

 

Qui va produire :

Nous pouvons réutiliser le même code que précédemment pour la génération, mais la configuration doit, elle, être modifiée en conséquence :

Vous aurez probablement noté l’ajout de 2 nouvelles constantes, [ et ] :

  • [ sauvegarder la position et l’angle courant
  • ] restaurer la position et l’angle courant à partir de la dernière sauvegarde

 

Ceci nous donne une pile LIFO permettant de dessiner des lignes non continues, idéale pour représenter les embranchements inhérents à la modélisation d’une plante. Regardons maintenant quel en est le fonctionnement.

Embranchement d'une plante fractale

Vous allez devoir modifier le code concernant la génération de segments afin d’y intégrer les nouvelles instructions.
Et comme il ne s’agit plus d’une ligne continue, les segments sont maintenant des objets composés d’un vecteur start et end :

Nous devons également modifier quelque peu le code concernant le tracé de notre plante :

Ça y est, nous avons dorénavant tout le code nécessaire à la génération d’un organisme quasiment naturel qui va résulter  dans l’illustration utilisée en haut de cette section.

Vous pouvez retrouver un exemple de ce code sur codepen.

Il y a un nombre infini de variations possibles en jouant avec les règles, l’angle ou encore la longueur des segments, si vous lancez une recherche google pour le terme L-Systems, vous trouverez à coup sûr bon nombre de configurations pré-établies.

Conclusion

Merci Aristid ! Je ne pense pas qu’il ait anticipé la popularité à venir lorsqu’il menait ses recherches.

En dehors de fournir un bon moyen pour démarrer avec le code créatif, cet algorithme démontre assez bien que des problèmes complexes peuvent (et devraient) être adressés avec des solutions simples et élégantes. La prochaine fois que vous vous arrachez les cheveux sur un algorithme récursif complexe, ne négligez pas la feinte à base de réécriture !

Si les L-Systèmes vous ont séduit ou que vous êtes intéressés par le code créatif, je ne saurais que trop vous recommander le site internet de Paul Bourke, il ne faut pas se fier au style rudimentaire de celui-ci, c’est une véritable mine d’or !

J’envisage d’écrire une seconde partie à cet article expliquant comment ajouter de l’aléatoire dans un L-Système (utilisant une grammaire stochastique), alors restez connectés !

Références