Algorithme pour la génération de labyrinthes sans impasses ?

Question

Je cherche un algorithme de génération de labyrinthes qui puisse générer des labyrinthes sans impasse mais avec seulement un début et une fin. Comme ceci :

_{Image de <a href="http://www.astrolog.org/labyrnth/maze/unicursl.gif" rel="noreferrer">http://www.astrolog.org/labyrnth/maze/unicursl.gif</a>}

Où puis-je trouver ou m'y prendre pour construire un tel algorithme de génération de labyrinthes ?

Answer 1

On dirait que vous voulez une courbe de remplissage d'espace pseudo-aléatoire (par exemple, voir Courbes de remplissage de l'espace basées sur le contexte -EUROGRAPHICS '2000 (format PDF, 1.1 MB))

Jetez un coup d'œil à _Courbe de remplissage de l'espace_ .

Je pense que vous pourriez appliquer un certain caractère aléatoire à la construction de l'un d'entre eux pour obtenir ce que vous voulez.

Answer 2

Je vous suggère de commencer par un carré complètement noir (plein) et d'essayer de creuser le chemin. Pendant le creusement, vous pouvez facilement vous assurer qu'il n'y a pas d'impasse, continuez simplement. Utilisez le backtracking, l'algorithme de recherche en profondeur. Faites une "marche aléatoire" - à chaque étape, décidez aléatoirement de garder la direction ou de la changer. Vérifiez l'absence d'impasse - si vous êtes bloqué, vous pouvez soit dire "bon, j'ai fini, je suis à l'arrivée", soit, si vous considérez que le labyrinthe n'est pas encore assez creusé, revenir en arrière. Se souvenir toujours de ce que l'on a fait avant et essayer au hasard une autre action. Utilisez probablement une heuristique pour préférer certaines directions, comme, par exemple, toujours garder un espace libre avant d'esquiver le mur, essayer d'abord de contourner les murs, etc. - De cette façon, vous pourriez trouver la solution souhaitée qui remplit tout le carré beaucoup plus rapidement.

Answer 3

Je n'y ai pas réfléchi, c'est juste une idée :

• Ne vous concentrez pas sur le chemin, mais sur les murs.
• Commencez par le carré extérieur noir
• Ajouter progressivement des blocs de mur dans des positions arbitraires adjacentes aux blocs de mur existants, 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 avez terminé.

Le processus de sélection "arbitraire" de nouveaux morceaux de mur peut commencer par essayer de faire "pousser" des sections droites perpendiculaires au mur extérieur, puis, à un moment donné, passer au remplissage partout où cela est possible.

Il faudrait probablement qu'il puisse revenir en arrière s'il était bloqué.

Il n'est probablement pas très efficace.

Answer 4

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 des marches aléatoires !

Le concept est simple : compte tenu des limites extérieures du labyrinthe, d'un point de départ et d'un point d'arrivée, écrivez une fonction permettant de générer des parcours aléatoires à partir du point de départ qui se terminent au point d'arrivée. Les conditions seraient que notre "marcheur aléatoire" ne puisse se déplacer que vers le haut, le bas, la droite ou la gauche à partir de la case précédente, et qu'il ne puisse pas s'approcher à moins d'une case d'une case précédemment traversée (cela crée des murs).

À mon avis, il y a deux défis algorithmiques à relever. Le premier consiste à vérifier si nous sommes à moins d'un carré d'un carré déjà traversé (collisions). Peut-être pourrions-nous maintenir une liste des carrés traversés (leurs coordonnées) et des limites du labyrinthe, et pour chaque nouveau carré, évaluer la distance par rapport à chaque carré de la liste. Mais cela ne semble pas très efficace.

L'autre défi consiste à atteindre le point final avec notre marche aléatoire. Si les collisions avec les carrés précédemment traversés n'étaient pas un problème, nous serions obligés d'atteindre notre point final, mais avec elles, nous avons le problème de nous isoler du point final. Le moyen d'éviter cela est de vérifier et d'éviter d'entrer dans des boucles. Si nous évitons d'entrer dans les boucles formées par le chemin parcouru et/ou les limites du labyrinthe, nous conservons un chemin possible vers le point final. Pour ce qui est de déterminer si nous sommes dans une boucle... Meh, c'est un peu difficile.

Si vous disposez déjà d'un algorithme de résolution de labyrinthe, vous pouvez l'exécuter à chaque fois qu'une collision est possible pour voir s'il existe un chemin entre votre case actuelle et le point d'arrivée. Lorsque vous l'exécutez, faites-lui penser que tous les carrés précédemment traversés sont des murs, ainsi que leurs limites.

Answer 5

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

Commencez par une grille vierge, et remplissez-la de petites boucles de 2x2. Si la grille est impaire par paire, vous devrez ajouter quelques boucles 2x3, et si elle est impaire par impaire, vous devrez laisser un seul carré libre - je laisse normalement un coin non rempli.

Ensuite, joignez arbitrairement les boucles ensemble pour former des boucles plus grandes - ainsi (par exemple) 2 boucles 2x2 deviennent une seule boucle 4x2. Continuez ainsi, en veillant à ne pas relier une boucle à elle-même.

Vous finirez par obtenir une seule boucle qui utilise toutes les cellules occupées par la ferme de boucles d'origine. Brisez cette boucle à n'importe quel endroit, et vous obtenez un labyrinthe unicursal, où les points de départ et d'arrivée sont voisins.

Vous pouvez maintenant déplacer les points d'extrémité dans la grille en formant et en brisant de petites boucles - accrochez l'extrémité à un autre point du labyrinthe, puis brisez la jonction en T du côté opposé pour reformer votre unique morceau de ficelle avec un nouvel emplacement d'extrémité.

Si vous travaillez sur un labyrinthe impair, utilisez cette dernière technique pour faire passer l'une de vos extrémités dans le coin non rempli afin de compléter votre labyrinthe.