1.1 Grille et indexation

• Le labyrinthe a rows × cols cellules (voir ci-contre un exemple 9×9).
• La représentation utilise une grille augmentée de taille R × C avec :
  • R = 2*rows + 1
  • C = 2*cols + 1
• La grille augmentée est stockée dans un tableau linéaire Maze.Cell[] grid.
• La case (i, j) de la grille augmentée, ligne i, colonne j, se trouve à l’indice i + R*j.
• Selon sa position dans la grille augmentée une case (i,j) peut être de l’un des types suivants :
  • une cellule, quand i et j sont impairs ;
  • une case de bord, quand i == 0 || i == R-1 || j == 0 || j == C-1 ;
  • un passage entre cellules, quand l’un des indices est pair et l’autre impair et que la case n’est pas au bord ; le passage peut être ouvert ou fermé par un mur amovible ;
  • un pilier, quand i et j sont pairs. Ces cases ne sont jamais utilisées.

1.2 Codes de cellule

Chacune des cases de la grille a un état parmi les valeurs suivantes.

enum Cell {
  VOID, WALL, REMOVABLE, RIGHT, UP, LEFT, DOWN, MARK
}

• Les piliers et les cases de bords (en gris dans l’image) sont WALL.
• Les cellules (en blanc dans l’image) sont VOID ou marquées par la marque neutre MARK ou une marque directionnelle (RIGHT, UP, LEFT, DOWN).
• Les passages (en vert) sont VOID (passage ouvert) ou REMOVABLE (passage obstrué par un mur amovible).

Les cases d’entrée (bleu) et de sortie (jaune) sont spécifiées par start et exit et ne correspondent pas à un état.

1.3 Voisinage d’une cellule

• Le champ final int[] dirs = { 1, -R, -1, R } encode les 4 directions sous forme de décalage d’indice:
  • +1 → bas (DOWN)
  • -R → gauche (LEFT)
  • -1 → haut (UP)
  • +R → droite (RIGHT)
• À partir d’une cellule d’indice p:
  • La case entre p et la cellule voisine dans la direction shift se trouve à l’indice w = p + shift. La valeur de cette case indique s’il y a un mur ou non. S’il y a un mur WALL (inamovible), on a atteint le bord du labyrinthe, il n’y a pas de cellule voisine au-delà.
  • Quand elle existe, la cellule voisine dans la même direction se trouve à l’indice q = p + 2*shift.

Pour itérer sur les voisins accessibles de la cellule à l’indice int cell, on peut donc écrire

for (int shift: dirs) {
  int passage = cell + shift;
  int next = cell + 2*shift; // indice de la cellule voisine
  if (grid[passage] == WALL || grid[passage]==REMOVABLE)
    continue; // Il y a un mur: on ne passe pas
  
  // ...
}

La condition sur grid[passage] peut bien sûr être adaptée selon la manière dont on veut traiter les murs amovibles.

1.4 Itération sur toutes les cellules

Les cellules sont les cases (i,j) avec i et j impairs. Donc on peut itérer sur toutes les cellules comme suit :

for (int i = 1; i < R; i += 2) {
  for (int j = 1; j < C; j += 2) {
    int cell = i + R*j;
    // ...
  }
}

1.5 Interface graphique

Les méthodes que vous developperez seront accessibles depuis l’interface MazeGUI.java.

• reset (Alt+R) réinitialise le labyrinthe
• generate (Alt+G) lance la génération (méthode sélectionnée)
• solve (Alt+S) lance la résolution
• pause/resume (Ctrl+Space)

La classe Maze fournit aussi toString(), ce qui permet d’afficher l’état du labyrinthe dans la console.

3.1 Génération par rebroussement récursif

Lors de la génération, on partira d’un labyrinthe dont toutes les cellules sont isolées, c’est-à-dire entourées de quatre murs, et leur marque est VOID. Les murs internes sont amovibles. La génération de labyrinthe consiste à supprimer des murs internes jusqu’à obtenir un labyrinthe parfait. On supprime le mur d’une cellule cell dans la direction shift avec grid[cell + shift] = VOID. On pourra marquer certaines cellules avec la marque neutre MARK:

• grid[cell] = MARK: marquer la cellule à l’indice cell
• grid[cell] == MARK: teste si une cellule est marquée.

Tout au long de la génération, on maintiendra les invariants suivants :

1. Les cellules non marquées sont isolées.
2. Toute cellule marquée est reliée à la cellule start par un chemin.

Et la suppression des murs est soumise à la règle :

3. Seul un mur entre une cellule marquée et une cellule non marquée peut être supprimé.

Pour ne pas toujours aboutir au même labyrinthe, on peut vouloir parcourir les voisins dans un ordre aléatoire. On peut, par exemple, procéder ainsi:

int[] random_dirs = dirs.clone();
shuffle(random_dirs);
for (int shift : random_dirs) {
  int next = cell + 2 * shift;
  //...
}

Testez votre code avec Test.java et MazeGUI.java.

3.2 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 un conteneur abstrait Bag<Integer> bag. Ce conteneur ne fournit que trois méthodes:

• boolean isEmpty()
• void push(Integer p): ajoute un élément
• Integer pop(): retire un élément et le renvoie

On impose la règle supplémentaire suivante:

4. Toute cellule marquée jouxtant une cellule non marquée est dans bag.

Testez votre code avec Test.java et MazeGUI.java. Dans l’interface graphique, un menu permet de sélectionner le comportement de bag.pop():

• stack correspond à une pile, dernier arrivé, premier sorti ;
• queue correspond à une file, premier arrivé, premier sorti ;
• avec random, pop retire un élément aléatoire ;
• avec max, pop retire le plus grand élément.

N’oubliez pas d’appeler step() à chaque itération.

3.3 Génération uniforme (algorithme de Wilson)

Nous venons d’implémenter des algorithmes de génération de labyrinthes aléatoires. La forme des labyrinthes 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 uniformément 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. Marquer la cellule start avec MARK.

2. Tant qu’il y a une cellule non marquée, choisir une cellule non marquée uniformément au hasard, et

   1. générer une marche aléatoire uniforme à partir de la cellule choisie jusqu’à ce qu’une cellule marquée soit rencontrée (on ignore les murs pour générer la marche), supprimer les boucles de la marche ;
   2. marquer toutes les cellules et supprimer tous les murs le long de la marche.

L’algorithme est beaucoup plus simple à implémenter qu’il n’y paraît ! Pour tirer des cellules uniformes aléatoires successivement, il suffit de mettre toutes les cellules dans un tableau et de le mélanger avec shuffle.

Pour effacer les boucles d’une marche aléatoire, il suffit d’enregistrer dans grid la direction prise par la marche à chaque étape. On utilise pour cela les marques directionnelles (RIGHT, UP, LEFT, DOWN) et on écrase les valeurs précédente. Ainsi, quand la marche est terminée, on la reprend depuis son point de départ et on suit les flèches. Elles amènent jusqu’à l’arrivée sans faire de boucles.

Pour transformer un décalage (1, -R, -1, R) en marque directionnelle (DOWN, LEFT, UP, RIGHT), on peut utiliser la méthode Maze.Cell markOfShift(int shift). Pour la transformation inverse, on peut utiliser int shiftOfMark(Maze.Cell mark).

Testez votre code avec Test.java et MazeGUI.java.