Informatique au lycée > Terminale > Langages et programmation > Récursivité > Des plantes réalistes

Des plantes réalistes

Des plantes “réalistes” avec le module Turtle de Python

Selon Wikipédia, un “L-système ou système de Lindenmayer est un système de réécriture ou grammaire formelle, inventé en 1968 par le biologiste hongrois Aristid Lindenmayer. Un L-système modélise le processus de développement et de prolifération de plantes ou de bactéries.”

Les L-systèmes permettent d’obtenir des dessins de plantes relativement réalistes (c’est subjectif …).

Je vous propose de comprendre et programmer un type de L-sytème : la réécriture d’arête.

Vous pouvez visionner la vidéo suivante :

Résumé de l’exemple :

On commence par un segment (voyons-le comme une branche ou un tronc)
Il va être remplacé par un ensemble de segments, un motif : on peut le voir comme le motif de base
Chaque branche va ensuite être remplacée, de manière recursive, par ce motif en version réduite.

Voici les étapes successives que l’on obtient (de 0 à 4):

La grammaire que nous allons utiliser :

Lindenmayer a inventé une façon de décrire le motif de réécriture, en utilisant une longueur et un angle :

la lettre F va symboliser le dessin d’une arête, un segment (une branche si l’on parle de végétaux)
le signe - indique que l’on va tourner à droite
le signe + indique que l’on va tourner à gauche
le fait de placer des crochets autour d’une séquence indique que l’on revient en arrière, après cette séquence, avant de continuer,

Ainsi, notre motif de base donné en exemple est symbolisé par la règle suivante, appliquée avec un angle de 20 degrés et une division par 3 des longueurs à chaque itération :

F -> F[+F]F[-F]F

L’utilisation du module Turtle de Python est particulièrement adapté à cette situation, puisque :

F va correspondre à l’instruction forward(taille)
- à l’instruction rt(angle)
+ à l’instruction lt(angle)

Je vous propose de commencer par programmer directement l’exemple proposé, avant de créer un interpréteur de règle simple, qui permettra à l’utilisateur d’écrire une règle et de laisser le programme dessiner le résultat au niveau voulu.

Application directe de la règle F -> F[+F]F[-F]F

import turtle

def arbre_branche(t, taille, angle):
    """ F -> F[+F]F[-F]F"""
    # F : on construit une branche tout droit
    t.fd(taille)
    # [+F : on construit une branche sur la gauche
    t.lt(angle)
    t.fd(taille)
    # ] : on revient en arrière
    t.bk(taille)
    t.rt(angle)
    # F on construit une branche tout droit
    t.fd(taille)
    # [-F : on construit une branche sur la droite
    t.rt(angle)
    t.fd(taille)
    # ] : On revient en arrière
    t.bk(taille)
    t.lt(angle)
    # F : on construit une branche tout droit
    t.fd(taille)

def main():
    # initialisation de Turtle
    t = turtle.Turtle()
    myWin = turtle.Screen()
    myWin.setup(800, 600)
    # On se place pour démarrer
    t.lt(90)
    t.up()
    t.bk(250)
    t.down()
    t.color("green")

    arbre_branche(t, 100, 20)

    # La fenêtre se fermera lors d'un clic de souris
    myWin.exitonclick()

# appel du programme principal
main()
turtle.mainloop() # pour empecher la fenêtre de se fermer

Dans l’exemple ci-dessus, nous avons programmé directement le dessin d’une branche.

Comment obtenir les différentes itérations de notre plante ?

Le procédé étant récursif, nous allons rendre la fonction arbre_branche récursive.

Comme tout procédé récursif, nous devons avoir :

une condition d’arrêt
un appel récursif.

Lorsque l’on dessine une branche, on doit :

soit dessiner un segment, si l’on est au dernier niveau (niveau 0) : c’est la condition d’arrêt.
soit dessiner un motif de niveau supérieur : on appelle la fonction arbre_branche au niveau inférieur.

Cela donne :

import turtle

def arbre_branche(t, niveau, taille, angle):
    """ F -> F[+F]F[-F]F"""
    if niveau == 0:
        t.fd(taille)
    else:
        # F : on construit une branche tout droit
        arbre_branche(t, niveau - 1, taille/3, angle)
        # [+F : on construit une branche sur la gauche
        t.lt(angle)
        arbre_branche(t, niveau - 1, taille/3, angle)
        # ] : on revient en arrière
        t.bk(taille/3)
        t.rt(angle)
        # F on construit une branche tout droit
        arbre_branche(t, niveau - 1, taille/3, angle)
        # [-F : on construit une branche sur la droite
        t.rt(angle)
        arbre_branche(t, niveau - 1, taille/3, angle)
        # ] : On revient en arrière
        t.bk(taille/3)
        t.lt(angle)
        # F : on construit une branche tout droit
        arbre_branche(t, niveau - 1, taille/3, angle)

