« Génération et résolution de labyrinthes II » : différence entre les versions
| Ligne 147 : | Ligne 147 : | ||
== Sources == |
== Sources == |
||
Génération |
|||
[http://www.lama.univ-savoie.fr/mediawiki/index.php/INFO805_:_Introduction_%C3%A0_l%27Informatique_Graphique Diapo INFO805] |
|||
<ul> |
|||
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Fusion_al%C3%A9atoire_de_chemins Kruskal (fr)] </li> |
|||
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal's_algorithm Kruskal (en)] </li> |
|||
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#Exploration_exhaustive Parcours en profondeur (fr)] </li> |
|||
<li> [https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Depth-First_Search Parcours en profondeur (en)] </li> |
|||
| ⚫ | |||
Résolution |
|||
<span style="display:screen" onmouseover="> eee </span> |
|||
<ul> |
|||
<li> [https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_de_labyrinthe#R%C3%A9solution Résolution générale (fr)] </li> |
|||
<li> [https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower Mur droit (en)] </li> |
|||
| ⚫ | |||
Structures de données |
|||
<div class="pdf-icon-box" style="position:relative;" onmouseover="this.getElementsByClassName('name')[0].style.backgroundColor = 'yellow'"; onmouseout="this.getElementsByClassName('name')[0].style.backgroundColor = 'green'"; > |
|||
<ul> |
|||
<span class="pdf-style"> |
|||
<li> [https://fr.wikipedia.org/wiki/Union-find Union-Find / Disjoint-Set (fr)] </li> |
|||
<span class="name" style="display:inline-block;background-color:orange;"> T E S T </span> |
|||
<li> [https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Pile / Stack (en)] </li> |
|||
| ⚫ | |||
<li> [https://en.wikipedia.org/wiki/Queue_(abstract_data_type) File / Queue (en)] </li> |
|||
| ⚫ | |||
</ul> |
|||
Version du 17 mai 2019 à 10:18
Lorem ipsum
Représentation
Propriétés
Un labyrinthe est une grille de cellules reliées, ou non, entre elles.
Deux cellules sont reliées entre elles par une porte, ou séparées par un mur.
Tout labyrinthe a une entrée et une sortie, et quelle que soit l'entrée ou la sortie, le chemin entre ces deux cellules est unique.
Modélisation en graphe
En théorie des graphes, un graphe est un ensemble de points (ou nœuds ou sommets) reliés ensemble par des lignes (ou liens ou arêtes).
Un graphe peut être connexe (en un seul morceau) ou non connexe (en plusieurs morceaux).
Un graphe peut aussi être cyclique si les points sont reliés en formant une boucle ou acyclique.
Enfin, un graphe peut être orienté (si les arêtes sont à sens unique) ou non orienté.
Un arbre est un graphe connexe, acyclique et non orienté.
En plaçant un point sur chaque cellule de notre labyrinthe, et en reliant deux cellules séparées par une porte, on peut dessiner un arbre à partir de n'importe quel labyrinthe.
Génération
Un labyrinthe rectangulaire de largeur et de hauteur contient exactement portes.
Du point de vue du graphe, il y a donc arêtes.
Maintenant, comment répartir toutes ces portes de façon à ce que toutes les cellules soient accessibles et qu'il n'existe qu'un unique chemin entre l'entrée et la sortie ?
De nombreux algorithmes existent, dont le parcours en profondeur et l'algorithme de Kruskal. Chaque algorithme est différent et produit des labyrinthes visuellement différents.
Parcours en profondeur
Dans l'algorithme du parcours en profondeur ("recursive backtracker" en anglais), on commence sur une cellule aléatoire dans le labyrinthe.
On se dirige dans une direction aléatoire et on casse le mur en face, tout en marquant la cellule précédente comme visitée.
Lorsque aucune direction n'est disponible, on remonte à la position précédente.
Pour sauvegarder l'historique des positions, on peut utiliser une pile.
Une pile est une liste dans laquelle seul le dernier élément peut être récupéré.
Une pile contient 2 méthodes :
- push(elem) : ajoute elem à la pile
- pop() -> elem : retourne le dernier élément de la pile (elem dans notre cas)
Dans mon implémentation de la pile, une erreur est levée si l'on appelle la méthode pop sur une pile vide.
Kruskal
Alors que pour le parcours en profondeur on partait des cellules, l'algorithme de Kruskal s'applique sur des murs.
On attribue à chaque cellule un identifiant unique.
On choisit
Labyrinthes cycliques
Il est possible, en retirant un certain pourcentage de murs, de créer des labyrinthes cycliques à partir des labyrinthes acycliques générés auparavant.
Cependant, certains algorithmes de résolution n'auront pas le même comportement.
Résolution
?
Exploration exhaustive
Mur droit
Affichage
tkinter
Code
N'ayant pas utilisé de bibliothèques autres que tkinter, mon projet total contient plusieurs milliers de lignes réparties dans une dizaine de fichiers.
Je ne peux donc évidemment pas l'insérer directement dans cette page.
Le code source est disponible sur Github à cette adresse
Sources
Génération
Résolution
Structures de données