L_systemes

LOGO et les L-systèmes

Le mot "L-système" est une abréviation de "Lindenmayer system". Aristid Lindenmayer (1925-1989), biologiste hongrois, a été le premier à remarquer que certains processus de croissance naturels pouvaient être modélisés par un simple ensemble de règles. C'est ainsi que lors de la croissance d'un être vivant, les cellules de l'organisme, en se reproduisant, se divisent tour à tour en deux, plus petites. Parfois, la cellule d'origine ne disparaît pas tout de suite lors de la génération suivante. De cette observation, Lindenmayer en a tiré plusieurs axiomes possibles et indépendants:

On appellera C, la cellule "mère", et c une cellule "fille".
La flèche -> veut dire "... est remplacée par ..."
axiome 1: C-> c c C (les deux cellules "filles" sont à gauche de la cellule "mère")
axiome 2: C-> C c c (les deux cellules "filles" sont à droite de la cellule "mère")
axiome 3: C-> c C c (les deux cellules "filles" encadrent la cellule "mère")

Lorsque la cellule "mère" disparaît lors de la génération suivante, il n'y a qu'un seul axiome possible:

axiome 4: C -> c c

En prenant l'axiome 3 pour passer d'une génération à la suivante, on aura:

Génération initiale: C
Génération 1: c C c
Génération 2: c C c c C c c C c (les deux cellules "fille" se sont divisées chacune de leur côté)
Génération 3: c C c C c C c c C c C c C c c C c C c C c
Génération 4:
c C c C c C c C c C c C c C c c C c C c C c C c C c C c C c c C c C c C c C c C c C c C c
.......................

Comme on le constate, cet axiome engendre un organisme qui peut devenir gigantesque. Dans la nature, la cellule "mère" disparaît la plupart du temps lors des premières générations qui suivent sa réplication, ce qui ramène l'organisme en construction à une taille raisonnable (axiome 4).

Les observations de Lindenmayer en sont restées là jusqu'en 1968, date qui a vu l'essor des mini-ordinateurs, ce qui a permis leur adaptation au domaine de la géométrie et du graphisme par le truchement de l'informatique. Il fallait simplement remplacer la cellule "mère" et les deux cellules "fille" (3 configurations possibles) pour définir une longueur de déplacement du crayon et un angle pour passer d'une génération à la suivante. Ce passage d'une génération à l'autre peut se faire soit en tournant à gauche (-), soit en tournant à droite (+). La place des signes est purement arbitraire et ils peuvent être interchangés.

Si on définit la longueur de déplacement par L (1 unité) et l'angle alpha par un nombre (exprimé en degré ou en radians, selon le cas), on aura par exemple:

un carré par la gauche: un carré par la droite:

L=1 L=1
alpha=90° alpha=90°
axiome: L -> L - L axiome: L -> L + L
Pour le carré par la gauche, on aura successivement:
Génération initiale: L
Génération 1: L - L
Génération 2: L - L - L - L
Génération 3: L - L - L - L - L - L - L - L
Un L-système est donc une grammaire formelle : un ensemble de règles et de symboles.
Il est composé de quatre éléments :
1. Les variables : des symboles pouvant être remplacés. 2. Les constantes : des symboles ne pouvant pas être remplacés (angle, module de déplacement). 3. Un axiome de reproduction, appliquées aux variables de manière récursive. 4. Une configuration initiale, ou encore objet de départ. En LOGO, la tortue se trouve
en (0,0).

Les conditions sont à présent réunies pour traduire ces axiomes en langage LOGO.

Si AVANCE, TOURNEDROITE et TOURNEGAUCHE sont des primitives évidentes à appliquer, il faut, avant de faire déplacer la tortue, construire la liste des mouvements qui résulte de la transformation de l'axiome de reproduction pendant le passage inter-générationnel. A la troisième génération, le carré par la gauche aura pour liste des mouvements :

[ L - L - L - L - L - L - L - L ]

Il faut donc prévoir l'utilisation des primitives PREMIER, SAUFPREMIER,
PHRASE, CARDINAL

On définira tout d'abord:

1) Les procédures de déplacement:

