Au début était la tortue Logo

Christophe Vu-Brugier

2016-03-20

Quand j'étais à l'école primaire, notre classe disposait de deux ordinosaures Thomson MO5 et TO7, reliques du plan français informatique pour tous. Ces deux machines étaient déjà dépassées à l'époque et décoraient le fond de notre classe.

Un jour, l'institutrice dépoussiéra un des ordinateurs Thomson et le démarra. Je me souviens que cet ordinateur austère, avec son crayon optique, était particulièrement pénible à utiliser. Son utilisation difficile avait de quoi entamer la curiosité d'un enfant, mais l'ordinateur proposait néanmoins une application amusante : la tortue Logo.

C'est cette tortue Logo que je vais essayer d'animer dans cet article en présentant un script écrit en Python capable d'afficher sa trace. Le tout en moins de 100 lignes de code que je commenterai.

Principe de la tortue Logo

La tortue Logo est un robot qui se déplace à la surface de l'écran. Un crayon est attaché à la tortue et trace son chemin quand il est baissé. La tortue obéit aux commandes formulées par son guide comme AVANCE, REPETE ou TOURNEDROITE.

Voici plusieurs polygones tracés par la tortue Logo, du triangle à l'octogone :

REPETE 3 [ AVANCE 50 TOURNEDROITE 120 ]
REPETE 4 [ AVANCE 50 TOURNEDROITE 90 ]
REPETE 5 [ AVANCE 50 TOURNEDROITE 72 ]
REPETE 6 [ AVANCE 50 TOURNEDROITE 60 ]
REPETE 8 [ AVANCE 50 TOURNEDROITE 45 ]

Mise en oeuvre et contraintes

Je m'impose les contraintes suivantes pour le programme capable d'afficher la trace d'une tortue Logo.

Le programme doit peser moins de 100 lignes de code.
Le programme est implémenté en Python. Comme chacun sait le python et la tortue sont des reptiles. Plus sérieusement, l'expressivité du langage Python et ses nombreux modules sont de précieux atouts pour respecter l'objectif de concision.
Le code du programme est en français (même si les mots clefs sont en anglais). Je ne parlais pas anglais à l'école primaire. De plus, la tortue ne comprend que le français.
Le programme enregistre la trace de la tortue dans une image adaptée à la publication sur le Web. Le format choisi est le format vectoriel SVG.
Le programme est suffisamment élaboré pour "tracer mon logo en Logo". Mon logo est un space invader façon pixel art.
Le programme n'est pas interactif. Il accepte en entrée un fichier contenant les commandes Logo et génère en sortie une image vectorielle SVG.

Ma tortue Logo en Python

Voici les 98 lignes de ma tortue Logo écrite en Python (fichier source). L'implémentation est grandement simplifiée en utilisant les bibliothèques pyparsing et svgwrite.

#!/usr/bin/python3

from collections import namedtuple
from math import cos, sin, pi
import sys
from pyparsing import Group, Keyword, Literal, nums, OneOrMore, ParseResults, replaceWith, Word
from svgwrite import Drawing
from svgwrite.path import Path

av = Group((Keyword('AV') | Keyword('AVANCE')).setParseAction(replaceWith('AV')) + Word(nums))
bc = Group(Keyword('BC') | Keyword('BAISSECRAYON').setParseAction(replaceWith('BC')))
lc = Group(Keyword('LC') | Keyword('LEVECRAYON').setParseAction(replaceWith('LC')))
re = Group((Keyword('RE') | Keyword('RECULE')).setParseAction(replaceWith('RE')) + Word(nums))
td = Group((Keyword('TD') | Keyword('TOURNEDROITE')).setParseAction(replaceWith('TD')) + Word(nums))
tg = Group((Keyword('TG') | Keyword('TOURNEGAUCHE')).setParseAction(replaceWith('TG')) + Word(nums))
commande = av | bc | lc | re | td | tg
repete = Group(Keyword('REPETE') + Word(nums) + Literal('[').suppress() + OneOrMore(commande) + Literal(']').suppress())
logo = OneOrMore(repete | commande)

LARGEUR_CANEVAS = 400

Position = namedtuple('Position', 'x y')

class Tortue:
    def __init__(self) -> None:
        self.pos = Position(LARGEUR_CANEVAS / 2, LARGEUR_CANEVAS / 2)
        self.cap = 0  # en degres : 0 => haut, 90 => droite
        self.crayon_bas = True
        self.chemin = Path(d=f'M{self.pos.x},{self.pos.y}', stroke = 'black', fill='white')

    def __radian(self) -> float:
        return self.cap * pi / 180.0 - pi / 2.0

    def avance(self, nb_pas: int) -> None:
        self.pos = Position(self.pos.x + int(round(cos(self.__radian()) * nb_pas)),
                            self.pos.y + int(round(sin(self.__radian()) * nb_pas)))
        if self.crayon_bas:
            self.__svg_lineto()

    def recule(self, nb_pas: int) -> None:
        self.avance(- nb_pas)

    def tourne_droite(self, angle: int) -> None:
        self.cap = (self.cap + angle) % 360

    def tourne_gauche(self, angle: int) -> None:
        self.tourne_droite(- angle)

    def baisse_crayon(self) -> None:
        self.crayon_bas = True
        self.__svg_moveto()

    def leve_crayon(self) -> None:
        self.crayon_bas = False

    def trace_commandes(self, commandes: ParseResults) -> None:
        for cmd in commandes:
            if cmd[0] == 'AV':
                self.avance(int(cmd[1]))
            elif cmd[0] == 'RE':
                self.recule(int(cmd[1]))
            elif cmd[0] == 'TD':
                self.tourne_droite(int(cmd[1]))
            elif cmd[0] == 'TG':
                self.tourne_gauche(int(cmd[1]))
            elif cmd[0] == 'BC':
                self.baisse_crayon()
            elif cmd[0] == 'LC':
                self.leve_crayon()
            elif cmd[0] == 'REPETE':
                nb = int(cmd[1])
                for _ in range(nb):
                    self.trace_commandes(cmd[2:])

    def trace_programme(self, programme: str) -> None:
        self.trace_commandes(logo.parseString(programme))

    def trace_fichier(self, fichier: str) -> None:
        with open(fichier, 'r') as contenu:
            self.trace_programme(contenu.read())

    def __svg_moveto(self) -> None:
        self.chemin.push(f'M{self.pos.x},{self.pos.y}')

    def __svg_lineto(self) -> None:
        self.chemin.push(f'L{self.pos.x},{self.pos.y}')

    def enregistre_svg(self, fichier: str) -> None:
        dessin = Drawing(fichier, profile='full', fill='white')
        dessin.add(self.chemin)
        dessin.save()


