Labyrinthes : différents algorithmes

Tableau comparatif des algorithmes

Traduit en Français par moi-même. Les originaux sont fici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Caractéristiques des algorithmes de création de labyrinthes parfaits

Algorithme	Impasses %	Type	Focus	Sans biais ?	Uniforme ?	Mémoire	Temps	Solution %	Source
Unicursal	0	Arbre	Mur	Oui	Jamais	N^2	379	100.0	Walter Pullen
Retour-récursif	10	Arbre	Passage	Oui	Jamais	N^2	27	19.0	(Générique)
Chasse et tue	11 (21)	Arbre	Passage	Oui	Jamais	0	100 (143)	9.5 (3.9)	Walter Pullen
Division récursive	23	Arbre	Mur	Oui	Jamais	N*	10	7.2	John Perry
Arbre binaire	25	Ensemble	Les deux	Non	Jamais	0*	10	2.0	(Générique)
Sidewinder	27	Ensemble	Les deux	Non	Jamais	0*	12	2.6	Walter Pullen
Algorithme d’Eller	28	Ensemble	Les deux	Non	Non	N*	20	4.2 (3.2)	Marlin Eller
Algorithme de Wilson	29	Arbre	Les deux	Oui	Oui	N^2	48 (25)	4.5	David Wilson
Algorithme d’Aldous-Broder	29	Arbre	Les deux	Oui	Oui	0	279 (208)	4.5	David Aldous & Andrei Broder
Algorithme de Kruskal	30	Ensemble	Les deux	Oui	Non	N^2	33	4.1	Joseph Kruskal
Algorithme de Prim (original)	30	Arbre	Les deux	Oui	Non	N^2	160	4.1	Robert Prim
Algorithme de Prim (simplifié)	32	Arbre	Les deux	Oui	Non	N^2	59	2.3	Robert Prim
Algorithme de Prim (modifié)	36 (31)	Arbre	Les deux	Oui	Non	N^2	30	2.3	Robert Prim
Algorithme de l’arbre qui grandit	49 (39)	Arbre	Les deux	Oui	Non	N^2	48	11.0	Walter Pullen
Algorithme de la forêt qui grandit	49 (39)	Les deux	Les deux	Oui	Non	N^2	76	11.0	Walter Pullen

Ce tableau résume les caractéristiques des algorithmes de création de labyrinthes parfaits mentionnés ci-dessus. L’algorithme de labyrinthe unicursal (les labyrinthes unicursaux sont techniquement parfaits) est inclus à titre de comparaison. Voici les descriptions des colonnes :

Impasses : C’est le pourcentage approximatif de cellules qui sont des impasses dans un labyrinthe créé avec cet algorithme, lorsqu’il est appliqué à un labyrinthe orthogonal 2D. Les algorithmes dans le tableau sont triés selon ce critère. Généralement, créer en ajoutant des murs donne le même résultat que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses. La valeur de l’Arbre qui grandit peut en réalité varier de 10% (toujours choisir la cellule la plus récente) à 49% (toujours échanger avec la cellule la plus ancienne). Avec un facteur de course suffisamment élevé, le Retour-récursif peut descendre en dessous de 1%. Le pourcentage maximum possible d’impasses dans un labyrinthe parfait orthogonal 2D est de 66%, ce qui correspondrait à un passage unicursal avec une série d’impasses d’une unité de longueur de chaque côté.

Type : Il existe deux types d’algorithmes de création de labyrinthes parfaits : Un algorithme basé sur les arbres fait croître le labyrinthe comme un arbre, ajoutant toujours à ce qui est déjà présent, ayant un labyrinthe parfait valide à chaque étape. Un algorithme basé sur les ensembles construit où il le souhaite, gardant la trace des parties du labyrinthe qui sont connectées entre elles, pour s’assurer qu’il peut tout relier pour former un labyrinthe valide une fois terminé. Certains algorithmes comme la Forêt qui grandit font les deux en même temps.

