Génération et résolution de labyrinthes II

Fichier:???.png

???

bla bla blabla dsdsds

• VISI201 Analyse syntaxique (Tristan Porteries, 2018)

Définition

Propriétés d'un labyrinthe

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é.

Exemple de graphe connexe cyclique non orienté

Un arbre est un graphe connexe, acyclique et non orienté.

Exemple d'arbre

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 comme ceci :

Exemple de labyrinthe avec son arbre. Pour plus de simplicité, on attribue à chaque nœud une position.

Génération

Un labyrinthe rectangulaire de largeur L et de hauteur H contient exactement L*H-1 portes.

Du point de vue du graphe, il y a donc L*H-1 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. Lorsqu'aucun

Kruskal

Kruskal

Prim

?

Résolution

?

Structures de données

Union-Find

Dijoint Set

Pile

Stack

File

Queue

Affichage

tkinter

tkinter

Code

Le code source est disponible à l'adresse Github suivante : https://github.com/Rominos111/Labyrinthe_VISI201