Génération et résolution de labyrinthes
Aller à la navigation
Aller à la recherche
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