TP3 : génération de labyrinthes

Le but de ce TP est de comparer différentes manières de générer un labyrinthe intéressant sur une grille rectangulaire.

On peut, en première approximation, représenter un labyrinthe sur une telle grille par un arbre : une pièce est reliée à une pièce voisine (graphe non-orienté) s'il y a une ouverture entre les deux. Le fait de prendre un arbre permet de garantir les deux propriétés suivantes :

• connexité : toute la grille est accessible (il n'y a pas de partie qui ne sert à rien)

• acyclicité : il n'y a qu'un seul chemin pour aller d'un endroit à un autre

On pourrait considérer des labyrinthes plus généraux, mais cette restriction suffira pour le TP...

L'archive contenant les fichiers necessaires pour le TP se trouve ici : http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info505/tp.tgz .

Préliminaires

Les fichiers graphes.h et graphes.c (les mêmes que pour les TP précédents) contiennent les structures de base pour les graphes. Vous pourrez continuer à les utiliser...

Vous disposez en plus de deux fichiers labyrinthes.h et labyrinthes.h qui contiennent des définitions supplémentaires :

• définitions de constantes LARGEUR et HAUTEUR : c'est la taille de la grille

• un type de données Tile : un trucs entre les piles et les files. On peut insérer un élément en tête de structure et on peut récupérer soit le premier (comme dans une pile) soit le dernier (comme dans une file). On peut stocker des arcs (avec un but, une origine et un poids), mais on peut également s'en servir pour stocker juste une valeur entière. (C'est juste qu'on n'utilise pas tous les champs.)

• Le fichier labyrinthes.c contient, entre autre, la définition de la fonction grillePleine : cela permet d'initialiser le graphe qui contient des passages entre toutes les pièces. Le graphe est non-orienté avec des poids aléatoires. Toutes les listes d'adjacences sont triées par ordre de poids croissant.

Affichage

Écrivez la fonction de prototype void afficheGrille(GrapheListe) qui affiche un graphe sous forme de labyrinthe dans une grille.

Le graphe doit comporter exactement LARGEUR * HAUTEUR sommet, et ne doit avoir que des arêtes entre des sommets k et :

• k+1 (case à droite)
• k-1 (case à gauche)
• k+LARGEUR (case en bas)
• k-LARGEUR (case en haut)

(Modulo les bords de la grille bien entendu...)

Voici un exemple d'affichage pour un labyrinthe intéressant :

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|              |        |        |     |  |        |     |  |     |
+--+--+  +--+  +--+  +  +  +--+  +  +  +  +--+  +--+--+  +  +  +  +
|           |  |     |        |  |  |     |        |           |  |
+  +  +  +  +--+--+--+--+  +  +  +--+--+  +--+  +--+  +  +--+--+--+
|  |  |  |     |           |  |  |  |        |  |     |           |
+--+--+--+--+  +  +--+--+--+--+  +  +  +  +--+  +--+  +  +--+  +--+
|  |                    |     |        |  |           |  |        |
+  +--+  +  +--+--+--+--+  +  +--+--+  +  +--+--+  +--+--+  +--+  +
|        |     |           |  |        |  |        |     |     |  |
+  +--+--+--+  +  +--+  +  +--+--+  +--+  +--+  +  +--+  +  +  +  +
|  |     |     |  |     |     |  |  |           |     |  |  |  |  |
+  +  +--+--+  +  +  +  +  +--+  +  +  +--+  +  +--+  +  +--+  +--+
|  |              |  |  |     |     |  |     |     |  |           |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Note:

Pour ceux qui le souhaite, la fonction d'affichage est disponible dans le fichier affiche.c .

Génération de labyrinthes

Utilisation du parcours en largeur

Écrivez une fonction qui utilise un parcours en largeur pour calculer un arbre couvrant d'une grille pleine (et donc un labyrinthe). Pour faire ceci, vous pouvez soit utiliser la variante avec les tableaux, ou la variante avec la file en utilisant le type Tile.

Pour pouvoir afficher le labyrinthe directement, vous remplacerez le tableau pere par un GrapheListe vide, auquel vous rajouterez les arêtes parcourues.

Utilisation du parcours en profondeur

Écrivez une fonctions qui utilise le parcours en profondeur pour calculer un arbre couvrant d'une grille pleine.

Testez et comparez les labyrinthes obtenus par cette méthode et la méthode précédente.

Utilisation d'un arbre couvrant de poids minimal

Lors des des parcours précédents, l'aléatoire du labyrinthe venait du fait que l'ordre des sommets dans les listes d'adjacence était aléatoire.

Comme les grilles pleines contiennent des arcs de poids aléatoire, une autre manière d'obtenir un labyrinthe est de chercher un arbre couvrant de poids minimal.

Utilisez l'algorithme de Kruskal (ou de Prim, au choix) pour chercher un tel arbre couvrant, et affichez le.

Comparez les labyrinthes obtenus par les 3 méthodes...

Résolution de labyrinthes (BONUS)

Étant donné un sous graphe de la grille pleine, écrivez une procédure qui teste si l'on peut aller d'une case (a,b) vers une case (c,d). Si un tels chemin existe, affichez le labyrinthe avec une solution optimale.