Focus : La plupart des algorithmes peuvent être implémentés soit en creusant des passages, soit en ajoutant des murs. Quelques-uns ne peuvent être réalisés que d’une seule manière. Les labyrinthes unicursaux sont toujours créés par ajout de murs puisqu’ils impliquent de bissecter des passages avec des murs, bien que le labyrinthe de base puisse être créé des deux façons. Le Retour-récursif ne peut pas être fait en ajoutant des murs car cela tend à donner un chemin solution qui suit le bord extérieur, où l’intérieur entier du labyrinthe est attaché à la bordure par une seule tige. De même, la Division récursive ne peut être faite qu’en ajoutant des murs en raison de son comportement de bissection. Chasse et tue est techniquement uniquement réalisé par creusement de passages pour une raison similaire, bien qu’il puisse être fait par ajout de murs si un effort particulier est fait pour croître vers l’intérieur depuis tous les murs frontières de manière égale.

Sans biais : Ceci indique si l’algorithme traite toutes les directions et tous les côtés du labyrinthe de manière égale, où l’analyse du labyrinthe après coup ne peut révéler aucun biais de passage. L’Arbre binaire est extrêmement biaisé, où il est facile de voyager vers un coin et difficile vers son opposé. Le Sidewinder est également biaisé, où il est facile de voyager vers un bord et difficile vers son opposé. L’algorithme d’Eller tend à avoir un passage à peu près parallèle aux bords de début ou de fin. Chasse et tue est sans biais, tant que la chasse est faite colonne par colonne ainsi que ligne par ligne pour éviter un léger biais le long d’un axe.

Uniforme : Ceci indique si l’algorithme génère tous les labyrinthes possibles avec une probabilité égale. « Oui » signifie que l’algorithme est complètement uniforme. « Non » signifie que l’algorithme peut potentiellement générer tous les labyrinthes possibles dans un espace donné, mais pas avec une probabilité égale. « Jamais » signifie qu’il existe des labyrinthes possibles que l’algorithme ne peut jamais générer. Notez que seuls les algorithmes sans biais peuvent être complètement uniformes.

Mémoire : C’est la quantité de mémoire supplémentaire ou de pile nécessaire pour implémenter l’algorithme. Les algorithmes efficaces ne requièrent et ne regardent que la bitmap du labyrinthe elle-même, tandis que d’autres nécessitent un stockage proportionnel à une seule ligne (N), ou proportionnel au nombre de cellules (N^2). Certains algorithmes n’ont même pas besoin d’avoir le labyrinthe entier en mémoire et peuvent être étendus indéfiniment (ceux-ci sont marqués d’un astérisque). L’algorithme d’Eller nécessite le stockage d’une ligne, mais compense largement cela puisqu’il n’a besoin de stocker que la ligne courante du labyrinthe en mémoire. Sidewinder n’a également besoin de stocker qu’une ligne du labyrinthe, tandis que l’Arbre binaire n’a besoin que de garder trace de la cellule courante. La Division récursive nécessite une pile jusqu’à la taille d’une ligne, mais à part cela n’a pas besoin de regarder la bitmap du labyrinthe.

Temps : Ceci donne une idée du temps nécessaire pour créer un labyrinthe avec cet algorithme, les nombres plus bas étant plus rapides. Les nombres sont seulement relatifs les uns aux autres (l’algorithme le plus rapide étant assigné à la vitesse 10) plutôt qu’en unités spécifiques, car le temps dépend de la taille du labyrinthe et de la vitesse de l’ordinateur. Ces nombres proviennent de la création de labyrinthes de passages 100×100 dans la dernière version de Daedalus. Généralement, créer en ajoutant des murs prend le même temps que creuser des passages, cependant si la différence est significative, le temps d’ajout de murs est indiqué entre parenthèses.

Solution : C’est le pourcentage de cellules du labyrinthe que le chemin solution traverse, pour un labyrinthe typique créé par l’algorithme. Cela suppose que le labyrinthe fait 100×100 passages avec le début et la fin dans des coins opposés. C’est une mesure de la « sinuosité » du chemin solution. Les labyrinthes unicursaux ont une sinuosité maximale, puisque la solution traverse l’ensemble du labyrinthe. L’Arbre binaire a la sinuosité minimale possible, où le chemin solution traverse simplement le labyrinthe et ne dévie jamais ou ne cesse jamais de progresser vers la fin. Généralement, créer en ajoutant des murs a les mêmes propriétés que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses.

Source : C’est la source de l’algorithme, ce qui signifie par qui il est nommé, ou qui l’a inventé ou popularisé. Certains sont listés comme « génériques », ce qui signifie qu’ils sont si évidents qu’ils ont été imaginés ou implémentés par de nombreuses personnes indépendamment. Walter Pullen a nommé « Chasse et tue », mais n’a pas inventé la technique, dont on peut trouver des implémentations datant de nombreuses années.