def main():
    # initialisation de Turtle
    t = turtle.Turtle()
    myWin = turtle.Screen()
    myWin.setup(800, 600)
    # On se place pour démarrer
    t.lt(90)
    t.up()
    t.bk(250)
    t.down()
    t.color("green")

    arbre_branche(t, 2, 500, 20)

    # La fenêtre se fermera lors d'un clic de souris
    myWin.exitonclick()

# appel du programme principal
main()
turtle.mainloop() # pour empecher la fenêtre de se fermer

Remarquez le changement de la taille dans l’appel de la fonction, qui correspond à la taille d’une branche du niveau de départ (ici 3). À chaque itération, la taille est divisée par 3 : il faut donc adapter la taille donnée dans l’appel de la fonction pour obtenir quelque chose de réaliste. Pour le calcul de la taille finale de notre plante, il faut faire appel à des notions de mathématiques.

A chaque appel récursif, la taille va être divisée par 3, donc au bout de n appels, la taille sera de $ /frac taille {3^n} $ Mais à ce moment-là, combien y aurat-il de segments tracés sur la tige principale ? Cela dépend du nombre de F hors des crochets qu’il y a dans la règle.

On commence à obtenir quelque chose de sympathique non ?

Mais comment faire si l’on veut changer le motif (la règle) ?

Il faut tout reprogrammer …

Je vous propose plutôt de créer un interpréteur qui va lire une chaine de caractères contenant la séquence à dessiner.

Un interpréteur de règle

Nous allons passer en argument à la fonction arbre_branche une chaîne de caractère regle correspondant à la règle. Pour réaliser notre dessin, il faudra parcourir cette chaine et interpréter chaque caractère.

Vous remarquerez l’utilisation d’une variable de type MaPile qui, comme son nom l’indique, est une classe qui implémente une pile. Si pile est du type MaPile, vous avez accès aux méthode pile.empile(element) et pile.depile().

Vous devez compléter le code ci-dessous :

import turtle

class MaPile():
    """ implémentation d'une pile simple """
    def __init__(self):
        self.pile = []
    
    def estVide(self):
        return (False if len(self.pile) > 0 else True)

    def empile(self, element):
        self.pile.insert(0,element)
    
    def depile(self):
        if not self.estVide():
            return self.pile.pop(0)

def arbre_branche(t, regle, niveau, taille, angle):
    """ interpréteur de règle """
    if niveau == 0:
        t.fd(taille)
    else:
        pile = MaPile() # on crée une pile vide
        for r in regle:
            if r == "F":
                # F : on construit une branche tout droit
                arbre_branche(t, regle, niveau - 1, taille/3, angle)
            elif r == "+":
                # on construit une branche sur la gauche
                t.lt(angle)
            elif r == "-":
                # on construit une branche sur la droite
                t.rt(angle)
            elif r == "[":
                # on empile la position et la direction de la tortue
                position = t.pos()
                direction = t.heading()
                pile.empile((position,direction))
            elif r == "]":
                # on depile la position et la direction de la tortue
                    ...
                # on replace la tortue
                    t.penup()
                    t.setpos(...)
                    t.seth(...)
                    t.pendown()

def main():
    # initialisation de Turtle
    t = turtle.Turtle()
    myWin = turtle.Screen()
    myWin.setup(800, 600)
    # On se place pour démarrer
    t.lt(90)
    t.up()
    t.bk(250)
    t.down()
    t.color("green")

    angle = 20
    regle = "F[+F]F[-F]F"
    arbre_branche(t, regle, 3, 500, 20)

    # La fenêtre se fermera lors d'un clic de souris
    myWin.exitonclick()

# appel du programme principal
main()
turtle.mainloop() # pour empecher la fenêtre de se fermer

Ce que vous devez faire à partir de là :

Ecrivez une règle qui permette de tracer un côté du Flocon de Von Koch et essayez-la.
Essayez de trouver des règles qui donnent des plantes esthétiques

Il est intéressant de s’intéresser à une grammaire un peu plus évoluée. Au lieu de procéder à de la réécriture d’arête, on peut procéder à de la réécriture de noeud (node rewriting en anglais). Cela consiste à envisager des bourgeons desquels les nouvelles branches vont partir. Ces bourgeons seront symbolisés par la lettre X.

On considérera que le point de départ est un bourgeon.

A chaque itération, on remplace les X par une nouvelle branche construite selon la même règle, à une échelle inférieure.

Exemple : considérons la règle X->FF[+FX][-FX] correspondant à la chaîne de caractères ""FF[+FX][-FX]"

Voici ce que l’on obtient lors des 3 premières itérations (on a fait aparaître les bourgeons) :

Ecrivez un programme qui permette de tracer la figure ci-dessus. Vous pourrez l’essayer avec des règles de votre choix …

Des plantes réalistes