« Génération et résolution de labyrinthes » : différence entre les versions
Aller à la navigation
Aller à la recherche
| Ligne 7 : | Ligne 7 : | ||
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. |
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 : |
|||
<ul> |
|||
<li>Générer un graphe G représentant une grille de taille m*n</li> |
|||
<li>Construire un '''arbre couvrant''' A de ce graphe</li> |
|||
<li>Dessiner le labyrinthe en traçant un mur entre les sommets directement liés dans G et non dans A</li> |
|||
Version du 26 mai 2017 à 08:20
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