Labyrinthes : différents algorithmes

Labyrinthe Sidewinder

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthe Sidewinder

Cet algorithme simple est très similaire à l’algorithme de l’arbre binaire, et seulement légèrement plus compliqué. Le labyrinthe est généré ligne par ligne : Pour chaque cellule, décidez au hasard de creuser un passage vers la droite. Si un passage n’est pas creusé, alors considérez le passage horizontal qui vient d’être complété, formé par la cellule actuelle et toutes les cellules à gauche qui ont creusé des passages menant jusqu’à elle. Choisissez au hasard une cellule le long de ce passage, et creusez un passage vers le haut à partir de celle-ci (qui doit être la cellule actuelle si la cellule adjacente n’a pas creusé). Alors qu’un labyrinthe en arbre binaire monte toujours depuis la cellule la plus à gauche d’un passage horizontal, un labyrinthe Sidewinder monte depuis une cellule aléatoire. Alors qu’un arbre binaire a les bords supérieur et gauche du labyrinthe formant un long passage, un labyrinthe Sidewinder n’a que le bord supérieur formant un long passage. Comme l’arbre binaire, un labyrinthe Sidewinder peut être résolu de manière déterministe sans erreur de bas en haut, car à chaque ligne, il y aura toujours exactement un passage menant vers le haut. Une solution à un labyrinthe Sidewinder ne reviendra jamais sur elle-même ou ne visitera jamais une ligne plus d’une fois, bien qu’elle « serpente de côté en côté ». Le seul type de cellule qui ne peut pas exister dans un labyrinthe Sidewinder est une impasse avec le passage orienté vers le bas, car cela contredirait le fait que chaque passage montant mène au début. Un labyrinthe Sidewinder a tendance à avoir une solution élitiste, où le bon chemin est très direct, mais il y a beaucoup de longs faux chemins descendant du haut à côté de lui.

Labyrinthes : différents algorithmes

Labyrinthes en arbre binaire

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthes en arbre binaire

C’est fondamentalement l’algorithme le plus simple et le plus rapide possible, cependant les labyrinthes qu’il produit ont une texture très biaisée. Pour chaque cellule, creusez un passage soit vers le haut, soit vers la gauche, mais pas les deux. Dans la version avec ajout de murs, pour chaque sommet ajoutez un segment de mur menant vers le bas ou vers la droite, mais pas les deux. Chaque cellule est indépendante de toutes les autres cellules, où vous n’avez pas besoin de vous référer à l’état des autres cellules lors de sa création. Par conséquent, c’est un véritable algorithme de génération de labyrinthe sans mémoire, sans limite de taille du labyrinthe que vous pouvez créer.
C’est fondamentalement un arbre binaire au sens informatique, si vous considérez le coin supérieur gauche comme la racine, où chaque nœud ou cellule a un parent unique qui est la cellule au-dessus ou à gauche de celle-ci. Les labyrinthes en arbre binaire sont différents des labyrinthes parfaits standards, puisqu’environ la moitié des types de cellules ne peuvent jamais exister en eux. Par exemple, il n’y aura jamais de carrefour, et toutes les impasses ont des passages pointant vers le haut ou vers la gauche, et jamais vers le bas ou vers la droite.
Le labyrinthe a tendance à avoir des passages menant en diagonale du coin supérieur gauche au coin inférieur droit, ce qui rend le labyrinthe beaucoup plus facile à naviguer du coin inférieur droit vers le coin supérieur gauche. Vous pourrez toujours voyager vers le haut ou vers la gauche, mais jamais les deux, donc vous pouvez toujours voyager de manière déterministe en diagonale vers le haut et vers la gauche sans rencontrer d’obstacles. C’est en voyageant vers le bas et vers la droite que vous rencontrerez des choix et des impasses. Notez que si vous retournez un labyrinthe en arbre binaire à l’envers et traitez les passages comme des murs et vice versa, le résultat est fondamentalement un autre arbre binaire.

Labyrinthes : différents algorithmes

Algorithme de la Division récursive

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de la Division récursive

