Comment fonctionne A * pathfinding?

J'aimerais comprendre à la base le fonctionnement de A * pathfinding. Toute implémentation de code ou de code pseudo ainsi que des visualisations seraient utiles.

Avertissement

Il y a des tonnes d'exemples de code et d'explications sur A * disponibles en ligne. Cette question a également reçu beaucoup de bonnes réponses avec beaucoup de liens utiles. Dans ma réponse, je vais essayer de fournir un exemple illustré de l'algorithme, qui pourrait être plus facile à comprendre que le code ou les descriptions.

Algorithme de Dijkstra

Pour comprendre A *, je vous suggère de jeter un coup d'œil à l'algorithme de Dijkstra . Laissez-moi vous guider à travers les étapes que l'algorithme de Dijkstra effectuera pour une recherche.

Notre nœud de départ est Aet nous voulons trouver le chemin le plus court F. Chaque bord du graphique est associé à un coût de déplacement (indiqué par des chiffres noirs à côté des bords). Notre objectif est d'évaluer le coût de déplacement minimal pour chaque sommet (ou nœud) du graphique jusqu'à atteindre notre nœud d'objectif.

Ceci est notre point de départ. Nous avons une liste de nœuds à examiner, cette liste est actuellement:

{ A(0) }

Aa un coût de 0, tous les autres nœuds sont réglés à l' infini (dans une implémentation typique, ce serait quelque chose de similaire int.MAX_VALUEou similaire).

Nous prenons le nœud avec le coût le plus bas de notre liste de nœuds (car notre liste ne contient que Ac'est notre candidat) et nous visitons tous ses voisins. Nous fixons le coût de chaque voisin à:

Cost_of_Edge + Cost_of_previous_Node

et gardez une trace du noeud précédent (indiqué par une petite lettre rose en dessous du noeud). Apeut être marqué comme résolu (rouge) maintenant, de sorte que nous ne le visitons plus. Notre liste de candidats ressemble maintenant à ceci:

{ B(2), D(3), C(4) }

De nouveau, nous prenons le nœud avec le coût le plus bas de notre liste ( B) et évaluons ses voisins. Le chemin d'accès à Dest plus coûteux que le coût actuel de D, donc ce chemin peut être ignoré. Esera ajouté à notre liste de candidats, qui ressemble maintenant à ceci:

{ D(3), C(4), E(4) }

Le prochain nœud à examiner est maintenant D. La connexion à Cpeut être supprimée, car le chemin d'accès n'est pas plus court que le coût existant. Nous avons trouvé un chemin d'accès plus court E, donc le coût Eet son nœud précédent seront mis à jour. Notre liste ressemble maintenant à ceci:

{ E(3), C(4) }

Comme précédemment, nous examinons le nœud présentant le coût le plus bas de notre liste, qui est maintenant E. Ea seulement un voisin non résolu, qui est également le nœud cible. Le coût pour atteindre le nœud cible est défini sur 10et son nœud précédent sur E. Notre liste de candidats ressemble maintenant à ceci:

{ C(4), F(10) }

Ensuite, nous examinons C. Nous pouvons mettre à jour le coût et le noeud précédent pour F. Puisque notre liste a maintenant Fcomme nœud le coût le plus bas, nous avons terminé. Notre chemin peut être construit en rétrogradant les nœuds les plus courts précédents.

Algorithme A *

Vous pourriez donc vous demander pourquoi je vous ai expliqué Dijkstra au lieu de l' algorithme A * ? Eh bien, la seule différence réside dans la façon dont vous pesez (ou triez) vos candidats. Avec Dijkstra c'est:

Cost_of_Edge + Cost_of_previous_Node

Avec A * c'est:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Où Estimated_Cost_to_reach_Target_fromest communément appelée une fonction heuristique . C'est une fonction qui essaiera d'estimer le coût pour atteindre le noeud cible. Une bonne fonction heuristique permettra d’atteindre moins de nœuds pour trouver la cible. Bien que l'algorithme de Dijkstra soit étendu à tous les côtés, A * (grâce à l'heuristique) effectuera une recherche dans la direction de la cible.

La page d’Amit sur les heuristiques donne un bon aperçu des heuristiques courantes.

A * path find est une recherche de type best-first qui utilise une heuristique supplémentaire.

La première chose à faire est de diviser votre zone de recherche. Pour cette explication, la carte est une grille carrée de tuiles, car la plupart des jeux 2D utilisent une grille de tuiles et parce que c'est simple à visualiser. Notez cependant que la zone de recherche peut être décomposée de la manière que vous souhaitez: une grille hexagonale, voire des formes arbitraires telles que Risk. Les différentes positions de la carte sont appelées "nœuds" et cet algorithme fonctionnera chaque fois que vous devrez traverser un groupe de nœuds et établir des connexions définies entre eux.

Quoi qu’il en soit, à partir d’une tuile de départ donnée:

• Les 8 tuiles autour de la tuile de départ sont "notées" sur la base a) du coût de déplacement de la tuile actuelle vers la tuile suivante (généralement 1 pour les mouvements horizontaux ou verticaux, sqrt (2) pour les mouvements en diagonale).

• On attribue ensuite à chaque mosaïque un score "heuristique" supplémentaire - une approximation de la valeur relative du déplacement sur chaque mosaïque. Différentes méthodes heuristiques sont utilisées, la plus simple étant la distance en ligne droite entre les centres de la mosaïque et de la mosaïque finale.

• La mosaïque actuelle est alors "fermée" et l'agent passe à la mosaïque voisine qui est ouverte, qui a le score de mouvement le plus bas et le score heuristique le plus bas.

• Ce processus est répété jusqu'à ce que le nœud de l'objectif soit atteint ou jusqu'à ce qu'il n'y ait plus de nœuds ouverts (ce qui signifie que l'agent est bloqué).

