TD 4 : parcours de labyrinthe
Ce sujet est inspiré d'un sujet de Laurent Mauborgne.
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.
Quand vous aurez finis de répondre aux questions qui suivent, déposez vos fichiers en utilisant la ligne de commande :
/users/profs/info/Depot/INF_421/deposer vos_fichiers_java TD_4 votre_groupe
où vos_fichiers_java est la liste des fichiers que vous déposez (séparés par des espaces) et votre_groupe est votre numéro de groupe en informatique.
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.
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 4 (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)
}
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) ;
}
}
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 : une vers le premier maillon de la liste et une vers le dernier. Si la file est vide, les deux références vaudront null.
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 :
Pour gérer proprement les cas inattendus de file vide, on utilisera une exception :
class FileVideException extends Exception {
}
On laissera le corps de la classe FileVideException en se contentant du constructeur par défaut. On pourra par exemple lever une exception en cas de file vide par throw new FileVideException (). Ne pas oublier de rajouter throws FileVideException à la déclaration des méthodes qui risquent de renvoyer une telle exception.
Au cas où la référence vers le début de la liste serait null mais pas celle vers la fin de la liste, il est logique que la méthode estVide() (qui est utilisée par supprimer() et valeur()) lève une erreur par un appel du type throw new Error ("Etat de file anormal."). En effet, une telle erreur ne viendrait pas d'une mauvaise utilisation de la classe File, mais d'un bug dans sa programmation. Il n'est donc pas question de laisser passer une telle erreur. Pour une levée d'erreur, il est inutile de déclarer une clause throws ..., contrairement à une levée d'exception.
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 parcours 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 paramétrer 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.
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.) 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. Implanter des méthodes similaires à celle 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 ?
/users/profs/info/Depot/INF_421/deposer vos_fichiers_java... TD_4 votre_groupe...