Tableau comparatif des algorithmes

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.