« Génération et résolution de labyrinthes » : différence entre les versions
Aller à la navigation
Aller à la recherche
| Ligne 17 : | Ligne 17 : | ||
<li>Construire un '''arbre couvrant''' A de ce graphe</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> |
<li>Dessiner le labyrinthe en traçant un mur entre les sommets directement liés dans G et non dans A</li> |
||
</ul> |
|||
===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=== |
|||
====Principe==== |
|||
On commence par explorer un nœud source, puis ses voisins, puis les voisins non explorés de ces voisins, etc |
|||
Version du 26 mai 2017 à 08:24
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
Principe
On commence par explorer un nœud source, puis ses voisins, puis les voisins non explorés de ces voisins, etc