TD-2, Graphisme et récursion




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-2/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

1 Un petit interprète graphique
Soit un tout petit langage de commande d'une tortue graphique, composé de quatre instruction seulement. À un instant donné la tortue est dans un état donné (un x, un y et une direction courante). Les quatre instructions suivantes modifient cet état, la première en profite pour dessiner un trait au passage : La tortue ignore tous les autres caractères, c'est à dire qu'elle passe au caractère suivant sans se troubler.

Il est demandé d'écrire l'interprète de ce petit langage. L'interprète prend des options en argument qui donnent les valeurs de step et delta, ainsi que l'état initial de la tortue (position en x et y, direction initiale). Il prend aussi un programme (une suite d'instructions) en argument.

Ainsi, l'appel (à saisir à la souris !) :
java Tortue  -x 100 -y 100 -delta 60 -step 100 F+F+F+F+F+F+
devra donner ce dessin:
Pour se concentrer sur ce qui est important (l'écriture de l'interprète), vous ne partez pas de zéro, mais du programme à trous Tortue.java.

Ce programme réalise déjà le traitement des options et l'initialisation de la fenêtre graphique (à une taille de 400 par 400). Il faut remarquer les points suivants : Solution.

2 Définition récursives
Nous alons maintenant enrichir notre interprète avec des définition (potentiellement) récursives, afin de dessiner des fractales. Une règle du genre F -> F-F++F-F produit une suite d'instructions par expansions successives. Soit d la profondeur d'expansion. Les caractères non-définis par une règle seront également laissés tel quels (cela s'applique en particulier pour ``+'' et ``-'').

Ainsi, voici les expansions successives de F, pour une valeur initiale d=2.
F,    F-F++F-F,     F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
Vous pouvez d'ailleurs vous donner une idée du dessin produit par
java Tortue -step 40 F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
(Les valeurs par défaut des options non données conviennent à ce dessin.) Vous noterez la schizophrénie de ``F'' qui n'a pas le même comportement selon que l'on expanse ou que l'on dessine. Vous obtiendrez cette image :

Il faut en partant de la classe Tortue, créer une nouvelle classe Fractal qui prend les options supplémentaires suivantes: Ainsi, l'appel
java Fractal -step 4 -depth 4 -rule F F-F++F-F  F
Devrait produire ce joli dessin :

Il est conseillé d'expanser d'abord les caractères du programme d fois, puis d'appeler l'interprète de la question précédente sur le programme complètement expansé.

L'expanseur devra donc prendre en argument une chaîne et un niveau d'expansion, et renvoyer une chaîne:
static String expanse (String s, int d)
Pour des raisons d'efficacité, l'expanseur devra utiliser de façon interne un objet de la classe StringBuffer. J'attire votre attention sur les points suivants : Une fois que votre programme fonctionne, produire le flocon complet (ce n'est pas difficile à partir de la règle déjà donnée) :
Ensuite, attaquez vous à l'île, dont voici les dessins aux premiers ordres. Regardez bien l'île d'ordre un.

Solution.

3 Interprète récursif
Tel qu'il est l'interprète a du mal à dessiner des arbres. En effet, pour dessiner un arbre dont les branches fourchent deux par deux :
Il faut, à chaque fourche, dessiner une branche, puis revenir au point de branchement avant de dessiner la deuxième branche. Il faut donc être capable de se souvenir de l'état de la tortue à n'importe quel moment puis revenir dans cet état. On notera, qu'il peut y avoir à un instant donné, un nombre quelconque d'états sauvegardés. (Dans le cas de l'arbre tous les points de fourchement qui mènent au point courant en suivant la première branche.)

On ajoute donc deux instructions à l'interpréteur : Le viel informaticien blanchi sous le harnais se rend rapidement compte qu'il faudra une pile des états en attente. L'instruction ``['' empile l'état courant, tandis que l'instruction ``]'' dépile un état qui devient l'état courant. Faîtes lui confiance, c'est comme ça que ça marche.

L'informaticien astucieux se souvient alors que Java autorise la récursion et qu'il ``suffit'' d'écrire un interprète qui se rappelle récursivement en cas de ``['' et retourne en cas de ``]''. (Il reste quelques détails à régler !) Une fois réalisé ce petit tour de force, on pourra dessiner l'arbre ci-dessus par une règle du genre ``-rule T [+FT]-FT'' et un angle delta pas trop grand. (Reflexion faite, un règle ``-rule T F[+T]-T'' semble un peu plus réaliste.)

Ensuite, avec la règle ``-rule D FD'' qui permet de faire décroître la taille des branches au fur et à mesure que la récursion s'approfondit, on peut dessiner de jolis arbres (par vent d'ouest modéré) :
java Fractal -x 155 -y 380 -step 6 -angle -90 -delta 20 -rule T D[-T]D[++T]T -rule D FD T -depth 8
Et par fort vent d'ouest :

Solution.

4 Prolongements

4.1 Plus de fractales
Trouver les règles qui produisent diverses fractales. Par exemple, la courbe du dragon (pas évident à mon avis), ou la courbe de Hilbert ou encore. Vous vous rendrez compte qu'il n'est pas facile de décrire une fractale avec les mains.

4.2 Plus pratique
Il n'est vraiment pas pratique de devoir donner soi-même au programme les coordonnées initiales de la tortue et la valeur du pas step. Or, il est possible, en dessinant d'abord la figure avec des valeurs quelconques pour ces paramètres, d'en déduire les valeurs les plus adéquates. Réaliser cette extension bien pratique.

4.3 Plus puisssant
Essayez d'optimiser votre programme. Par exemple, si il plante par manque de mémoire à un certain ordre d dans le tracé du flocon, gagnez au moins un ordre. Une première piste simple est d'écrire un expanseur récursif qui expanse localement chaque caractère (au lieu d'un expanseur itératif qui parcourt d chaînes de plus en plus longues).

Pour aller encore plus loin, il faudra sans doute mélanger expansion et interprétation, ce qui évitera de contruire une grosse chaîne pour le programme. C'est un peu plus difficile à faire, à cause des instructions ``['' et ``]''. On pourra faire l'hypothèse simplificatrice que ces crochets sont toujours bien parenthésés localement (i.e., dans un bout de programme qui est, soit le programme de départ, soit un membre droit de règle).


Dernière modification : 2002-11-27

Ce document a été traduit de LATEX par HEVEA.