Cet algorithme est un peu similaire au retour-récursif, puisqu’ils sont tous deux basés sur une pile, sauf que celui-ci se concentre sur les murs plutôt que sur les passages. Commencez par créer un mur horizontal ou vertical aléatoire traversant la zone disponible dans une rangée ou une colonne aléatoire, avec une ouverture placée au hasard le long de celui-ci. Ensuite, répétez le processus de manière récursive sur les deux sous-zones générées par le mur de division. Pour de meilleurs résultats, privilégiez le choix horizontal ou vertical en fonction des proportions de la zone, par exemple une zone deux fois plus large que haute devrait être divisée plus souvent par un mur vertical. C’est l’algorithme le plus rapide sans biais directionnel, et peut même rivaliser avec les labyrinthes en arbre binaire car il peut terminer plusieurs cellules à la fois, bien qu’il ait le défaut évident de longs murs traversant l’intérieur. Cet algorithme est une forme de labyrinthes fractals imbriqués, sauf qu’au lieu de toujours créer des labyrinthes de taille de cellule fixe avec des labyrinthes de même taille dans chaque cellule, il divise la zone donnée de manière aléatoire en un labyrinthe de taille aléatoire 1×2 ou 2×1. La division récursive ne fonctionne pas comme un creuseur de passages, car cela aboutirait à un chemin de solution évident qui suit soit le bord extérieur, soit traverse directement l’intérieur.

Labyrinthes : différents algorithmes

