Plante Fractale à une profondeur 8 (D0L système).

H.urna Fractal à une profondeur 8 (D0L système).

Dragon Koch à une profondeur 13 (D0L système).

Fractal Islands à une profondeur 3 (D0L système).

Peano Gosper Curve à une profondeur 5 (D0L système).

Squares Modified à une profondeur 5 (D0L système).

En 1968, le botaniste hongrois Aristid Lindenmayer développa un système de grammaire pour modéliser et simuler les schémas de la croissance des plantes. A l'origine, les systèmes L (diminutif de Lindenmayer) ont été conçus pour fournir une description formelle du développement des organismes multicellulaires simples tout en illustrant les relations de voisinage entre les cellules végétales. Plus tard, ce système a été étendu pour décrire des plantes et des structures de ramification plus complexes.

La modélisation réaliste de la croissance des plantes est très utile en biologie, en physique et également en infographie (les jeux vidéo utilisent et et améliorent toujours le rendu des plantes / forêts utilisant ce système).

Nous verrons comment cela fonctionne et en ferons usage pour générer toutes sortes de fractales. Ces systèmes sont incroyablement intéressants car ils fournissent un mécanisme pour suivre formellement les structures successives de nos fractales.

Composition

Voyons rapidement les quatre composantes des systèmes L:

• Alphabet : Contient les symboles pouvant être utilisés. Par exemple, nous pourrions dire que l’alphabet est {‘F’, ‘X’, ‘Y’}, signifiant que chacun de ces trois caractères peuvent être remplacés en utilisant une règle (voir ci-dessous).
  
  
• Constantes : Symboles ne pouvant pas etre remplacés, souvent !, [, ], +, - , elles sont inhérentes à la manière de dessiner la fractale (cf. Interprétation Visuelle).
  
  
• Axiome : L'axiome décrit l'état initial du système (à l'itération 0). Cela peut être par exemple "F", "FX", "F - F - F" ou tout autre chose.
  
  
• Règles : Une règle est simplement une transformation prenant une lettre de notre alphabet en paramètre. Les règles sont appliquées successivement à chaque symbole en commeçant par notre axiome et puis récursivement à chaque itération. Si nous prenons la règle “A -> AB”: chaque fois qu’un symbole “A” est trouvé, il sera remplacé par «AB».

Nous avons maintenant tout ce qu'il faut pour construire un exemple simple, étudions le système original de Lindenmayer utilisé pour la modélisation de la croissance d’une algue.

Exemple

• Alphabet : A, B
• Constantes : none
• Axiome : A
• Règles : (A → AB), (B → A)

Le système commence par «A» qui est l’axiome (itération 0) et a deux règles de productions, une pour la lettre A et l'autre pour B; jettons un coup d'œil aux cinq premières itérations:

Itération 0 Itération 1 Itération 2 Itération 3 Itération 4

A AB AB A AB A AB AB A AB AB A

Pour la première itération, nous appliquons simplement la première règle pour A.
Lors de la deuxième itération, nous devons appliquer les règles pour A et puis pour B, etc., etc.
Les produits de ce processus connaissent une croissance exponentielle: une lettre étant souvent remplacée par au moins deux lettres à chaque itération.

Code

string LSystem(axiom, rules, depth)
{
  string production;

  // For each iteration:
  for (auto level = 0; level < depth; ++level)
  {
    // Initialize production to empty string at each iteration
    production = '';

    // Iterate over each symbols/characters of the current axiom
    for (auto symbol = axiom.begin(); symbol < axiom.end(); ++symbol)
    {
      // Transform it if a rule applies
      if (rules.has(symbol))
        production += rules.get(symbol);
      // Add it without change otherwise
      else
        production += symbol;
    }

    // Update the axiom to its new content
    axiom = production
  }

  return production;
} 

La nature récursive des systèmes L conduit à une similitude à chaque échelle (profondeur) et donc à des formes fractales. Voyons maintenant comment ces chaînes de caractères deviennent des dessins!

Les systèmes L, comme celui décrit ci-dessus, produisent souvent des motifs textuels complexes.

Il est presque impossible pour un humain de se représenter ces motifs directement (composés de longues chaînes de symboles). Cependant, tout comme avec beaucoup de types de données, une représentation graphique peut les exposer clairement.

La manière graphique la plus courante de représenter un L-Systems est basée sur le Turtle Graphics (cf. Langage de programmation LOGO : une très ancienne méthode d'enseignement de l'informatique - 1967). Cette méthode tire son nom du commandant d'une tortue dans un plan cartésien.

Imaginez une tortue posée sur l'écran de votre ordinateur, imaginer que vous pouvez lui donner les directions à prendre : avancer, tourner à gauche, tourner à droite, tracer une ligne en avançant, etc.

Nous allons maintenant pouvoir associer chaque symbole à une direction, les directives suivantes sont couramment utilisées:

• F : Avancer tout droit en traçant un trait (dans la démo, dirigé vers l'Est initiallement).
• G : Avancer tout droit (sans aucun trait).
• + : Tourner à gauche (suivant un certain angle).
• - : Tourner à droite (suivant un certain angle).
• [ : Mémoriser la position actuelle dans une pile.
• ] : Popper la position de la pile.

Exemple

Interprétons la chaîne "F - F - F - F" avec un angle de rotation de 90◦ et une orientation initiale vers le nord. Alors que vous pouvez déjà imaginer le dessin final, voici la tortue qui nous écoute:

! Est venu le moment de produire notre propre fractale !

Nous allons créer un Triangle de Koch étape par étape:

• Alphabet : F
• Angle de Rotation : 60°
• Constantes : aucunes
• Axiome : F
• Règles : F → F+F--F+F

1. La première itération est l'axtiome 'F':
- Avancer tout droit en traçant un trait

2. Puis "F" (l'axiome) est transformé suivant la règle F → F+F--F+F:
- "F" : Avancer tout droit en traçant un trait
- "+" : Tourner à gauche de 60°
- "F" : Avancer tout droit en traçant un trait
- "--" : Tourner à droite de 120° (x2)
- "F" : Avancer tout droit en traçant un trait
- "+" : Tourner à gauche de 60°
- "F" : Avancer tout droit en traçant un trait

3. Encore une fois: la règle est appliquée sur chaque segment . Le même motif est répété récursivement.

4. Une nouvelle iteration effectuée.

5. Nous obtenons notre fractale "Koch Triangle" à une profondeur de 4 , mais nous pourrions continuer indéfiniment à affiner notre fractale.

• Testez vous-même ! (Démonstration en ligne)

Nous avons vu ici le plus simple des systèmes L. Cependant, des systèmes plus avancés existent et peuvent être construits tout aussi facilement. En voici la liste (les noms seront gardés en anglais pour l'usage) :

• Deterministic context-free System or D0L-System : S'il y a exactement une règle de production pour chaque symbole, alors le système L est dit déterministe. Si chaque règle de production ne fait référence qu’à un seul symbole sans tenir compte de ses voisins, on dit alors que le système est sans contexte (context-free).
  
  
• Stochastic context-free System or S0L-Système : S'il existe plusieurs règles de production pour un symbole et que ces règles sont choisies avec une certaine probabilité, il s’agit alors d’un système stochastique.
  
  
• Context Sensitive System, IL-System, or (k, l)-System : A une grammaire contextuelle qui ne regarde pas seulement le symbole qu'elle modifie, mais prend en compte les symboles voisins.
  
  
• Parametric L-System : A une grammaire paramétrique dont chaque symbole de l'alphabet est associé à une liste de paramètres. Un symbole associé à sa liste de paramètres est appelé un module; une chaîne est une série de modules.