Comment fonctionne A * pathfinding?

67

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.

Daniel X Moore
la source
Voici un petit article avec un GIF animé qui montre l'algorithme en mouvement de Dijkstra.
Ólafur Waage
Les pages * d'Amit ont été une bonne introduction pour moi. Vous pouvez trouver beaucoup de bonnes visualisations recherchant l' algorithme AStar sur youtube.
jdeseno
Plusieurs explications de A * m'embrouillaient avant de trouver ce formidable tutoriel: policyalmanac.org/games/aStarTutorial.htm J'y ai surtout fait référence lorsque j'ai écrit une implémentation de A * dans ActionScript: newarteest.com/flash /astar.html
Jalousie le
4
-1 wikipedia a l' article sur A * avec l' explication, le code source, la visualisation et ... . Certaines des réponses ici ont des liens externes à partir de cette page wiki.
user712092
4
De plus, comme il s’agit d’un sujet assez complexe et d’un grand intérêt pour les développeurs de jeux, je pense que nous souhaitons obtenir les informations ici. Je me souviens qu'une fois, Joel avait déclaré qu'il souhaitait que StackOverflow soit le produit le plus utilisé lorsque les utilisateurs interrogent Google.
Jhocking

Réponses:

63

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.

Dijkstra's Illustré, 1ère partie

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).

Dijkstra's Illustré, 2ème partie

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) }

Dijkstra est illustré, partie 3

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) }

Dijkstra's Illustré, 4ème partie

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) }

Dijkstra's Illustré, 5ème partie

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) }

Dijkstra's Illustré, 6ème partie

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)

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.

bummzack
la source
2
Il est à noter que l'heuristique ne poussera pas toujours la recherche pour trouver le meilleur itinéraire. Par exemple, si votre heuristique est la distance par rapport à la cible, mais que l'itinéraire viable se situe autour du bord de la carte, la recherche recherchera dans ce cas toute la carte avant d'obtenir le bon itinéraire. Alors sûrement, vous devez penser, il y a quelque chose que je ne comprends pas? Ça ne marche pas! - la chose à comprendre est que le but d'une heuristique est de réduire la recherche dans la plupart des cas, et que votre travail consiste à en trouver une qui soit la «meilleure» parmi toutes les solutions disponibles pour vos besoins spécifiques.
SirYakalot
2
@ AsherEinhorn Il sera toujours meilleur (ou dans le pire des cas égal) qu'une recherche mal informée comme celle de Djikstra.
Bummzack
oui oui, vous avez absolument raison. Je ne savais peut-être pas que ce cas dont j'ai parlé dans le commentaire ci-dessus est un «pire cas» théorique pour A * avec cette heuristique, MAIS c'est ce que Dijkstra ferait CHAQUE FOIS. La plupart du temps, A * sera meilleur, même avec une heuristique très simple. Mon point de vue était que l'heuristique peut être source de confusion au début, car la «distance par rapport à la cible» n'a pas toujours de sens pour tous les scénarios - le fait est que c'est le cas pour la plupart.
SirYakalot
Voir aussi: qiao.github.io/PathFinding.js/visual
David Chouinard
Cette réponse pourrait utiliser une mention de ce qui rend une heuristique admissible, dans le sens de garantir que A * trouvera le chemin le plus court. (Brièvement: pour être admissible, l'heuristique ne doit jamais surestimer la distance réelle par rapport à la cible. Des heuristiques non admissibles peuvent parfois être utiles, mais elles peuvent amener A * à renvoyer des chemins sous-optimaux.)
Ilmari Karonen le
26

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.

Sean James
la source
1
Une explication avec un graphique, des nœuds, des arêtes serait plus claire que les carreaux. Cela ne vous aide pas à comprendre que, quelle que soit la structure spatiale de votre jeu, vous pouvez appliquer le même algorithme dans la mesure où vous avez des informations de positions liées dans cet espace.
Klaim
Je dirais que ce serait moins clair en réalité, car il est plus difficile à visualiser. Mais oui, cette explication devrait indiquer qu’une grille de tuiles n’est pas requise; en fait, je vais modifier ce point.
Jhocking
14

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
David McGraw
la source
4
Votre exemple Python est en C ++.
Buns of Aluminum
@finish - C'est bien de voir quelqu'un attraper ça! Les activités quotidiennes tournent autour de Python ces jours-ci. Merci!
David McGraw
3
Votre exemple en C ++ pourrait aussi bien être C.
deceleratedcaviar Le
4
L'exemple pourrait aussi bien être en assembleur pour toute la structure dont il dispose. Ce n'est même pas A *, comment est-ce la réponse acceptée?
4
Désolé, ce n'est pas à la hauteur, mes camarades, c'était l'une de mes premières tentatives de codage quand j'ai commencé. N'hésitez pas à contribuer quelque chose aux commentaires / modifier le message pour partager votre propre solution.
David McGraw
6

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.

VirtuosiMedia
la source
4

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.

Karantza
la source
1
Ce n'est pas vraiment une description précise de la différence entre A * et Dijkstra. Il est vrai que Dijkstra résout le problème de source unique à tous les points, mais lorsqu'il est utilisé dans les jeux, il est généralement coupé dès que vous trouvez un chemin vers l'objectif. La vraie différence entre les deux réside dans le fait qu'A * est informé par une approche heuristique et peut trouver cet objectif avec moins de branches.
Pour ajouter à l'explication de Joe: A * trouvera également le chemin d'accès à tous les points, si vous le laissez, mais dans les jeux, nous voulons généralement nous arrêter plus tôt. A * fonctionne comme l'algorithme de Dijsktra, sauf que l'heuristique aide à réorganiser les nœuds pour qu'ils explorent d'abord les chemins les plus prometteurs. De cette façon, vous pouvez généralement arrêter même plus tôt qu'avec l'algorithme de Dijkstra. Par exemple, si vous souhaitez rechercher un chemin du centre de la carte vers le côté est, l'algorithme de Dijkstra explorera également toutes les directions et s'arrêtera lorsqu'il trouvera le côté est. A * passera plus de temps à aller à l'est qu'à l'ouest et y arrivera plus tôt.
amitp
3

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.

coderanger
la source
3

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.
Kylotan
la source