Algorithme de Prim (modifié)

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (modifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, modifié de sorte que tous les poids des arêtes soient les mêmes, mais également implémenté en regardant les cellules plutôt que les arêtes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Pendant la création, chaque cellule est d’un des trois types : (1) « Dedans » : La cellule fait partie du labyrinthe et a déjà été creusée, (2) « Frontière » : La cellule ne fait pas partie du labyrinthe et n’a pas encore été creusée, mais est à côté d’une cellule qui est déjà « dedans », et (3) « Dehors » : La cellule ne fait pas encore partie du labyrinthe, et aucun de ses voisins n’est « dedans » non plus.

Commencez par choisir une cellule, la mettre « dedans », et définir tous ses voisins comme « frontière ». Continuez en choisissant une cellule « frontière » au hasard, et en creusant vers elle à partir d’une de ses cellules voisines qui sont « dedans ». Changez cette cellule « frontière » en « dedans », et mettez à jour tous ses voisins qui sont « dehors » en « frontière ». Le labyrinthe est terminé quand il n’y a plus de cellules « frontière » (ce qui signifie qu’il n’y a plus de cellules « dehors » non plus, donc elles sont toutes « dedans »).

Cet algorithme donne des labyrinthes avec un facteur « rivière » très bas avec beaucoup d’impasses courtes, et une solution plutôt directe. Le labyrinthe résultant est très similaire à l’algorithme de Prim simplifié, avec seulement la subtile distinction que les indentations dans l’arbre en expansion ne sont remplies que si cette cellule frontière est sélectionnée au hasard, contrairement au fait d’avoir trois fois plus de chances de remplir cette cellule via une des arêtes frontières menant à elle. Il s’exécute également très rapidement, plus rapidement que l’algorithme de Prim simplifié car il n’a pas besoin de composer et de maintenir une liste d’arêtes.

Labyrinthes : différents algorithmes

Algorithme de Prim (simplifié)

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (simplifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, simplifié de telle sorte que tous les poids des arêtes sont les mêmes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Commencez avec un sommet aléatoire. Continuez en sélectionnant au hasard une arête de passage reliant le labyrinthe à un point qui n’en fait pas encore partie, et attachez-la au labyrinthe. Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer. Comme les arêtes n’ont pas de poids et ne sont pas ordonnées, elles peuvent être stockées dans une simple liste, ce qui signifie que la sélection d’éléments dans la liste est très rapide et ne prend qu’un temps constant. Par conséquent, c’est beaucoup plus rapide que l’algorithme de Prim original avec des poids d’arêtes aléatoires. La texture du labyrinthe produit aura un facteur « rivière » plus faible et une solution plus simple que l’algorithme de Prim original, car il se répandra uniformément à partir du point de départ comme du sirop versé, au lieu de contourner et de s’écouler autour des groupes d’arêtes de poids plus élevé qui ne sont pas couverts avant plus tard. Copy

Labyrinthes : différents algorithmes

Algorithme de Prim (original)

Traduit en Français par moi-même. Les originaux sont ici.

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (original)<

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, opérant sur des poids d’arêtes aléatoires uniques. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe.

Fonctionnement de l’algorithme :

1. Commencez avec n’importe quel sommet (le labyrinthe final sera le même quel que soit le sommet de départ).
2. Continuez en sélectionnant l’arête de passage ayant le plus petit poids qui relie le labyrinthe à un point qui n’en fait pas encore partie.
3. Attachez cette arête au labyrinthe.
4. Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer.

Pour sélectionner efficacement l’arête suivante, une file de priorité (généralement implémentée avec un tas) est nécessaire pour stocker les arêtes frontières. Malgré cela, cet algorithme est relativement lent, car la sélection d’éléments et la maintenance du tas nécessitent un temps logarithmique (log(n)).

Par conséquent, l’algorithme de Kruskal, qui produit également un arbre couvrant minimal, peut être considéré comme meilleur, car il est plus rapide et produit des labyrinthes avec une texture identique. En fait, avec la même graine de nombres aléatoires, des labyrinthes identiques peuvent être créés avec les algorithmes de Prim et de Kruskal.

J’ai crée un algorithme qui génère grâce à autohotkey toute une suite d’ordres clavier afin de générer des labyrinthes.

Comme beaucoup de personnes me l’ont demandé, je vous donne toutes mes sources, des heures entières de travail…
Cliquez ici pour les récupérer !
C’est le programme complet qui génère les labyrinthes, et il faut compiler tout en ligne de commande sous Linux. C’est ultra simple :

• allez dans le répertoire « 0 » et tapez « make », et vous avez le premier programme ;
• allez dans le répertoire « 1 » et tapez « make », et vous avez le second programme ;
• allez dans le répertoire « 2 » et tapez « make », et vous avez le troisième programme ;

Chaque programme génère un fichier… pour qu’il soit en entrée pour le suivant. Je me suis basé sur le principe Linux : chaque programme est petit, mais fait une tâche, et la fait bien.

En voici quelques écrans :

Vous êtes toujours là ? Ok alors, j’ai un peu mieux : j’ai développé l’algorithme de l’arbre qui grandit (regardez dans mes algorithmes de labyrinthes) et je l’ai appliqué à Trackmania. Ca fonctionne parfaitement ! Les circuits sont encore plus durs à réaliser, mais parfois si on arrive à prendre de l’élan on peut tricher et couper, mais c’est rare ! Enfin tout ça pour dire que c’est pas évident d’y arriver et que les résultats sont impressionnants, regardez les images qui suivent !

Eh oui vous l’avez constaté peut-être mais il y a plusieurs montées possibles, et une seule est valide ! Incroyable non ? Moi je suis fier du résultat !

Concernant les labyrinthes, il n’est nulle part précisé le principe de pondération des liens. Alors je le fais !

La pondération, c’est « donner un poids ». Dans la plupart des algorithmes que j’ai donné on peut tout à fait donner un « poids » à chaque lien. Et en fonction de son poids, le lien aura plus ou moins de chances d’être tiré.
Exemple : une cellule a 4 sorties possibles : N, E, S, O. Chaque sortie a un poids.

• Premier exemple : N = 1, E=1, S = 1, O = 1. Les chances sont toutes identiques. La pondération n’est pas utile dans ce cas, mais c’est juste pour avoir une idée.
• Deuxième exemple : N = 40, E=10, S = 40, O = 10. La somme totale de la pondération est 100. On aura 80 chances sur 100 de tirer N ou S, et à peine 20 chances sur 100 de tirer E ou O.

Voilà sur le principe.
En pratique, voilà comment j’ai implémenté cela : j’ai, au départ, un tableau de poids. Par exemple :
poids[0] = 1, poids[1]=40 et poids[2]=10
Tous mes liens n’ont pas un poids, mais un indice vers le tableau des poids.
Reprenons les exemples :

• Premier exemple : ma cellule aura les liens ainsi : N = 0, E=0, S = 0, O = 0 ;
• Deuxième exemple : ma cellule aura les liens ainsi : N = 1, E=2, S = 1, O = 2.

Au moment de « tirer au hasard » un lien parmi ceux présents de la cellule : je fais la somme de tous les poids.
Reprenons les exemples :

• Premier exemple : somme = 4 ;
• Deuxième exemple : somme = 100.

Ensuite, je tire un chiffre entre 1 et la somme et je cherche à quelle direction cela correspond.
En pratique, il m’est ainsi possible de créer des labyrinthes avec des « orientations » dans certaines zones, et d’autres orientations dans d’autres zones.
Si cette idée vous a été utile, servez-vous en !