Modélisation mathématique d'un labyrinthe
1830646
29622830
2008-05-16T10:29:39Z
Sherbrooke
18624
/* Labyrinthes parfaits et labyrinthes à îlots */ SYntaxe.
Une approche [[Mathématiques|mathématique]] permet la génération de '''[[labyrinthe]]s''' modernes. Les labyrinthes peuvent être modélisés dans un espace multi-dimensionnel, les plus courants étant les labyrinthes en deux dimensions. Concernant ces derniers, on quadrille le plus souvent l'espace en cellules carrées.
=== Labyrinthes parfaits et labyrinthes à îlots ===
Un labyrinthe est une surface [[Connexité (mathématiques)|connexe]]. De telles surfaces peuvent avoir des topologies différentes : simple, ou comportant des anneaux ou îlots :
{| align=center
| [[Image:yl maze.1.png|Une surface [[Connexité (mathématiques)|connexe]] simple]]
| [[Image:yl maze.2.png|Une surface [[Connexité (mathématiques)|connexe]] avec un îlot]]
|}
Ces deux surfaces ne sont topologiquement pas équivalentes. Cette différence, rapportée aux labyrinthes, conduit à une distinction en deux catégories :
* celle des labyrinthes dits « parfaits » où un chemin unique passe par toutes les cellules
* celle des labyrinthes dits « imparfaits » où un chemin se recoupant forme des ensembles de cloisons connexes appelés « îlots ». Ces îlots peuvent éventuellement isoler des cellules qui deviennent alors inaccessibles.
{| align=center
{| align=center
| [[Image:yl maze.3.png]]
| [[Image:yl maze.4.png]]
| [[Image:yl maze.5.png]]
|-----
| align=center | Labyrinthe « parfait »
| colspan=2 align=center | Labyrinthes « imparfaits »
|}
|}
=== Notion de chemin dans un labyrinthe ===
Les chemins des labyrinthes parfaits peuvent être représentés par des [[graphe]]s directs acycliques (ou DAG) :
{| align="center"
|-
|[[Image:yl maze.md.svg|thumb|300 px|Un labyrinthe parfait et son DAG associé (en rouge). Les noeuds sont marqués selon qu'il s'agit d'entrées ou de sorties, d'intersections ou de cul-de-sac.]]
|[[Image:Yl maze.td.svg|thumb|300 px|Vue du DAG déployée en arborescence ]]
|}
=== Sortir d'un labyrinthe ===
On sait, de façon pragmatique, que l'on trouve obligatoirement la sortie d'un labyrinthe si on longe systématiquement un mur en le gardant, sans jamais le lâcher, à main droite ou à main gauche. Cette idée est vérifiée dans le cas d'un labyrinthe parfait, mais elle peut conduire à explorer la totalité du labyrinthe, c'est-à-dire à passer au moins une fois dans toutes les cellules sans exception. Cela correspond à ce que l'on appelle le parcours de l'arbre en profondeur (voir [[lexique de la théorie des graphes]])
[[Image:Nested Labyrinth.svg|thumb|400px|right|Exemple de labyrinthe à îlots imbriqués avec son graphe abstrait associé]]
Cette ruse a toutefois été déjouée par les concepteurs de labyrinthes, car dans les labyrinthes à îlots, tourner systématiquement à droite, ou systématiquement à gauche, peut conduire à tourner systématiquement en rond. L'exemple ci-contre présente un labyrinthe à îlots imbriqués où la méthode de la main au mur est inopérante et où il faut passer à des méthodes plus évoluées.
La sortie d'un labyrinthe relève plus généralement de la [[Pathfinding|recherche de chemin]] dans le [[Graphe (théorie des graphes)|graphe]] du labyrinthe. On distingue deux cas.
Dans le premier cas, on dispose d'une ''vue globale'' et on est capable de distinguer sans ambiguïté deux positions. De plus, on sait localiser la sortie. On peut alors utiliser toute ces connaissances pour mesurer une [[Distance (mathématiques)|distance]] (par exemple de Manhattan) par rapport à la sortie et déterminer le chemin pour l'atteindre.
Le second cas est celui de la ''vue locale'', celle qu'aurait la personne qui serait placée dans le labyrinthe (toute autre perception que les murs avoisinants étant négligée). Cette personne ne dispose alors plus de moyen de distinguer un couloir ou un carrefour d'un autre. Dans ce cas, la sortie d'un labyrinthe ne relève guère plus de la chance pure, à moins d'exploiter une [[Mémoire (psychologie)|mémoire]] quelconque. L'explorateur peut utiliser ses propres ressources, en retenant les endroits déjà visités, les décisions prises et en dressant une carte au fur et à mesure. Il peut aussi marquer l'environnement en notant par exemple les directions déjà explorées aux carrefours. Le fameux ''Fil d'Ariane'' est lui-même la trace concrète que [[Thésée]] laisse derrière lui au fur et à mesure qu'il s'enfonce dans l'antre du [[Minotaure]].
Algorithme de Trémaux
=== Générer un labyrinthe ===
Les algorithmes proposés ici vont s'intéresser aux labyrinthes parfaits, mais quelques adaptations permettent de créer facilement des labyrinthes à îlots. Ils sont basés sur l'espace discrétisé dont les cellules carrées sont initialement remplies et séparées par des cloisons, selon les quatre directions (nord, sud, est et ouest).
[[Image:yl maze.cell.png|center|Cloisons d'une cellule]]
Un labyrinthe rectangulaire parfait de <math>m</math> colonnes par <math>n</math> lignes est un ensemble de <math>mn</math> cellules reliées les unes aux autres par un chemin unique. L'équivalence [[Espace topologique|topologique]] des surfaces [[Connexité (mathématiques)|connexes]] simples va nous servir pour affiner notre vision des labyrinthes parfaits :
[[Image:yl maze.eqv.png|center|thumb|300 px|Ces deux surfaces connexes sont équivalentes : chacune a 11 celules et 10 murs internes (marqués en pointillés)]]
Le nombre de murs ouverts pour permettre un chemin unique dans un labyrinthe de <math>mn</math> cellules est identique au nombre de murs ouverts pour un chemin droit de <math>mn</math> cellules, soit <math>mn - 1</math> murs.
Dans un rectangle <math>m \times n</math> cellules, le nombre total de murs internes possible est : <math>2mn - m - n</math>. Pour obtenir ce résultat, on compte deux murs par cellule, par exemple celui du bas et celui de droite (on évite ainsi de recompter deux fois les mêmes) et on retire le nombre de murs limitant le rectangle en bas <math>m</math> et à droite <math>n</math>.
[[Image:yl maze.walls.png|thumb|center|300 px|Murs internes]]
Le nombre de murs fermés dans un labyrinthe parfait est donc : <math>2mn - m - n - (mn - 1) = (m - 1) (n - 1)</math>
==== Algorithmes ====
Il existe de nombreux algorithmes. Voici deux d'entre eux assez simples.
===== Fusion aléatoire de chemins =====
[[Image:yl maze ani algo1.gif|right]]
Cet algorithme, utilise une propriété des labyrinthes parfaits précédemment énoncée tel quel : ''Chaque cellule est reliée à toutes les autres, et ce, de manière unique''. Il fonctionne en fusionnant progressivement des chemins depuis la simple cellule jusqu'à l'obtention d'un chemin unique, il suit donc une [[Technologie bottom-up|approche ascendante]].
L'algorithme associe une valeur unique à chaque cellule (leur numéro de séquence, par exemple) et part d'un labyrinthe où tous murs sont fermés.
A chaque itération, on choisit un mur à ouvrir de manière aléatoire.
Lorsqu'un mur est ouvert entre deux cellules adjacentes, les deux cellules sont liées entre elles et forment un chemin. L'identifiant de la première cellule est recopié dans la seconde.
À chaque fois que l'on tente d'ouvrir un mur entre deux cellules, on vérifie que ces cellules ont des identifiants différents.
Si les identifiants sont identiques, c'est que les deux cellules sont déjà reliées et appartiennent donc au même chemin. On ne peut donc pas ouvrir le mur.
Si les identifiants sont différents, le mur est ouvert, et l'identifiant de la première cellule est affecté à toutes les cellules du second chemin.
Au final, on obtient un chemin unique lorsque le nombre de murs ouverts atteint <math>mn-1</math>, ce qui donne 19 étapes dans l'exemple ci-contre.
===== Exploration exhaustive =====
[[Image:yl maze ani algo2.gif|right]]
On part d'un labyrinthe où tous les murs sont fermés. Chaque cellule contient une variable booléenne qui indique si la cellule a déjà été visitée ou non (i.e. les cellules visitées sont celles qui appartiennent au chemin du labyrinthe en cours de construction).
Au départ, toutes les cellules sont marquées comme non visitées (''faux'').
On choisit arbitrairement une cellule et on la marque comme visitée (''vrai'').
Puis on regarde quelles sont les cellules voisines possibles et non visitées et on stocke la position en cours.
S'il y a au moins une possibilité, on en choisit une au hasard, on ouvre le mur et on recommence avec la nouvelle cellule.
S'il n'y en pas, on revient à la case précédente et on recommence.
Lorsque l'on est revenu à la case de départ et qu'il n'y a plus de possibilités, le labyrinthe est terminé.
L'historique des emplacements des cellules précédentes peut être géré de deux façons équivalentes :
* par la sauvegarde dans un tableau de <math>mn - 1</math>
* par la sauvegarde dans la pile, en utilisant la récursivité
La formulation récursive donne de très bon résultats pour des labyrinthes de taille modeste. Dès lors que l'on veut générer de grands labyrinthes (1000 x 1000, par exemple), le programme risque de se terminer brutalement si la taille de la pile est insuffisante. Il est donc important de prévoir une taille de pile suffisante ou à défaut de passer à une autre solution comme l'historique à base de tableau.
L'exploration exhaustive est moins complexe que la fusion de chemins car elle ne nécessite pas la mise en œuvre de structures complexes.
==== Discussion ====
Les deux types d'algorithmes ne sont pas tout à fait équivalents d'un point de vue qualitatif.
Le premier type fournit un labyrinthe dont l'arbre est statistiquement mieux équilibré (ou balancé) que celui généré par le second.
En effet, tous les murs ouvrables ont statistiquement approximativement autant de chances d'être ouverts.
Le premier algorithme favorisera l'apparition des bifurcations.
A contrario, le second privilégie les chemins. Les arbres seront donc assez fortement déséquilibrés. Plus un chemin est généré tôt, et plus il a de chances d'être long. Plus il est généré tardivement et plus il a de chances d'être court.
Le labyrinthe final sera composé de quelques chemins assez longs avec peu de ramifications et les ramifications auront une taille moyenne très inférieure au chemin sur laquelle il se greffe.
Pour des labyrinthes de petite taille, les deux algorithmes donneront des résultats comparables. En revanche, les grands labyrinthes auront des apparences dissemblables.
D'un point de vue quantitatif, le second type d'algorithme sera en moyenne plus rapide que le premier. Une fois encore, sur de petites surfaces, les temps seront comparables. Mais sur de grandes surface, le second se montrera plus performant.
Du point de vue de la mise en œuvre, les deux algorithmes présentés sont [[Probabilités|probabilistes]] et à horizon fini, car le nombre de murs à enlever aléatoirement est connu. En revanche, alors que le premier nécessite une gestion lourde de l'ensemble des murs à considérer, le second est plus simple par sa gestion de l'historique des cellules visitées. Il s'impose naturellement comme le meilleur choix possible.
=== Liens externes ===
* Source technique : [http://www.ilay.org/yann/articles/maze/ Yann Langlais] Algorithmique pratique et optimisation de code : La génération de labyrinthes
{{Portail ludopédia}}
[[Catégorie:Casse-tête]]
[[Catégorie:Théorie des graphes]]