Création et résolution de labyrinthes

Références :
Wikipedia pour l'algorithme d'exploration exhaustive
"Mazes for Programmers" de Jamis Buck, qui traite de différents problèmes liés aux labyrinthes, et propose des implémentations en Ruby.

1°) Introduction

1_1 Présentation

L'objectif de cette SAE est de voir différents algorithmes permettant de construire des labyrinthes, puis de les résoudre.

Nous nous restreindrons à des labyrinthes dits parfaits, c'est à dire des labyrinthes où chaque cellule peut joindre une autre par un chemin unique.
A l'inverse, les labyrinthes pouvant contenir des ilôts, des boucles ou des cellules inaccessibles sont dits imparfaits, et ne seront pas étudiés dans ce projet.

Exemple de labyrinthe parfait : labyrinthe parfait

Exemple de labyrinthe imparfait : labyrinthe imparfait

Remarque :Un labyrinthe parfait peut être vu comme un arbre, où chaque sommet est une cellule (= une "case") du labyrinthe.

Le labyrinthe parfait ci-dessus donne l'arbre : labyrintheArbre

Il y a donc un lien très fort entre labyrinthe parfait et théorie des arbres, et nous allons voir que les algorithmes utilisés dans cette SAE sont proches de ceux vus en TP de graphes.

1_2 Grille

Avant de construire un labyrinthe, nous allons commencer par construire une grille.
Nous avons pour cela défini plusieurs classes :

1_3 Utilisation des classes

Afin de mieux comprendre les classes ci-dessus, voyons quelques exemples.

1_4 Premier exercice

Reprenons la grille grilleTest précédente, et commençons par détruire quelques murs.

On remarque que le mur Est de la cellule (2,3) est bien détruit. Mais pour autant ... le mur Ouest de la cellule (2,4) est encore intact !!

Pourtant, en terme de représentation du labyrinthe, le mur Est de (2,3) est bien le même mur que le mur Ouest de (2,4)!

Plus problèmatique, encore : reconstruisons le mur Est de (2,3), détruisons le mur Ouest de (2,4), et visualisons le résultat :

Le mur Ouest de (2,4) est bien détruit, et pourtant cela n'apparaît pas dans la visualisation de la grille.

Cela est du à la façon de construire la représentation de la grille. Par commodité, seuls les murs Est et Sud d'une cellule sont traçés. Cela permet de ne pas afficher de 'doubles murs', mais en contrepartie le lien qui existe entre deux cellules de part et d'autres d'un même mur est perdu.

Nous aurons le même problème avec par exemple le mur Nord de (2,3) et le mur Sud de (1,3).

Exception : pour les cellules touchant le bord gauche de la grille, ou le bord du haut, les 4 murs sont bien représentés, pas seulement les murs Est et Sud.

Exercice :

Afin de palier au problème évoqué plus haut, créer une fonction effaceMur(grille, coord, orientation) qui pour une grille grille :

Remarque
On fera attention aux cellules situées au bord de la grille, qui n'auront pas forcément de cellules voisines.

Exemple :

2°) Construction de labyrinthes parfaits

Nous allons voir dans cette partie plusieurs algorithmes permettant de créer des labyrinthes parfaits. Nous ne nous occuperons pas de placer les entrées et sorties du labyrinthes, qui n'influent pas sur la construction.

Ainsi, les murs extérieurs de la grille ne seront jamais détruits.

2_1 Algorithme de l'arbre binaire

Nous allons construire notre premier labyrinthe, à l'aide d'un algorithme très simple. En voici sa description :

Exercice :

Construire une fonction arbreBinaire(grille) qui retourne un labyrinthe créé par l'algorithme précédent.

Exemple :

Essayez de construire plusieurs labyrinthes à l'aide de cette méthode. Qu'ont en commun tous ces labyrinthes ?

2_2 Algorithme sidewinder

Cet algorithme simple est très similaire à l'algorithme précédent. Le labyrinthe est généré une ligne à la fois : pour chaque cellule de cette ligne, on décide aléatoirement s'il faut détruire le mur Est ou pas.

Exemple :
Commençons par la ligne du haut. Imaginons que le sort décide de ne pas détruire le mur Est de (0,0). On choisit donc aléatoirement parmi les cellules du passage et on détruit le mur Sud de la cellule choisie. Comme pour l'instant il n'y a que (0,0) dans le passage, on détruit son mur Sud.

Imaginons maintenant que le sort ait décidé qu'aux étapes 2 et 3, les murs Est de (0,1) et de (0,2) soient détruits.
On se retrouve alors dans cette situation à la fin de l'étape 3 :

A l'étape 4, le sort décide de ne pas détruire le mur Est de (0,3). Ce passage horizontal est terminé. On choisit aléaoirement parmi les cellules du passage, à savoir (0,1), (0,2) et (0,3) laquelle vera son mur Sud détruit.

Remarque : la cellule (0,0) ne fait pas partie du même passage horizontal !

Imaginons que c'est la cellule (0,2) qui perd son mur Sud. On se retrouve ainsi à la fin de l'étape 4 :

