Comment parcourir un labyrinthe par programme lorsque vous êtes dans une impasse

Question

Avancer dans le labyrinthe est assez facile, mais je n'arrive pas à comprendre comment reculer dans le labyrinthe pour essayer un nouvel itinéraire une fois que vous êtes dans une impasse sans revenir trop loin ?

Answer 1

Utiliser retour en arrière en conservant une pile de décisions de direction antérieures.

Answer 2

L'algorithme le plus simple (à mettre en œuvre) serait de simplement conserver une pile d'emplacements où vous vous êtes rendu et l'itinéraire que vous avez emprunté à partir de chacun, à moins qu'un retour en arrière ne vous donne cette information.

Pour revenir en arrière, supprimez simplement les anciens emplacements de la pile et recherchez d'autres sorties à partir de cet emplacement jusqu'à ce que vous trouviez un ancien emplacement avec une sortie non testée.

En testant systématiquement les sorties dans le même ordre à chaque fois, si vous savez que le retour en arrière vers un emplacement vient du bas (c.-à-d.la dernière fois que vous étiez à l'ancien endroit où vous êtes descendu), vous choisissez alors simplement la direction suivante après vers le bas.

Je ne suis pas entièrement sûr de ce que tu veux dire par je remonte trop loin cependant, je suppose que vous voudriez revenir à l'endroit précédent où vous aviez des itinéraires non testés, n'est-ce pas ce que vous voulez ?

Notez qu'à moins que vous n'essayiez de suivre le chemin depuis le point de départ jusqu'à votre emplacement actuel et d'éviter ces carrés lorsque vous essayez de trouver de nouveaux itinéraires, vous pourriez finir par faire un cercle, ce qui finirait par rendre la pile trop grande.

Une méthode récursive simple qui marque le chemin qu'il emprunte et n'entre jamais dans les zones marquées peut facilement le faire.

Aussi, si votre chose qui se déplace dans le labyrinthe est légèrement plus intelligent que de simplement pouvoir se déplacer et frapper (s'arrêter) sur les murs, dans le sens où il peut voir depuis son point actuel dans toutes les directions, j'ai d'autres algorithmes qui pourraient aider.

Answer 3

Eric Lippert a rédigé une série d'articles sur la création d'un Implémentation C# de A*, ce qui pourrait être plus efficace.