pour L
av :longueur
fin
pour moins
tg :alpha
fin
pour plus
td :alpha
fin
2) Une procédure pour faire passer la liste des mouvements d'une génération à la
suivante:
POUR transforme_liste :liste1 :liste2 :signe :niveau
/*
liste1: configuration actuelle.
liste2: axiome de reproduction.
signe: représente ici L.
niveau: nombre de configurations souhaitées.
*/
TESTE :niveau = 0
SIVRAI RENDS :liste1
SIFAUX [
DONNE "l1 :liste1 DONNE "résu []
DONNE "c1 CARD :liste1 DONNE "c2 CARD :liste2
REPETE :c1 [
DONNE "s PREM :l1
TESTE :s = :signe
SIVRAI [
DONNE "l2 :liste2
DONNE "résu PH :résu [/]
/* On divise par 2 les déplacements dans la prochaine configuration. */
REPETE :c2 [ DONNE "résu PH :résu PREM :l2 DONNE "l2 SP :l2 ]
DONNE "résu PH :résu [x]: /* On multiplie par 2 les déplacements pour revenir à la configuration actuelle. */
]
SIFAUX DONNE "résu PH :résu PREM :l1
DONNE "l1 SP :l1
]
RENDS transforme_liste :résu :liste2 :signe :niveau -1
]
FIN
3) Les variables:
DONNE "alpha 90 /* PI/2 radians. */
DONNE "longueur 7 /*module de déplacement. */

4) La configuration initiale et l'axiome de reproduction:


DONNE "config [ L - L ] donne "axiome [ L - L ]

5) On fixe la transformation de la liste des mouvements après la deuxième génération:


DONNE "config transforme_liste :config :axiome "L 2 /* 2 générations. */

6) On peut à présent faire évoluer la tortue:
répète card :config [
donne "consigne PREM :config
donne "config SP :config
si :consigne = "L L
si :consigne = "- moins
si :consigne = "+ plus
si :consigne = "/ DONNE "longueur ENTIER (:longueur / 2 )
si :consigne = "x DONNE "longueur :longueur * 2
]
Certains calculs itératifs peuvent être très longs, car la configuration des mouvements s'allonge à chaque génération. L'exemple illustré ici n'est esthétiquement pas très probant (la tortue trace un carré autant de fois que de générations (=2)), mais la plupart des ordinateurs construiront cette liste assez rapidement. C'est son principal avantage.

pour L
av :longueur
fin
pour moins
tg :alpha
fin
pour plus
td :alpha
fin
POUR transforme_liste :liste1 :liste2 :signe :niveau
TESTE :niveau = 0
SIVRAI RENDS :liste1
SIFAUX [
DONNE "l1 :liste1 DONNE "résu []
DONNE "c1 CARD :liste1 DONNE "c2 CARD :liste2
REPETE :c1 [
DONNE "s PREM :l1
TESTE :s = :signe
SIVRAI [
DONNE "l2 :liste2
DONNE "résu PH :résu [/]
REPETE :c2 [
DONNE "résu PH :résu PREM :l2 DONNE "l2 SP :l2
]
DONNE "résu PH :résu [x]
]
SIFAUX DONNE "résu PH :résu PREM :l1
DONNE "l1 SP :l1
]
RENDS transforme_liste :résu :liste2 :signe :niveau -1
]
FIN
EFF ACCELERE DEROULE
DONNE "alpha 90 /* PI/2 */
DONNE "longueur 7
DONNE "config [ L - L ] donne "axiome [ L - L ]
DONNE "config transforme_liste :config :axiome "L 2 /* 2 générations */

répète card :config [
donne "consigne PREM :config
donne "config SP :config
si :consigne = "L L
si :consigne = "- moins
si :consigne = "+ plus
si :consigne = "/ DONNE "longueur ENTIER (:longueur / 2 )
si :consigne = "x DONNE "longueur :longueur * 2
]
Pour télécharger cet exemple, cliquer ici .

Remarque: en remplaçant la ligne de l'axiome:
DONNE "config [ L - L ] donne "axiome [ L - L ]
par:
DONNE "config [ L - L ] donne "axiome [ L - L + ]
on obtient une courbe C nettement moins monotone à observer.

Haut de page >>

Retourner à la page d'accueil >>

Rückkehr >>