Algorithme de Prim (modifié)

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.