if __name__ == '__main__':
    tortue = Tortue()
    tortue.trace_fichier(sys.argv[1])
    tortue.enregistre_svg(sys.argv[2])

Quelques commentaires

Un peu de trigonométrie

Au départ, la tortue Logo est positionnée au centre de l'écran et pointe vers le Nord. Depuis sa position initiale, elle se déplace pas à pas et peut tourner sur sa droite ou sur sa gauche par degrés.

Par exemple, la tortue Logo trace un triangle de 100 pas de côté quand elle avance de 100 pas et tourne de 120 degrés sur sa droite à trois reprises :

REPETE 3 [ AVANCE 100 TOURNEDROITE 120 ]

Pour calculer la position de la tortue après chaque déplacement, il faut tenir compte :

de la position initiale de la tortue ;
de son orientation ;
du nombre de pas qu'elle doit effectuer.

Un soupçon de grammaire

La tortue Logo obéit à des commandes qui ressemblent au langage naturel (AVANCE, TOURNEDROITE, REPETE, etc.). Une partie de notre programme est donc dévolue à l'analyse syntaxique (parsing, en anglais) des commandes Logo.

La bibliothèque pyparsing permet d'implémenter un analyseur syntaxique avec Python en décrivant une grammaire formelle.

Voici, par exemple, la grammaire formelle du mini langage Logo interprétable par notre tortue.

av ::= "AVANCE" + nombre
bc ::= "BAISSECRAYON"
lc ::= "LEVECRAYON"
re ::= "RECULE" + nombre
td ::= "TOURNEDROITE" + nombre
tg ::= "TOURNEGAUCHE" + nombre
commande ::= av | bc | lc | re | td | tg
repete ::= "REPETE" + nombre + "[" + UnOuPlus(commande) + "]"
logo ::= UnOuPlus(repete | commande)

La transcription en Python avec pyparsing se fait presque directement. Pour chaque commande, on définit aussi un raccourci (e.g. AV pour AVANCE) :

av = Group((Keyword('AV') | Keyword('AVANCE')).setParseAction(replaceWith('AV')) + Word(nums))
bc = Group(Keyword('BC') | Keyword('BAISSECRAYON').setParseAction(replaceWith('BC')))
[...]
commande = av | bc | lc | re | td | tg

Une fois que pyparsing a digéré les commandes Logo, la fonction trace_commandes() identifie chaque commande et ses éventuels paramètres et les transmet à la fonction associée :

def trace_commandes(self, commandes: ParseResults) -> None:
    for cmd in commandes:
        if cmd[0] == 'AV':
            self.avance(int(cmd[1]))
[...]
        elif cmd[0] == 'BC':
            self.baisse_crayon()
[...]
        elif cmd[0] == 'REPETE':
            nb = int(cmd[1])
            for _ in range(nb):
                self.trace_commandes(cmd[2:])

À noter que la fonction trace_commandes() utilise la récursivité pour gérer la commande REPETE.

Un chemin vers SVG

La trace de la tortue Logo est dessinée dans une image SVG avec la bibliothèque svgwrite. Le programme n'utilise qu'un seul élément de SVG, le path qui est parfaitement adapté à notre usage.

Un path SVG comprend un attribut d (pour data) qui est une liste de commandes L (pour lineto) ou M (pour moveto) suivies des coordonnées cartésiennes. La première commande d'un path SVG doit être une commande moveto.

Par exemple, pour tracer un angle droit, il faut donner les coordonnées de trois points et tracer deux lignes entre ces trois points :

<path d="M10,10  L10,100  L100,100"/>

Dans le cas de notre tortue Logo, il suffit d'un path SVG pour matérialiser sa trace.

Quand la tortue reçoit la commande BAISSECRAYON, on ajoute une commande moveto pour débuter sa trace.
À chaque déplacement de la tortue, on ajoute une commande lineto au path SVG si le crayon est baissé.

Pixel art vectoriel

Pour conclure, j'ai demandé à la tortue Logo de tracer le space invader qui me sert d'avatar (fichier source).

Enfin, la vidéo suivante montre la tortue Logo filant à toute allure telle un lièvre.

Tortue Logo : LEVECRAYON.