Le but du TD est de parcourir tous les déplacements possibles dans un labyrinthe jusqu'à trouver la sortie. On utilisera pour cela des files. Dans l'image ci-dessus la couleur du cheminement indique la distance parcourue depuis l'entrée en haut à gauche.
Nous vous recommandons, si vous utilisez l'éditeur macs, de téléchar au préalable
ce fichier dans votre répertoire personnel (pas das le sous-répertoire où
vous mettez le TD) en gardant le nom .emacs. C'est un fichier de configuration qui
va vous rajouter une option directe de compilation Compile→Buffer. Les erreurs seront
affichées dans une fenêtre en dessous de votre fichier et vous pourrez vous déplacer directement
sur l'erreur en cliquant (bouton du milieu) sur l'erreur.
Les labyrinthes que vous allez afficher et parcourir sont des labyrinthes
rectangulaires, composés de cases qui sont soit franchissables, soit
infranchissables. Les cases du bord seront toujours infranchissables sauf en
haut à gauche (coordonnées (0,1)) et en bas à droite. Ce seront les
cases d'entrée et de sortie.
Les labyrinthes seront naturellement représentés par des tableaux de booléens.
Une case sera codée par true ou false suivant
qu'elle est franchissable ou infranchissable, respectivement. Ainsi, la case
(x, y) sera codée par
lab[x][y].
Pour que vous commenciez directement par les files,
un programme permettant de créer et dessiner un labyrinthe
vous est donné : copiez
Labyrinthe.java dans votre
répertoire de travail pour le TD 2 (et compilez le
une fois pour toutes par javac Labyrinthe.java).
Il est inutile
de lire ce fichier ; pour l'utiliser, il vous suffit
de savoir qu'il contient les lignes suivantes :
class Labyrinthe {
static boolean[][] creeAleatoire (int largeur, int hauteur)
}
class Dessin {
static void imprimeLabyrinthe (boolean[][] lab)
static void imprimePasCouleur (int x1, int y1, int x2, int y2, int coul)
}
Labyrinthe.creeAleatoire (largeur, hauteur)
renvoie un tableau de booléens de taille largeur+2
par hauteur+2 représentant un labyrinthe généré
aléatoirement. (Attention, largeur
et hauteur doivent être impairs.)
Dessin.imprimeLabyrinthe (lab) crée une fenêtre de
nom Drawing et affiche le labyrinthe à l'intérieur.
Dessin.imprimePasCouleur (x1, y1, x2, y2, coul)
matérialise un pas de la case de coordonnées
(x1,y1) vers celle de coordonnées (x2,y2)
avec la couleur coul par un trait d'une case
à l'autre. (coul est un petit entier par exemple :
0, 1, 2, ..., 100, ... Des valeurs proches donnent
des couleurs proches.)
Tester le programme suivant qui crée un labyrinthe 21x21, l'affiche,
puis y dessine un pas de (0,1) vers (1,1) avec
couleur 0. Il est recommandé de ne pas lancer le programme
depuis nedit. Pour quitter votre programme, il faudra taper
Ctrl-C dans la fenêtre où vous l'aurez lancé. On peut changer la
taille du labyrinthe en passant des arguments au programme.
class Parcours
{
public static void main (String[] args) {
int largeur, hauteur ;
if (args.length < 2) largeur = hauteur = 21 ;
else {
largeur = Integer.parseInt (args[0]) ;
hauteur = Integer.parseInt (args[1]) ;
}
boolean[][] lab = Labyrinthe.creeAleatoire (largeur, hauteur) ;
Dessin.imprimeLabyrinthe (lab) ;
Dessin.imprimePasCouleur (0,1,1,1,0) ;
}
}
Il est conseillé de sauvegarder la classe précédente dans un fichier
Parcours.java, et d'écrire ensuite toutes les autres
classes dans ce même fichier. De plus, il pourra être utile de
vérifier la correction des méthodes écrites après chaque question
quand cela est possible.
Un petit rappel pour mieux comprendre les erreurs de compilation en
Java: lorsque vous compilez un programme, ici avec javac
Parcours.java, le compilateur peut aussi être amené à compiler
d'autres fichiers: ainsi, si votre classe File n'est pas
présente dans le fichier Parcours.java, et que vous y
faîtes référence (par File.ajouter(...) par exemple), le
compilateur va automatiquement rechercher un fichier
File.java et le compiler.
Pour chaque classe compilée, le compilateur génère un fichier
.class associé: Parcours.class,
Liste.class, etc... Il vous est alors possible d'exécuter
n'importe lequel de ces fichiers, par java Parcours par
exemple, à condition d'avoir défini auparavant une méthode
static void main(String[]) dans la classe
correspondante. Il est donc possible de définir une telle méthode
main et de l'exécuter pour chaque classe du TP, de façon
à tester chaque classe au fur et à mesure indépendemment des autres .
Pour parcourir le labyrinthe, vous utiliserez une file de pas. Un pas
comprend 4 coordonnées : les deux coordonnées x1 et
y1 du point de départ et les deux coordonnées x2 et
y2 du point d'arrivée.
On va de plus matérialiser la distance parcourue depuis l'entrée
à l'aide de la couleur. Un pas contiendra donc de plus un champ
dist indiquant la distance (en nombre de pas) parcourue
pour atteindre la case (x1,y1).
Pour parcourir le labyrinthe, une file contiendra les pas élémentaires (c'est-à-dire des chemins entre deux cases contiguës) restant à explorer. Les coordonnées de départ et d'arrivée permettront d'afficher facilement les pas au fur et à mesure du parcours.
Écrire une classe Pas avec le constructeur associé
permettant d'initialiser tous les champs.
Pour implanter les files, on utilisera des listes chaînées.
Écrire une classe Liste permettant de stocker
un pas et une référence vers l'élément suivant de la liste
avec le constructeur associé.
Écrire une classe File reposant sur une liste
de sorte que l'ajout d'un nouveau pas se fasse toujours à la
fin de la liste et que l'on ne puisse retirer que le premier élément
de la liste. On dit que la liste est FIFO (First In, First Out) :
un pas entré en premier dans la file en sortira en premier.
Pour pouvoir faire cela efficacement, une file contiendra deux
références : un pointeur premier vers une cellule de
list, qui pointera vers la tête de la file,
et un pointeur dernier qui pointera vers le dernier élément
de la file (voir cours). Si la file est vide, les deux références
contiendront null.
Nous vous rappelons qu'il faut distinguer chaque nœud placé dans la file
(qui sera de type Liste et la file en elle-même, qui sera
de type File.
Pour implanter une file FIFO avec une liste, la recommandation ci-dessus vous semble-t-elle plus judicieuse que d'ajouter les pas au début de la liste et de les retirer à la fin de la liste ?
On implantera entre autres les méthodes :
File (), un constructeur de file vide,
static boolean estVide (File f) qui renvoie
vrai si la file f est vide,
static void ajouter (Pas p, File f) qui ajoute
le pas p dans la file f,
static Pas valeur (File f) qui renvoie le
premier pas de la file f, sans le supprimer de la file.
static void supprimer (File f) qui supprime le
premier pas de la file f.
Dans le cas où l'une de ces fonctions ne pourrait pas retourner un
résultat correct, on pourra lever une erreur en utilisant
throw new Error ("Message d'erreur.").
On pourra tester la correction de ces fonctions au fur et à mesure en utilisant le code suivant:
File file = new File ();
if( !File.estVide(file))
System.out.println("La file devrait etre vide !!");
File.ajouter( new Pas(0,1,1,1,0), file);
if( File.estVide(file))
System.out.println("La file ne devrait pas etre vide !!");
File.ajouter( new Pas(1,1,2,1,1), file);
Pas pas1 = File.valeur(file);
File.supprimer(file);
System.out.println("Le premier pas est a distance " + pas1.dist);
if( File.estVide(file))
System.out.println("La file ne devrait pas etre vide !!");
Pas pas2 = File.valeur(file);
File.supprimer(file);
System.out.println("Le second pas est a distance " + pas2.dist);
if( !File.estVide(file))
System.out.println("La file devrait etre vide !!");
Pour parcourir un labyrinthe, on procédera ainsi: on initialise une
file de sorte qu'elle contienne un seul pas : celui de
l'entrée dans le labyrinthe de (0,1) vers (1,1).
Ensuite, tant que la file n'est pas vide, on retire
un pas de la file. Si ce pas est possible,
on le dessine et on ajoute dans la file
les quatre pas faisables suite à ce pas.
On itère ainsi de suite jusqu'à vider la file.
Si jamais on trouve la sortie, on interrompt le parcours.
Pour ne pas passer indéfiniment sur les mêmes cases, on mettra
à false les cases du labyrinthe au fur et à mesure du
parcours (une fois un pas dessiné, les deux cases du pas doivent
être à false).
Compléter la classe Parcours introduite plus haut
d'une méthode static void parcours (boolean[][] lab)
qui prend en argument le
tableau représentant le labyrinthe à parcourir et dessine
les pas parcourus tel que décrit ci-dessus.
Il convient de bien calculer la distance des pas : ainsi,
si un pas est à distance k de l'entrée, alors
les pas que l'on peut faire à la suite de ce pas sont à
distance k+1 de l'entrée.
Testez aussitôt que possible la méthode parcours en
l'appelant dans la fonction main à la place de la méthode
imprimePasCouleur de la question 1. Si vous bloquez plus de un quart
d'heure sur la question 2.4, utilisez la solution
suivante.
Il s'agit maintenant d'expliciter le chemin de l'entrée vers la sortie trouvé par un parcours :
Pour cela, on rajoutera dans la classe Pas
une référence vers le pas précédant dans le parcours. Ainsi quand on enfile
un pas q à la suite du tracé d'un pas p, on pourra
mettre dans q une référence vers p.
Pour le premier pas du parcours (celui d'entrée de (0,1) à
(1,1)), cette référence vaudra null.
Modifier ce qui précède en conséquence.
Remarquons que les pas sont maintenant chaînés entre eux aussi.
Ce chaînage est complètement indépendant de la structure de Liste
introduite plus haut pour faire des files.
Modifier parcours pour qu'elle renvoie une liste (donnée par une
référence vers le premier maillon) de la suite des pas depuis l'entrée du
labyrinthe jusqu'à la sortie. Indication : on pourra utiliser
une méthode auxiliaire static Liste remonte(Pas p) qui prend en argument
le pas de sortie du labyrinthe et remonte de précédant en précédant jusqu'au
pas d'entrée et construit une liste en ordre inverse de ces pas. La
méthode ne devra pas altérer les références existantes entre les pas
et ne devra pas faire d'allocation mémoire inutile
(seuls des maillons de liste doivent être créés). Il est recommandé de
faire une version itérative.
Écrire deux versions d'une méthode permettant de dessiner la suite des
pas de l'entrée vers la sortie trouvé par le parcours, une itérative
qui dessinera en noir et une récursive qui dessinera en rouge. On
pourra utiliser les méthodes suivantes de la classe Dessin
permettant d'imprimer un pas en noir ou en rouge :
static void imprimePasNoir (int x1, int y1, int x2, int y2)
static void imprimePasRouge (int x1, int y1, int x2, int y2)
Écrire dans la classe liste une méthode
static Liste[] dedouble (Liste l) permettant de
séparer une liste de pas en deux listes : celle des pas
en positions impaires et celle des pas en positions paires.
(La méthode renverra un tableau de deux listes.)
On pourra procéder récursivement, mais cela n'est pas une obligation.
Dédoubler la suite des pas obtenue de l'entrée vers la sortie
du labyrinthe,
dessiner les pas en positions impaires en noir et ceux en positions
paires en rouge de manière à obtenir un pointillé :
Il s'agit maintenant de remplacer la file par une pile.
Implanter une classe Pile sur la base d'une liste chaînée. Un
objet de type Pile contiendra simplement une référence vers
le premier maillon de la liste. Le début de la liste sera considéré comme
le sommet de la pile. Là encore, on distinguera la pile en elle-même
(objet de classe Pile) les nœuds dans la liste
(objets de classe Liste).
Implanter des méthodes similaires à celles de la
classe File avec un système d'exceptions similaires.
Tester des parcours à base de pile. Comparer les deux parcours
avec des labyrinthes creux construits par la méthode suivante
de la classe Labyrinthe (le seuil
entre 0.0 et 1.0 règle le nombre de cases noires : plus
le seuil est proche de 0, moins il y a de cases noires) :
static boolean[][] creeSeuil (int largeur, int hauteur, double seuil)
On pourra tester les deux parcours sur le même labyrinthe
en utilisant la méthode suivante de Labyrinthe
pour restaurer le labyrinthe :
static boolean[][] copie (boolean[][] lab)
À votre avis, est-il possible de trouver un chemin plus court de l'entrée jusqu'à la sortie du labyrinthe que celui trouvé par le parcours avec la file ?
Nous vous proposons une solution. Cependant, il n'y a pas une seule façon de faire !