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 :

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 par classes disjointes (voir cours et TD de la semaine dernière) avec l’algorithme d’Eller

Organisation du code

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

On pourra s’aider de la figure suivante.

directions

1. Solution de labyrinthes par rebroussement

Dans ce premier exercice 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) à celle avec les coordonnées (height-1, width-1). Le chemin doit être signalé avec des marques sur les cases. Plus précisément, un appel à la méthode marked doit renvoyer true pour toutes les cases sur le chemin et false pour toutes les cases qui ne sont pas sur le chemin. Dans tous les labyrinthes que nous utilisons, le chemin à trouver est unique, c’est-à-dire que les labyrinthes sont parfaits.

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 public boolean searchPath(int i, int j) de la classe Maze pour trouver le chemin en utilisant la technique du rebroussement. La méthode est initialement appelée avec les paramètres (0, 0).

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

En remarquant que l’on peut atteindre la sortie depuis la case (i, j) 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. Tester si nous sommes déjà à la destination, terminer si oui.
  3. Pour toutes les cases voisines : si le voisin est directement accessible 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.

Tester 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 l’exercice 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 pourrons créer un cycle et le labyrinthe ne sera 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 utilisons le squelette suivant pour parcourir le tableau des directions aléatoirement :

                List<Direction> dirs = Arrays.asList(Direction.values());
                Collections.shuffle(dirs);

                for(Direction dir : dirs) {
                        // TODO
                }

Nous avons donc la structure suivante simple pour notre algorithme dans la méthode public void generateRec(int i, int j) :

Tester 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. Nous utilisons la classe Coordinate pour encapsuler et stocker les coordonnées i et j.

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. L’énumération SelectionMethod a les valeurs possibles Newest, Oldest, Middle et Random. Toutes les quatre ont la méthode nextIndex qui renvoie un entier entre 0 (inclus) et une borne donnée (exclue).

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.

En tous les cas, l’algorithme commence avec une liste qui ne contient que l’élément (0, 0), le point de départ et rentre dans le squelette suivant :

                LinkedList<Coordinate> coords = new LinkedList<Coordinate>();
                coords.add(new Coordinate(0, 0));

                while(!coords.isEmpty()) {
                        slow();
                        int ind = meth.nextIndex(coords.size());

                        // TODO
                }

Pour maintenant implémenter l’algorithme itératif dans la méthode public void generateIter(SelectionMethod meth), on peut suivre le processus suivant :

  1. Choisir un nouvel élément de la liste selon la SelectionMethod si possible. Sinon terminer.
  2. Pour toutes les cases adjacentes dans un ordre aléatoire : si le voisin est isolé, créer une connexion, 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.

Comme nous l’avons fait dans la méthode generateRec, nous pouvons créer une permutation dir de l’ensemble des directions avec les instructions :

                        List<Direction> dirs = Arrays.asList(Direction.values());
                        Collections.shuffle(dirs);

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

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

4. Bonus : Génération alternative par classes disjointes : algorithme d’Eller

Vous avez vu en cours la semaine dernière une méthode pour générer des labyrinthes en utilisant des classes disjointes. L’idée générale de cette technique est de parcourir les connexions possibles et de créer une connexion seulement si les deux cellules appartiennent à deux classes distinctes. Cela garantit qu’aucun cycle n’est créé, c’est-à-dire qu’on finit bien avec un labyrinthe parfait.

La méthode présentée en cours choisissait les connexions possibles dans un ordre aléatoire. Dans cet exercice nous allons parcourir les connexions possibles systématiquement du haut vers le bas : nous commençons avec les connexions possibles horizontales de la première ligne, puis les connexions possibles verticales entre la première ligne et la deuxième ligne, puis les connexions possibles horizontales de la deuxième ligne et ainsi de suite.

Un avantage de cette méthode est que l’on ne regarde chaque ligne qu’une seule fois. En ce sens, c’est l’antithèse du rebroussement. Le fait de ne pas mettre de connexion entre deux cellules de la même classe garantit l’absence de cycles. Pour garantir la connexité du labyrinthe final, on doit créer au moins une connexion verticale pour chaque classe d’une ligne. Dans la dernière ligne, on va créer les connexions nécessaires pour terminer avec une seule classe.

Cette méthode de génération s’appelle l’algorithme d’Eller. Il procède comme suit :

  1. Pour chaque ligne sauf la dernière :
    1. parcourir toutes les paires de cellules adjacentes de cette ligne dans un ordre aléatoire et les connecter avec probabilité 0.5 si elles appartiennent à des classes différentes ;
    2. pour chaque classe qui existe dans la ligne, créer un nombre aléatoire de connexions vers la ligne suivante, mais au moins une par classe.
  2. Dans la dernière ligne, parcourir les paires de cellules adjacentes dans un ordre aléatoire et les connecter si elles appartiennent à des classes différentes.

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

algorithme d'Eller

Implémenter l’algorithme d’Eller en complétant la méthode generateEller(). Les classes Coordinate et UnionFind suivantes seront utiles :

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

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


Voici une solution possible : solution.zip