Vous pouvez penser à votre labyrinthe comme un arbre.
Un
/ \
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
/ \
L M
/ \
** O
(qui pourrait représenter)
DÉMARRER
+ +---+---+
DE L'A | C G |
+---+ + + +
| D B | F | J |
+---+---+ +---+---+
| L H E I |
+---+ +---+---+
| M O |
+ +---+
FINITION
(ignorer de gauche à droite de la commande sur l'arbre)
Où chaque nœud est un carrefour de chemins. D, I, J, L et S sont des impasses, et ** est le but.
Bien sûr, dans votre arbre, chaque nœud a une possibilité d'avoir trois enfants.
Votre objectif est simplement de trouver ce que les nœuds à traverser pour trouver la ligne d'arrivée. Tout ol' arbre de l'algorithme de recherche vont le faire.
Regardant l'arbre, il est assez facile de voir votre bonne solution simplement en "suivi" de l' ** à la partie la plus profonde de l'arbre:
A B E H M **
Notez que cette approche devient légèrement plus compliqué quand vous avez des "boucles" dans votre labyrinthe (c'est à dire, lorsque c'est possible, sans backtracing, vous entrez dans un passage que vous avez déjà parcouru à travers). Vérifier les commentaires pour une solution sympa.
Maintenant, penchons-nous sur votre première solution que vous avez mentionné, appliqué à cet arbre.
Votre première solution est fondamentalement une Profondeur d'Abord de Recherche, ce qui n'est vraiment pas mauvais. C'est en fait une très bonne recherche récursive. Fondamentalement, il est dit, "Toujours prendre la plus à droite de l'approche de la première. Si rien n'est là, revenir en arrière jusqu'à ce que le premier endroit où vous pouvez aller tout droit ou à gauche, puis répétez.
Profondeur d'abord la recherche ci-dessus l'arbre, dans cet ordre:
A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J
Notez que vous pouvez vous arrêter dès que vous trouvez l' **.
Cependant, lorsque vous code de la profondeur d'abord de recherche, l'utilisation récursive de programmation rend rend tout beaucoup plus facile. Même les méthodes itératives trop de travail, et vous n'avez jamais explicitement au programme de façon à revenir en arrière. Découvrez l'article lié pour les implémentations.
Une autre façon de chercher un arbre est la Largeur de la Première solution, qui permet de rechercher à travers les arbres en fonction de la profondeur. Il avait de recherche à travers le dessus de l'arbre, dans cet ordre:
A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O
Notez que, en raison de la nature d'un labyrinthe, en largeur d'abord a beaucoup plus de montant moyen de nœuds qu'il vérifie. En largeur d'abord est facilement mise en œuvre par avoir une file d'attente de chemins de recherche, et à chaque itération popping une voie de sortie de la file d'attente "exploser" par tous les chemins qu'il peut se transformer en après une étape, et de mettre ces nouveaux chemins à la fin de la file d'attente. Il n'y a pas explicite "niveau suivant" commandes de code, et de ceux qui étaient juste là pour aider à la compréhension.
En fait, il y a toute une vaste liste de moyens de recherche d'un arbre. J'ai juste mentionné les deux la plus simple, la plus simple.
Si votre labyrinthe est très, très, longue et profonde, et a boucles et des fous, et qu'il est compliqué, je suggère à la Une* l'algorithme, qui est le standard de l'industrie de l'algorithme de pathfinding qui combine une Largeur tout d'Abord de recherche avec les heuristiques...un peu comme une "intelligent en largeur d'abord de recherche".
Il fonctionne en fait comme ceci:
- Mettre un chemin dans une file d'attente (le chemin d'accès où vous ne marchez une étape directement dans le labyrinthe). Un chemin d'accès a un "poids" donnée par sa longueur actuelle + la distance en ligne droite à partir de la fin (qui peut être calculée mathématiquement)
- Pop le chemin avec le poids le plus bas de la file d'attente.
- "Exploser" le chemin d'accès dans chaque chemin qu'il pourrait être après une seule étape. (c'est à dire, si votre chemin est à Droite à Gauche Gauche à Droite, puis votre explosé chemins sont R L L R R et R L L R L, ne comprenant pas illégal de celles qui vont à travers les murs)
- Si l'un de ces chemins est l'objectif, la Victoire! Sinon:
- Calculer le poids de la éclatée chemins, et de mettre tous de retour dans la file d'attente (pas y compris le chemin d'origine)
- Trier la file d'attente en poids, plus bas en premier. Ensuite, répétez à partir de l'Étape #2
Et c'est Un*, et que je présente spécialement mis en avant parce que c'est plus ou moins la norme de l'industrie de l'algorithme de pathfinding pour toutes les applications de pathfinding, y compris le déplacement d'un bord de la carte à un autre tout en évitant les voies hors route ou de montagne, etc. Il fonctionne bien car il utilise une plus petite distance possible heuristique, qui lui donne son "intelligence". A* est polyvalent parce que, étant donné un problème, si vous avez une plus petite distance possible heuristique disponible (le nôtre est facile -- la ligne droite), vous pouvez l'appliquer.
MAIS il est d'une grande valeur à noter que A* est pas votre seule option.
En fait, le wikipédia de la catégorie de parcours d'arbres algorithmes de listes de 97 à lui seul! (le meilleur sera toujours sur cette page liée plus tôt)
Désolé pour la longueur =P (j'ai tendance à radoter)
