TD4 : Rebroussement, solution et génération de labyrinthes

Votre opinion sur le cours de lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

Avertissement

Afin de minimiser les risques d’erreurs de manipulation lors des dépôts de fichiers, toutes les classes que vous avez à modifier sont réunies dans un même fichier TD4.java que vous devez déposer après chaque question.

(On rappelle néanmoins qu’en dehors de circonstances exceptionnelles, on écrit plutôt des classes différentes dans des fichiers différents, tant pour la lisibilité du code que pour l’efficacité de la compilation.)

Avant de commencer

Contexte

Le TD adopte le plan suivant :

  1. Solution de labyrinthes par rebroussement
  2. Génération de labyrinthes par rebroussement en version récursive
  3. Génération de labyrinthes par rebroussement en version itérative
  4. Génération de labyrinthes uniformement distribués avec l’algorithme de Wilson

Organisation du code

Le code que vous venez de télécharger est organisé en plusieurs classes. Voici leurs fonctionnalités principales :

1. Solution de labyrinthes par rebroussement

Dans cette première question, nous voulons trouver un chemin dans un labyrinthe donné, allant du coin nord-ouest au coin sud-est, c’est-à-dire de la case avec les coordonnées (0, 0) à la sortie, dans notre cas celle avec les coordonnées (height-1, width-1). La méthode isExit de la classe Cell peut être utile : elle renvoie true si et seulement si la case actuelle est la sortie. Le chemin doit être signalé avec des marques sur les cases. Plus précisément, un appel à la méthode isMarked doit renvoyer true pour toutes les cases sur le chemin et false pour toutes les cases qui ne sont pas sur le chemin.

Par exemple, dans le labyrinthe 5x5

labyrinthe 5x5

le chemin unique du nord-ouest au sud-est est

labyrinthe 5x5 avec solution

où une case marquée se distingue par un cercle rouge.

Compléter la méthode searchPath de la classe Cell pour qu’elle renvoie true s’il existe un chemin dans le labyrinthe entre la case courante et la sortie. Pour cela, on implémentera récursivement la technique du rebroussement. En remarquant que l’on peut atteindre la sortie depuis la case courante si et seulement si on peut atteindre la sortie depuis l’une de ses voisines, une stratégie peut être la suivante :

  1. Marquer la case actuelle.
  2. Terminer si la case courante est la destination.
  3. Pour toutes les cases voisines : si le voisin n’est pas séparé par un mur et n’est pas encore marqué, faire un appel récursif. Terminer en cas de succès.
  4. Supprimer la marque de la case actuelle et rebrousser.

Pour trouver un chemin de l’entrée à la sortie dans le labyrinthe, il suffira d’appeler la méthode sur l’instance de Cell représentant la case (0,0). C’est ce qui est fait dans les tests.

Vous remarquez sans doute que la méthode commence avec l’appel maze.slow(). C’est utilisé pour ralentir l’animation de la recherche de chemin pour qu’elle soit observable à l’œil nu.

Testez avec le fichier Test1.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Génération par rebroussement récursif

Dans le reste du TD, nous allons travailler sur la génération de labyrinthe. Comme pour les labyrinthes de la question 1, ils doivent être parfaits, c’est-à-dire avoir la propriété qu’il y ait un chemin unique entre chaque paire de cases. Initialement, toutes les cases sont isolées.

Le rebroussement récursif pour la génération a la même structure générale que la recherche de chemin. Une différence est qu’il n’est pas nécessaire de marquer des cases. Une autre différence est la condition pour l’appel récursif : Nous voulons continuer seulement si le voisin est isolé. Sinon, nous créons un cycle et le labyrinthe n’est pas parfait.

Pour ne pas toujours aboutir au même labyrinthe, nous voulons parcourir les directions dans un ordre aléatoire. Pour faire cela on peut utiliser la méthode statique shuffle de la classe auxiliaire Collections qui prend une liste et la permute aléatoirement.

Nous avons donc la structure suivante simple pour notre algorithme dans la méthode generateRec :

Testez votre méthode avec le fichier Test2.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Génération par rebroussement itératif

Nous allons maintenant traduire l’algorithme de génération récursif en une version itérative. Cela veut dire que nous échangeons la pile d’appels contre une liste chaînée qui contient les coordonnées des cases dont nous avons commencé le traitement.

Une approche itérative peut avoir plusieurs avantages : moins d’espace sur la pile d’appels et plus de contrôle sur l’ordre dans lequel les cases sont visitées. La pile d’appels choisit toujours l’élement le plus récent. Avec une liste explicite on peut changer ce comportement.

La classe Bag (implémentée dans le fichier Util.java, que vous n’avez pas besoin de regarder) permet de choisir la méthode selon laquelle le prochain élément (de type Cell) d’une liste est choisi. Les différentes méthodes sont NEWEST, OLDEST, MIDDLE et RANDOM. Pour chacun des quatre choix, la méthode peek renvoie l’élément sélectionné selon le choix. La méthode pop supprime cet élément. Les deux méthodes supposent une liste non-vide. Pour tester si la liste est effectivement vide, on peut utiliser la méthode isEmpty. La méthode add permet de rajouter un nouvel élément à la fin de la liste.

Pour implémenter l’algorithme itératif dans la méthode generateIter, on peut suivre le processus suivant. L’algorithme commence avec une liste qui ne contient que l’élément (0, 0), puis rentre dans une boucle, comme ceci :

  1. Si la liste n’est pas vide, choisir un élément de la liste selon la méthode de sélection. Sinon terminer.
  2. Pour toutes les cases adjacentes dans un ordre aléatoire : si le voisin est isolé, créer un passage, rajouter le voisin à la liste et aller à l’étape 1.
  3. Si l’on a épuisé toutes les directions autour de la case actuelle, supprimer cette case de la liste et revenir à l’étape 1.

Vous pouvez remarquer qu’un choix de NEWEST revient à la version récursive. Un choix de RANDOM produit des labyrinthes tout à fait intéressants aussi, ce qui n’est pas le cas pour les choix MIDDLE ou OLDEST.

Testez votre méthode avec le fichier Test3.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4. Génération uniforme : algorithme de Wilson

Nous venons d’implémenter des algorithmes de génération de labyrinthe aléatoires. La forme des labyrithes générés par le rebroussement itératif dépendait fortement du choix de la méthode de sélection de la prochaine case à traiter. En particulier, les labyrinthes générés ne sont pas uniformement distribués dans l’ensemble de tous les labyrinthes parfaits de la taille donnée.

Dans cet exercice nous allons donc implémenter un algorithme de génération uniforme. La méthode de génération choisie s’appelle l’algorithme de Wilson. Il procède comme suit :

  1. Choisir une case uniformement par hasard et la marquer.

  2. Tant qu’il y a une case non-marquée, choisir une case non-marquée uniformement par hasard, et

    1. générer une marche aléatoire uniforme à partir de la case choisie jusqu’à ce qu’une case marquée soit rencontré (on ignore les murs pour générer la marche). Supprimer les boucles de la marche : on ne garde que la dernière sortie de chaque case.
    2. marquer toutes les cases et créer les connexions (en supprimant les murs avec breakWall) le long la marche générée.

Voici l’algorithme en plein milieu d’exécution :

algorithme de Wilson

Implémenter l’algorithme de Wilson en complétant la méthode generateWilson(). Pour tirer des cases uniformes aléatoires successivement, il suffit de mélanger la liste des cases. On pourra ajouter à la classe Cell un champ Cell next, pour garder trace de la direction prise par la marche aléatoire la dernière fois qu’elle quitte une case.

Testez votre méthode avec le fichier Test4.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer