Algorithme pour génération de labyrinthe sans impasses?

je préférerais commencer par un carré complètement noir (plein) et essayer de creuser le chemin. Pendant le creusage, vous vous assurez facilement qu'il n'y a pas de cul-de-sac, il suffit de continuer. Utilisez l'algorithme backtracking, depth first search. Faites une "marche au hasard" - à chaque étape, décidez au hasard s'il faut garder la direction ou la changer. Vérifiez la condition de l'impasse - si vous êtes coincé, vous pouvez soit dire "Eh bien, je suis fait, je suis dans l'arrivée", ou, si vous considérez le labyrinthe pas encore creusé assez, juste faire marche arrière. Toujours rappelez-vous ce que vous avez fait avant et essayer au hasard une autre action. Probablement utiliser quelque heuristique pour préférer certaines directions, comme, disons, toujours garder un peu d'espace libre avant d'esquiver le mur, essayer d'abord de marcher autour des murs, etc - de cette façon, vous pourriez trouver la solution désirée qui remplit tous les carrés beaucoup plus rapidement.

dans l'exemple que vous donnez, il n'y a qu'un seul chemin réel du début à la fin. Si c'est tout ce que vous voulez, je pense que vous pourriez utiliser marches aléatoires!

le concept est simple: étant donné les limites extérieures du labyrinthe, un point de départ, et un point final, écrivez une fonction pour générer des marches aléatoires à partir du point de départ qui finissent éventuellement au point final. Les conditions seraient que notre "random walker" ne peut se déplacer vers le haut, vers le bas, à droite ou à gauche de la place précédente, et ne peut pas venir dans un carré d'un carré précédemment traversé (cela crée des murs).

selon moi, il y a deux défis algorithmiques ici. La première consiste à déterminer si nous sommes à l'intérieur d'un carré d'un carré déjà traversé (collisions). Peut-être pourrions-nous maintenir une liste de carrés traversés (leurs coordonnées) et les limites de labyrinthe, et pour chaque nouveau carré évaluer la distance de chaque carré dans la liste. Cela ne semble pas très efficace cependant.

Les autres le défi est en fait d'atteindre le point final avec notre promenade au hasard. Si les collisions avec les carrés précédemment traversés n'étaient pas un problème, nous serions tenus d'atteindre notre point final éventuellement, mais avec eux, nous avons le problème que nous pourrions nous murer hors du point final. La façon d'éviter cela est de vérifier et d'éviter l'entrée de la boucle. Si nous évitons d'entrer dans les boucles formées par le chemin traversé et/ou les limites du labyrinthe, alors nous maintenons un chemin possible jusqu'au point final. Dans la mesure où effectivement déterminer si nous sommes dans une boucle... Meh c'est un peu dur.

si vous avez déjà un algorithme de résolution de labyrinthe, vous pouvez l'exécuter à chaque fois que vous avez une collision possible pour voir si un chemin existe entre votre carré actuel et le point final. Quand vous l'exécutez, pensez-vous que toutes les places précédemment traversées sont des murs, ainsi que leurs limites.

je n'ai pas réfléchi, juste une idée:

• Concentrer non pas sur le chemin, mais sur les murs
• Démarrer avec l'extérieur noir carré
• ajouter progressivement des blocs de mur dans des positions arbitraires adjacentes aux blocs existants de mur, en maintenant la condition qu'il reste un chemin du début à la fin
• quand aucune cellule de chemin n'a plus de deux voisins de chemin, vous êtes fait

la sélection "arbitraire" processus pour de nouveaux morceaux de paroi peut commencer à essayer de "croître" sections droites perpendiculaires à la paroi extérieure, puis à un certain stade passer à remplir dans la mesure du possible.

il aurait probablement besoin de la capacité de revenir en arrière s'il se coince.

probablement ce n'est pas trop efficace.

Ahh - j'ai trouvé un moyen beaucoup plus facile de générer un unicursal labyrinthe.

commencez avec une grille vierge, et remplissez-la avec de petites boucles 2x2. Si la grille est impair-by-pair, vous aurez besoin de mélanger dans quelques boucles 2x3, et si c'est impair-by-Impair, vous devrez laisser un carré libre - je laisse normalement un coin non rempli.

