Nous allons explorer différentes stratégies et algorithmes pour générer des labyrinthes aléatoires, nous apprendrons leurs avantages, inconvénients et comment analyser leur topologie.

Pour chacun d'entre eux, nous avons la possibilité de jouer avec des visualisations interactives en ligne, consulter des descriptions copieusement illustrées et télécharger le code source utilisé.

Pour s'amuser.
Pour profiter des animations de nos propres constructions.
Pour explorer.

Quoi d'autre?

Nous allons apprendre à coder et à générer des labyrinthes étape par étape. Nous allons également pratiquer des concepts de programmation tels que: listes d'adjacence (Adjacency list), efficacité de la mémoire, parcours de graphes récursivité, arbre couvrant (spanning tree), rapidité d'execution.

Et ensuite?

Maintenant que nous gérons la création de labyrinthes, essayons de les résoudre avec nos algorithmes de recherche de chemins ou nous pouvons aussi apprendrer à créer nos fractales.

La première chose à faire quand on étudie un algorithme est de comprendre les données.
Quelle est l'entrée ? Quelle est la sortie ?
Voici le genre de structure que nous allons créer.

Comment sont structurées les données?
Voici un labyrinthe avec un peu plus de détails.

Dans cette grille, chaque case représente un noeud. Une connection entre deux noeuds est représentée, elle, par un chemin entre deux cases. Ces informations sont aussi affichées textuellement (encadré haut gauche dans l'image). Ici, notre souris est sur le premier noeud (x:0, y:0) et affiche des connexions avec les noeuds (x:0, y:1) et (x:1, y:0).

Nous avons choisi de décrire notre grille (ou graphe) à l'aide d'une structure de données en liste d'adjacence (adjacency lists). L'idée est plutôt simple : un tableau de noeuds avec chaque noeud stockant la liste de leurs voisins connectés. Facile à créer, facile à manipuler, voici comment les données pourraient être représentées en JSON:

[
  {
    "x":0, "y":0,
    "neighbors":[1,5]
  }, {
    "x":0, "y":1,
    "neighbors":[0,2]
  }, {
    "x":0, "y":2,
    "neighbors":[1,3,7]
  }
  ...
] 

L'identifiant de noeud est donné par son index de tableau, cet identifiant est utilisé pour faire référence aux voisins.
Oui, c’est aussi simple que cela ! Cela contient toutes les informations nécessaires pour construire et visualiser nos labyrinthes.

Parfait, nous savons tout ce qu'il faut pour construire nos générateurs!

Remarque: Ici, les grilles (nos labyrinthes orthogonaux) sont utilisées car elles sont plus faciles à comprendre, à travailler et à visualiser; cependant le principe reste exactement le même que pour des formes plus complexes.

“Your mind is a walled garden. Even death cannot touch the flowers blooming there.”
“Votre esprit est un jardin clos. Même la mort ne peut toucher les fleurs qui y fleurissent.”*
(Ford - Westworld)

Depuis des milliers d'années, les labyrinthes fascinent les humains : ils les ont construits, ont raconté des histoires à leur sujet, ont créé des jeux et des énigmes autour d'eux et ont même étudié les comportements des animaux en leur sein.

Veuillez notez que deux types de labyrinthes existent et n'ont pas la même signification ni le meme usage. L'un est composé d'astuces, d'impasses et l'objectif est souvent d'en trouver la sortie. L'autre est formé d'un unique chemin (les labyrinthes sont dits unicursaux) et est le plus souvent utilisé pour la relaxation, la méditation ou la spiritualité.

Itoi Labyrinthe - Man in the maze (décrit plus bas dans la section spirituelle)

Jeu de sociéte Labyrinthe

Les classiques labyrinthes au dos des paquets de céréales

Labyrinthe de glace géant, connu comme étant le plus grand du monde en 2006. Il se trouvait à la station balnéaire de Zakopane en Pologne.

Vous trouverez une tonne de films et séries abordants ou incluant des labyrinthes

Labyrinthe de la vie et de l'incertitude qui prévaut

Selon la mythologie grecque, le labyrinthe originel aurait été construit par l'architecte Dédale et son fils Icarusto pour enclore le Minotaure : une créature avec le corps d'un homme et la tête d'un taureau. La légende raconte en outre que Dédale avait si habilement fait le labyrinthe, qu'il put à peine y échapper après sa construction.

Des labyrinthes mythologiques de la Grèce antique à ceux dans les champs / la glace / les parcs du 21ème siècle, voici 3 des principales raisons pour lesquelles nous pensons que les labyrinthes sont si attrayants.

Divertissant

Les labyrinthes sont à la fois déroutants et réconfortants : nous sommes perdus mais cherchons une sortie que nous savons existante. Cela les rend très amusants et addictifs.

Dès le 16ème siècle, les labyrinthes étaient destinés à divertir, mais aussi à fournir des endroits hors des sentiers battus pour des réunions secrètes. De nos jours, vous les trouverez partout et dans moultes formes : sur presque toutes les boîtes de céréales, dans les parcs d'attractions (Alice au pays des merveilles, labyrinthe de miroirs à la foire...), dans les jeux de société (e.g. le jeu s'appellant littéralement "Labyrinthe"), dans les jeux vidéo (presque tous), dans les films (e.g. le film s'appellant littéralement "Labyrinthe") etc.

Educatif

Les enfants semblent avoir un lien naturel presque immédiat et profond avec les labyrinthes. Ils vont relever le défi de presque tous les labyrinthes autommatiquement. Les labyrinthes offrent l'expérience de la résolution de problèmes tout en restant un jeu. Au lieu de créer des sentiments d'infériorité ou de gêne qu'un problème classique peut générer, les labyrinthes aident quiconque à se calmer, à effectuer des transitions et à se concentrer.

Les labyrinthes aident particulièrement les enfants à développer des compétences telles que:
- Planifier et réflechir à différentes stratégies.
- Obtenir une représentation spatiale et développer une orientation.
- Analyser un l’environnement complexe et mémoriser des chemins possibles.
- Se détendre.

Spirituel

Il y a de l'amour dans le labyrinthe
Il y a de la noirceur dans le labyrinthe
La sortie pourrait ne pas être là où vous l'imaginez

Nous sommes tous sur un chemin. Le labyrinthe est une métaphore du voyage de la vie; un symbole créant un espace et un lieu sacré nous tirant de notre ego vers notre 'sois' intérieur. Les labyrinthes antiques ont été conçus pour être sereins et introspectifs. Dans certains pays, les jeunes hommes traversaient un labyrinthe dans le cadre de leur initiation à l'âge adulte.

Les labyrinthes unicursaux, tels que «l'Itoi» («L'homme dans le labyrinthe») vu précédemment, peuvent représenter les cycles de la vie, le mouvement éternel, et les choix auxquels nous sommes confrontés. Les bons choix nous mènent à un point d’harmonie avec toutes choses peu importe la difficulté ou la longueur du chemin emprunté. Au centre du labyrinthe se trouve un cercle qui représente la mort. La mort n'est pas la sortie mais le début d'un nouveau voyage, d'un nouveau cycle.

• Astrolog par Walter D. Pullen
• Deadalus: The world’s most sophisticated Maze program par Walter D. Pullen
• The maze book for programmers par Jamis Buck (Livre)
• Wikipedia