On commence donc un nouveau passage horizontal à l'étape 5, et le traitement de la cellule (0,4). Imaginons que son mur Est soit détruit.
On traite alors à l'étape 6 la cellule (0,5), et comme elle est en bout de grille son mur Est ne peut pas être détruit. On choisit donc un mur Sud à abattre, parmi les cellules du passage horizontal actuel, à savoir (0,4) et (0,5) ... Le hasard décidant de détruire le mur Sud de (0,4), voici la situation à la fin du traitement de la première ligne :

Et ainsi de suite, on traite une par une chaque ligne. A savoir que pour les cellules de la dernière ligne, on détruira forcément les murs Est (histoire de ne pas sortir de la grille), et on ne détruira aucun mur de la dernière cellule située en bas à droite.

Exercice :

Construire une fonction sidewinder(grille) qui réalise l'algorithme précédent.

Exemple :

Essayez de construire plusieurs labyrinthes à l'aide de cette méthode. Qu'ont en commun tous ces labyrinthes ?

2_3 Algorithme d'exploration exhaustive

Cet algorithme s'apparente au parcours en profondeur d'arbre vu en cours. Voici la description de cet algorithme sur wikipedia:

Exploration Exhaustive

L'utilisation de la récursivité n'étant pas au programme, nous allons comme en TP de graphes utiliser une Pile.

Voila la description de l'algorithme :

definition de explorationE(grille)

Visite = tableau 2D (ou matrice ...) de même taille que la grille.
Ce tableau nous servira à savoir si une cellule a déja été traitée ou non

Pile = une liste, vide pour l'instant

On choisit aléatoirement une cellule, sous forme d'un couple (ligne, colonne)
On la met dans Pile, et on indique dans le tableau Visite que cette cellule a été traitée.

tant que Pile non vide
  soit (i,j) le premier élément de Pile
  on recherche les voisins non encore traités de (i,j)

  si il y en a
      soit (k,l) = un de ces voisins, choisi au hasard 
      on détruit le mur entre (k,l) et la cellule (i,j)
      on indique dans Visite que (k,l) a été traitée
      on ajoute (k,l) au début de Pile
  sinon
      on retire le premier élément de Pile

retourner grille

Exercice :

Construire une fonction explorationE(grille) qui réalise l'algorithme précédent.

Exemple :

2_4 Bonus

L'article wikipedia propose une autre façon de créer un labyrinthe parfait :

La fusion aléatoire des chemins

Proposer une fonction fusion(grille) qui construit un labyrinthe parfait sur ce principe.

3°) Résolution d'un labyrinthe parfait

3_1 Introduction

Nous allons proposer maintenant une résolution de labyrinthe, reposant sur un parcours en largeur du labyrinthe.

Pour cela, nous ferons la convention que l'entrée du labyrinthe est la cellule en haut à gauche et que la sortie est la cellule située en bas à droite.

Nous dirons que deux cellules sont attenantes ssi il n'y a pas de murs entre elles.

Exercice :

Construire une fonction attenantes(labyrinthe,coord) qui retourne les cellules attenantes à la cellule de position coord.

Exemple :

3_2 Calcul des distances depuis (0,0)

L'objectif de cette partie est d'obtenir un tableau (ou une matrice ...) notée D, où :
D[i,j] = nombre de cases nécéssaires pour se rendre de la case (0,0) à la case (i,j).

Par exemple, voici la matrice D correspondant au labyrinthe laby précédent :

Nous allons cette fois utiliser une File. Voici la description de l'algorithme :

definition de distance(labyrinthe)

D = tableau 2D (ou matrice ...) de même taille que la grille.
Ce tableau contiendra les distances depuis (0,0), et peut être initialisé à l'infini

File = une liste, vide pour l'instant

Initialisation :
D[0,0] = 0
On met (0,0) dans File

tant que File non vide
  soit (i,j) le premier élément de File
  on recherche les cellules attenantes à (i,j) non encore traitées 
  on met ces cellules à la fin de File
  ces cellules reçoivent dans D la valeur D[i,j]+1
  on retire le premier élément de File

retourner D

Exercice :

Construire une fonction distance(labyrinthe) qui retourne la matrice D pour un labyrinthe donné.

3_3 Résolution

Pour trouver la solution au labyrinthe, il "suffit" de partir de la cellule en bas à droite, et de remonter le chemin dans D en suivant l'ordre décroissant.

Exercice :

Construire une fonction resolution(labyrinthe) qui retourne le chemin permettant de résoudre le labyrinthe.

Exemple :

3_4 BONUS

La résolution précédente repose sur le fait que l'on connaisse la structure globale du labyrinthe.

Prenons désormais un point de vue local : une personne est placée à l'entrée du labyrinthe, et ne sait rien de sa structure. Elle est incapable de faire la différence entre deux positions dans le labyrinthe.
Un moyen bien connu pour trouver la sortie est la méthode de la main droite, qui consiste à longer systématiquement le mur de droite, sans le lacher.

Efficace, cette méthode peut néanmoins aboutir à explorer une grande partie du labyrinthe, et même la totalité dans le pire des cas.

Exercice :

Construire une fonction parcoursMD(labyrinthe), qui retourne le chemin emprunté pour sortir du labyrinthe en utilisant la méthode de la main droite.

Remarque : La personne dans le labyrinthe reconnaît la sortie quand elle l'atteint. Pour simuler ceci et simplifier un peu le problème, nous pouvons considérer qu'il est connu que le départ est en haut à gauche et la sortie en bas à droite. La taille de la grille est aussi connue.

Exemple :