Génération et résolution de labyrinthes

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

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

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.