Génération et résolution de labyrinthes

• 2016-2017
• Tuteur : Xavier PROVENCAL
• Etudiant : Candice ROBERT

Les programmes sont réalisés avec sage

Approche mathématique des labyrinthes

Un labyrinthe est dit parfait si chaque cellule est reliée à toutes les autres, et ce d’une seule manière. Les labyrinthes imparfaits peuvent donc contenir des boucles, des îlots ou des cellules inaccessibles

Nous nous intéresserons aux labyrinthes parfaits. On peut modéliser leurs chemins par des graphes. Pour résumer, un graphe est un ensemble de sommets reliés par des arrêtes.

---

Génération de labyrinthes

La création d'un labyrinthe suit les étapes suivantes :

• Générer un graphe G représentant une grille de taille m*n
• Construire un arbre couvrant A de ce graphe
• Dessiner le labyrinthe en traçant un mur entre les sommets directement liés dans G et non dans A

Qu'est ce qu'un arbre couvrant ?

Un arbre est un graphe à la fois connexe et sans cycle. Un arbre couvrant d'un graphe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe.

Algorithmes de construction de l'arbre couvrant

Parcours en largeur du graphe

On commence par explorer un nœud source, puis ses voisins, puis les voisins non explorés de ces voisins, etc

Voici la fonction qui réalise cet algorithme :

def parcoursLargeur(G):
    vu = set()
    L = deque() # insérer : L.append( ), retirer : L.popleft()
    A = Graph() # le graphe de notre labyrinthe
    A.add_vertices( G.vertices() )
    A.set_pos( G.get_pos() ) # juste pour l'affichage

    s = (0,0)
    vu.add(s)
    L.append(s)

    while len(L)>0:
        u = L.popleft()
        for v in G.neighbors(u):
            if v not in vu:
                A.add_edge(u, v)
                L.append(v)
                vu.add(v)
    return A

Et un résultat obtenu à partir de cette fonction :

Bien qu'il soit complètement régulier, il s'agit bien d'un labyrinthe parfait. Nous l'améliorerons plus tard.

Parcours en profondeur du graphe

Pour chaque sommet, on marque le sommet actuel, et on prend le premier voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous les voisins soient marqués), et on revient alors au sommet père. C'est un algorithme récursif, c'est à dire qu'il fait appel à lui même.

Voici le programme :

def parcoursProfondeur(G) :
    vu = set()
    A = Graph()
    s = (0,0)
    parcoursProfondeurRec(G,s,A,vu)

def parcoursProfondeurRec(G,u,A,vu):
    vu.add(u)
    for v in G.neighbors(u):
        if v not in vu:
            A.add_edge(u, v)
            vu.add(v)
            parcoursProfondeurRec(G,u,A,vu) #Ici le programme fait appel à lui même

Arbre couvrant minimum

On attribue (idéalement de manière aléatoire), des poids à chacune des arrêtes du graphe de départ. L'arbre couvrant minimum est l'arbre couvrant dont la somme des poids est minimale. Cela fonctionne également avec l'arbre couvrant maximal. L'aspect aléatoire donne un avantage sur les autres méthodes, puisque cela permet de construire un labyrinthe beaucoup plus équilibré.

Algorithme de Prim

On part d’un sommet du graphe. À chaque répétition, on ajoute à l'arbre le sommet libre accessible de poids minimal. On s'arrête quand l'arbre est recouvrant.

Initialiser A un graphe vide (arbre couvrant)
Initialiser vu un ensemble vide
Initialiser un dictionnaire poids
Initialiser un dictionnaire père
Pour chaque sommet u de G faire
   poids[u]= oo
   pere[u] = None
Choisir un sommet s du Graphe G
poids[s] = 0
Tant qu'il reste des sommets non-vus faire
   u = un somment non-vu de G ayant un poids minimum
   Ajouter l'arête (u,pere[u]) à A
   Ajouter u à vu
   Pour chaque sommet non-vu v voisin de u dans G faire
      Si le poids de (u,v) est < à poids[v] faire
         pere[v] = u 
         poids[v] = poids de (u,v)

---

Sortie d'un labyrinthe

Il est assez connu qu'en longeant les murs d'un labyrinthes, on parvient à en sortir. Il faut pour cela que ce labyrinthe soit parfait. On peut parcourir le labyrinthe avec l'algorithme de parcours en profondeur vu précédemment. Cela revient à avancer tant qu'on le peut, et à retourner en arrière lorsqu'on est dans une impasse. Cette méthode n'est pas la plus courte. Le chemin le plus court peut être déterminé avec une file de priorité, par exemple avec l'algorithme de parcours en largeur.

---

Sources

• [1]
• [2]
• [3]
• [4]
• [5]