ensuite, joindre arbitrairement les boucles ensemble pour former des boucles plus grandes - donc (par exemple) 2 boucles 2x2 deviennent une seule boucle 4x2. Continue de faire ça, en t'assurant que tu ne pas joindre une boucle de retour à lui-même.

finalement vous finirez avec une seule boucle qui épuise toutes les cellules occupées par la ferme originale des boucles. Briser cette boucle à n'importe quelle position, et vous avez un labyrinthe unicursal, où les emplacements de début et de fin sont à côté de l'autre.

vous pouvez maintenant déplacer les points d'extrémité autour de la grille en formant et en cassant de petites boucles-crocheter l'extrémité dans un autre point dans le labyrinthe, puis briser la jonction En T sur le côté opposé pour reformer votre seul morceau de corde avec un nouvel emplacement de fin.

si vous travaillez sur un labyrinthe Impair-by-Impair, utilisez cette dernière technique pour aiguiser une de vos extrémités vers le coin vide pour compléter votre labyrinthe.

je pense que j'ai trouvé une autre méthode, mais je ne l'ai pas encore testé en profondeur.

voir https://twitter.com/tdhooper/status/340853820584230915/photo/1

De gauche à droite:

• Générer une non-unicursal labyrinthe comme décrit ici https://en.wikipedia.org/wiki/File:Prim_Maze.svg, je pense que c'est l'algorithme de Prim

• sceller la sortie

• Dessiner un chemin de visites chaque point dans le labyrinthe (ie. essayez de le résoudre)

• faites de ce chemin un mur

quand "marche" garder les changements faits sur chaque pas dans une pile, de sorte que de cette façon vous pouvez regarder x Pas en avant et puis à chaque étape de sorte que vous ne pouvez pas prendre d'autres mesures ( marché dans un coin ou une spirale comme marcher ) pop la pile jusqu'à ce que vous avez un chemin de marche viable et continuer à marcher de là jusqu'à ce que la pile est vide ( I. e vous pop la pile tout le chemin du retour parce qu'à chaque étape précédente il n'y avait pas de voisin viable ). Ensuite, appliquez les transformations à la structure de données du labyrinthe.

je suis en train de travailler sur cette question à l'instant... En partant d'un bord, je marche au hasard à travers une rangée carrée, marquant les cellules avec la longueur du chemin que je passe à travers eux.

lorsque vous êtes coincé (et vous le ferez), créez une jonction En T formant une boucle avec le chemin le plus récent qui est adjacent à vous (mais voir ci-dessous). Je fais ensuite marche arrière le long du chemin existant jusqu'à l'autre côté de la jonction En T et je romps la boucle là. Cette queue pendante forme alors votre nouvelle "tête" de la promenade aléatoire (rappelez-vous de recalculer vos longueurs de chemin à partir de la source du chemin), et vous pouvez continuer.

les expériences montrent qu'en faisant cela, il n'entre pas (ou n'a pas encore - voir ci-dessous) dans une boucle de création de nouvelles queues, aussi longtemps que si votre nouvelle "queue" est piégée, vous ne reformez pas simplement sans réfléchir un lien avec la cellule que vous venez de briser si elle est la plus récente - choisissez la deuxième plus récente dans ce cas.

le cas de terminaison est lorsque vous êtes "coincé" sur un élément de bord, et vous avez rempli le tableau (votre longueur de chemin est la même que la zone du tableau) - c'est terminé. Votre point de départ mène à votre point final.

il semble y avoir deux inefficacités possibles et des hoquets potentiels avec ceci (je joue avec l'algorithme en ce moment) - parfois vous marcherez dans un coin et la seule façon de continuer est de reformer le lien de boucle avec celui que vous venez de casser. Puis la séquence recule à travers toutes les boucles que vous avez faites précédemment à la le point où tu étais coincé. Si vous ne pouvez pas aller n'importe où ailleurs (c'est un autre coin) alors vous aurez juste rebondir entre les deux. Il y a des moyens de contourner ça, mais ça veut dire garder une sorte de liste de cellules en boucle, ne l'effaçant que quand on trace un nouveau chemin.

L'autre est qu'il semble enclin à laisser un étrange carrés vacants, en particulier lorsque votre tableau est impair-impair. Je n'ai pas enquêté sur la raison pour laquelle c'est le cas, et c'est quand cela il se produit que le problème de coin précédent semble particulièrement prévalant. Le travail continue...