Pour les diagrammes illustrant ces étapes, reportez-vous au didacticiel de ce bon débutant .

Certaines améliorations peuvent être apportées, principalement en améliorant l'heuristique:

• Prise en compte des différences de terrain, de la rugosité, de la pente, etc.

• Il est également parfois utile de faire un "balayage" sur la grille pour bloquer les zones de la carte qui ne sont pas des chemins efficaces: une forme de U face à l'agent, par exemple. Sans test de balayage, l'agent entrerait d'abord dans le U, se retournerait, puis partirait et contournerait le bord du U. Un "vrai" agent intelligent noterait le piège en forme de U et l'éviterait simplement. Le balayage peut aider à simuler cela.

C'est loin d'être le meilleur, mais c'est une implémentation que j'ai faite de A * en C ++ il y a quelques années.

Il vaut probablement mieux que je vous indique des ressources plutôt que d'essayer d'expliquer l'intégralité de l'algorithme. De plus, tout en lisant l'article du wiki, jouez avec la démo et voyez si vous pouvez visualiser son fonctionnement. Laissez un commentaire si vous avez une question spécifique.

1. A * sur Wikipedia
2. Une démonstration * Java

L'article d'ActiveTut sur la recherche de chemin peut être utile. Il passe en revue à la fois l'algorithme de A * et celui de Dijkstra et leurs différences. Il est destiné aux développeurs Flash, mais il devrait fournir de bonnes informations sur la théorie, même si vous n'utilisez pas Flash.

Une chose qu'il est important de visualiser quand on traite avec A * et l'algorithme de Dijkstra est que A * est dirigé; il essaie de trouver le chemin le plus court vers un point particulier en "devinant" la direction à suivre. L'algorithme de Dijkstra trouve le chemin le plus court vers / chaque / point.

Donc, juste comme première déclaration, A * est au cœur un algorithme d'exploration de graphes. Habituellement, dans les jeux, nous utilisons les carreaux ou une autre géométrie du monde comme graphique, mais vous pouvez utiliser A * pour d'autres tâches. Les deux algorithmes ur pour la traversée de graphe sont la recherche en profondeur d'abord et la recherche en largeur d'abord. Dans DFS, vous explorez toujours complètement votre branche actuelle avant d'examiner les frères et soeurs du nœud actuel. Dans BFS, vous regardez toujours d'abord les frères et soeurs, puis les enfants. A * essaie de trouver un juste milieu entre ceux-ci lorsque vous explorez une branche (plutôt comme DFS) lorsque vous vous approchez de l'objectif souhaité, mais parfois vous arrêtez et essayez un frère ou une sœur s'il peut obtenir de meilleurs résultats dans sa branche. Le calcul actuel est que vous gardez une liste de nœuds possibles à explorer ensuite où chacun a une "bonté" score indiquant à quel point il est proche (dans un sens abstrait) de l'objectif, les scores les plus faibles étant meilleurs (0 signifie que vous avez trouvé l'objectif). Vous choisissez lequel utiliser ensuite en recherchant le minimum de la partition, plus le nombre de nœuds situés loin de la racine (qui correspond généralement à la configuration actuelle ou à la position actuelle dans pathfinding). Chaque fois que vous explorez un nœud, vous ajoutez tous ses enfants à cette liste, puis choisissez le meilleur.

Sur un plan abstrait, A * fonctionne comme ceci:

• Vous traitez le monde comme un nombre discret de nœuds connectés, par exemple. une grille ou un graphique.
• Pour trouver un chemin à travers ce monde, vous devez trouver une liste de «nœuds» adjacents dans cet espace, menant du début à l'objectif.
• L’approche naïve serait la suivante: calculez toutes les permutations possibles des nœuds qui commencent par le nœud de départ et se terminent au nœud de fin, puis choisissez le moins cher. Cela prendrait évidemment une éternité sur tous les espaces, sauf les plus infimes.
• Par conséquent, des approches alternatives tentent d’utiliser certaines connaissances sur le monde pour deviner quelles permutations méritent d’être examinées en premier, et pour savoir si une solution donnée peut être dépassée. Cette estimation s'appelle une heuristique.
• A * nécessite une heuristique admissible . Cela signifie qu'il ne surestime jamais.
  • La distance euclidienne est une bonne heuristique pour les problèmes de recherche de chemin, car nous savons que le chemin le plus court entre 2 points est une ligne droite. Cela ne surestime jamais la distance dans les simulations du monde réel.
• A * commence par le nœud de départ et essaie les permutations successives de ce nœud plus chaque voisin et les voisins de son voisin, etc., en utilisant l'heuristique pour décider quelle permutation doit être essayée.
• A chaque étape, A * examine le chemin le plus prometteur à ce jour et choisit le prochain nœud voisin qui semble être le "meilleur", en fonction de la distance parcourue jusqu'à présent, et l'estimation heuristique de la distance qui lui reste à parcourir. nœud.
• Parce que l'heuristique ne surestime jamais et que la distance parcourue jusqu'à présent est connue pour être précise, elle sélectionnera toujours l'étape suivante la plus optimiste.
  • Si cette étape suivante atteint l'objectif, vous savez qu'elle a trouvé l'itinéraire le plus court à partir de la dernière position, car il s'agissait de la conjecture la plus optimiste parmi celles qui restaient.
  • S'il n'atteint pas l'objectif, il reste un point à explorer ultérieurement. L'algorithme choisit maintenant la prochaine possibilité la plus prometteuse, de sorte que la logique ci-dessus s'applique toujours.