TD-2, Graphisme et récursion
|
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 :
-
Avancer d'un pas (step) dans la direction courante en
laissant une trace.
``
F
''
- Avancer d'un pas (step) dans la direction courante en sautant,
``
f
''.
- Tourner à gauche d'un angle delta, ``
-
''.
- Tourner à droite du même angle delta, ``
+
''.
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 :
-
La classe Tortue ne démarre pas toute nue dans la vie.
Elle hérite de la classe MacLib
(
class Tortue extends MacLib
). Cela lui permet de disposer d'entrée de jeu de toutes les
méthodes de la MacLib.
On écrira donc simplement initQuickDraw()
au lieu de
MacLib.initQuickDraw()
pour, par exemple, initialiser
l'interface graphique.
Pour plus de renseignements, vous pourrez regarder
les sections sur l'héritage et la
notation abrégée dans les
morceaux de Java.
- On aura bien évidemment besoin de méthodes particulières de la
MacLib, essentiellement pour tracer des traits,
voir la description de la MacLib dans les morceaux de Java.
- On aura également besoin de quelques fonctions numériques (genre
cosinus). Voir la description de la librairie
Math. Attention aux types,
les fonctions trigonométriques travaillent en double
(flottants double précision), tandis que les primitives graphique
prennent des int (entiers normaux) en argument, il faudra
recourrir à des arrondis puis à des
casts de long (entiers longs) en
int (entiers normaux). Il vaut mieux
procéder à ces conversions au tout dernier moment,
afin de préserver la précision.
- Dans la fenêtre graphique, l'origine des coordonnées est en haut
et à gauche, les abscisses croissantes vont vers la droite (logique)
et les ordonnées croissantes vers le bas (plus étrange).
Solution.
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.
-
Si d est nul, alors laisser
F
tel quel.
- Sinon, on remplace
F
par F-F++F-F
que l'on expanse
à nouveau en posant d=d-1.
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:
-
-depth d Spécifie la profondeur de l'expansion.
- -rule C S Définit l'expansion du caractère C comme
étant la suite de charactères S.
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 :
-
On crée un nouveau buffer par l'appel de constructeur
``new StringBuffer ()''.
- L'appel de méthode
``buff.append("coucou")'' permet
d'ajouter la chaîne "coucou" à la fin du buffer buff.
- L'appel de méthode
``buff.toString()'' renvoie une chaîne qui est le contenu du
buffer buff.
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.
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 :
-
Sauver l'état courant de l'interprète : ``
[
''.
- Revenir au dernier état sauvé : ``
]
''.
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.
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.
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.
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.