Wie funktioniert die A * -Pfadfindung?

67

Ich möchte auf einer fundamentalen Ebene verstehen, wie A * -Pfadfindung funktioniert. Alle Code- oder Pseudo-Code-Implementierungen sowie Visualisierungen wären hilfreich.

Daniel X Moore
quelle
Hier ist ein kleiner Artikel mit einem animierten GIF, das den Dijkstra-Algorithmus in Bewegung zeigt.
Ólafur Waage
Amits A * Pages waren eine gute Einführung für mich. Auf youtube finden Sie viele gute Visualisierungen, die nach AStar-Algorithmus suchen .
Jdeseno
Ich war durch eine Reihe von Erklärungen zu A * verwirrt, bevor ich dieses großartige Tutorial gefunden habe: policyalmanac.org/games/aStarTutorial.htm Ich habe mich hauptsächlich darauf bezogen, als ich eine Implementierung von A * in ActionScript schrieb: newarteest.com/flash /astar.html
jhocking
4
-1 hat Wikipedia - Artikel auf A * mit Erklärung, Quellcode, Visualisierung und ... . Einige der Antworten hier enthalten externe Links von dieser Wiki-Seite.
User712092
4
Da dies ein ziemlich komplexes Thema ist, das für Spieleentwickler von großem Interesse ist, möchten wir die Informationen hier finden. Ich erinnere mich, dass Joel einmal gesagt hat, er wolle, dass StackOverflow der Top-Hit ist, wenn Leute Fragen zur Google-Programmierung haben.
jhocking

Antworten:

63

Haftungsausschluss

Es gibt Unmengen von Codebeispielen und Erklärungen zu A * im Internet. Diese Frage hat auch viele gute Antworten mit vielen nützlichen Links erhalten. In meiner Antwort werde ich versuchen, ein illustriertes Beispiel für den Algorithmus zu liefern, das möglicherweise leichter zu verstehen ist als Code oder Beschreibungen.


Dijkstra's Algorithmus

Um A * zu verstehen, schlage ich vor, dass Sie sich zuerst den Dijkstra-Algorithmus ansehen . Lassen Sie sich von mir durch die Schritte führen, die der Dijkstra-Algorithmus für eine Suche ausführt.

Unser Startknoten ist Aund wir wollen den kürzesten Weg finden F. Mit jeder Kante des Graphen sind Bewegungskosten verbunden (bezeichnet als schwarze Ziffern neben den Kanten). Unser Ziel ist es, die minimalen Reisekosten für jeden Scheitelpunkt (oder Knoten) des Diagramms zu bewerten, bis wir unseren Zielknoten erreichen.

Dijkstra's illustriert, Teil 1

Dies ist unser Ausgangspunkt. Wir müssen einen Listenknoten untersuchen. Diese Liste ist derzeit:

{ A(0) }

Ahat die Kosten von 0, alle anderen Knoten sind auf unendlich gesetzt (in einer typischen Implementierung wäre dies so ähnlich int.MAX_VALUEoder ähnlich).

Dijkstra's illustriert, Teil 2

Wir nehmen den Knoten mit den niedrigsten Kosten aus unserer Knotenliste (da unsere Liste nur enthält A, ist dies unser Kandidat) und besuchen alle seine Nachbarn. Wir setzen die Kosten für jeden Nachbarn auf:

Cost_of_Edge + Cost_of_previous_Node

und verfolgen Sie den vorherigen Knoten (angezeigt als kleiner rosa Buchstabe unter dem Knoten). Akann jetzt als gelöst (rot) markiert werden, damit wir es nicht wieder besuchen. Unsere Kandidatenliste sieht jetzt so aus:

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

Dijkstra's illustriert, Teil 3

Wieder nehmen wir den Knoten mit den niedrigsten Kosten aus unserer Liste ( B) und bewerten seine Nachbarn. Der Pfad zu Dist teurer als die aktuellen Kosten von D, daher kann dieser Pfad verworfen werden. Ewird unserer Kandidatenliste hinzugefügt, die jetzt so aussieht:

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

Dijkstra's illustriert, Teil 4

Der nächste zu untersuchende Knoten ist jetzt D. Die Verbindung zu Ckann verworfen werden, da der Pfad nicht kürzer als die vorhandenen Kosten ist. Wir haben einen kürzeren Weg gefunden E, daher werden die Kosten für Eund den vorherigen Knoten aktualisiert. Unsere Liste sieht jetzt so aus:

{ E(3), C(4) }

Dijkstra's illustriert, Teil 5

Wie zuvor untersuchen wir nun den Knoten mit den niedrigsten Kosten aus unserer Liste E. Ehat nur einen ungelösten Nachbarn, der auch der Zielknoten ist. Die Kosten zum Erreichen des Zielknotens werden auf 10und seines vorherigen Knotens auf festgelegt E. Unsere Kandidatenliste sieht jetzt so aus:

{ C(4), F(10) }

Dijkstra's illustriert, Teil 6

Als nächstes untersuchen wir C. Wir können die Kosten und den vorherigen Knoten für aktualisieren F. Da unsere Liste jetzt den FKnoten mit den niedrigsten Kosten hat, sind wir fertig. Unser Weg kann konstruiert werden, indem die vorherigen kürzesten Knoten zurückverfolgt werden.


Ein * Algorithmus

Sie fragen sich vielleicht, warum ich Ihnen Dijkstra anstelle des A * -Algorithmus erklärt habe ? Der einzige Unterschied besteht darin, wie Sie Ihre Kandidaten wiegen (oder sortieren). Mit Dijkstra ist es:

Cost_of_Edge + Cost_of_previous_Node

Mit A * ist es:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Wo Estimated_Cost_to_reach_Target_fromwird allgemein eine heuristische Funktion genannt. Dies ist eine Funktion, die versucht, die Kosten zum Erreichen des Zielknotens abzuschätzen. Mit einer guten heuristischen Funktion wird erreicht, dass weniger Knoten besucht werden müssen, um das Ziel zu finden. Während sich der Dijkstra-Algorithmus nach allen Seiten ausdehnt, sucht A * (dank der Heuristik) in Richtung des Ziels.

Amits Seite über Heuristiken bietet einen guten Überblick über gängige Heuristiken.

Blödmann
quelle
2
Es ist erwähnenswert, dass die Heuristik nicht immer die Suche nach der besten Route forciert. Wenn Ihre Heuristik beispielsweise die Entfernung zum Ziel ist, sich die realisierbare Route jedoch am Rand der Karte befindet, durchsucht die Suche in diesem Fall die gesamte Karte, bevor die richtige Route ermittelt wird. Dann denkst du sicher, gibt es etwas, das ich nicht verstehe? Das geht nicht! - Zu verstehen ist, dass der Zweck einer Heuristik darin besteht, die Suche in den MEISTEN Fällen zu reduzieren, und dass es Ihre Aufgabe ist, eine Lösung zu finden, die die 'beste' aller verfügbaren Lösungen für Ihre spezifischen Anforderungen darstellt.
SirYakalot
2
@AsherEinhorn Es wird immer noch besser (oder im schlimmsten Fall gleich) sein als eine nicht informierte Suche wie die von Djikstra.
Mistzack
ja ja du hast absolut recht Vielleicht war mir unklar, dass der Fall, über den ich im obigen Kommentar gesprochen habe, ein theoretischer 'Worst-Case'-Fall für A * ist, mit dieser Heuristik, ABER das würde Dijkstra JEDES Mal tun. Meistens ist A * sogar mit einer sehr einfachen Heuristik besser. Mein Punkt war, dass die Heuristik zunächst verwirrend sein kann, weil die Entfernung zum Ziel nicht immer für jedes Szenario Sinn macht - der Punkt ist, dass dies für die meisten der Fall ist.
SirYakalot
Siehe auch: qiao.github.io/PathFinding.js/visual
David Chouinard
Diese Antwort könnte eine Erwähnung dessen gebrauchen, was eine Heuristik in dem Sinne zulässig macht, dass garantiert wird, dass A * den kürzesten Weg findet. (Kurz gesagt: Um zulässig zu sein, darf die Heuristik niemals die tatsächliche Entfernung zum Ziel überschätzen. Nicht zulässige Heuristiken können manchmal nützlich sein, können jedoch dazu führen, dass A * suboptimale Pfade zurückgibt.)
Ilmari Karonen
26

Eine * -Pfadfindung ist eine Suche nach dem besten zuerst, die eine zusätzliche Heuristik verwendet.

Als erstes müssen Sie Ihren Suchbereich aufteilen. Für diese Erklärung ist die Karte ein quadratisches Raster aus Kacheln, da die meisten 2D-Spiele ein Raster aus Kacheln verwenden und dies einfach zu visualisieren ist. Beachten Sie jedoch, dass der Suchbereich beliebig aufgeteilt werden kann: Vielleicht ein Hex-Raster oder sogar beliebige Formen wie Risk. Die verschiedenen Kartenpositionen werden als "Knoten" bezeichnet. Dieser Algorithmus funktioniert immer dann, wenn Sie eine Reihe von Knoten durchlaufen und Verbindungen zwischen den Knoten definiert haben.

Wie auch immer, beginnend mit einem bestimmten Startplättchen:

  • Die 8 Kacheln um die Startkachel werden "gewertet", basierend auf a) den Kosten für den Wechsel von der aktuellen Kachel zur nächsten Kachel (im Allgemeinen 1 für horizontale oder vertikale Bewegungen, sqrt (2) für diagonale Bewegungen).

  • Jedem Plättchen wird dann eine zusätzliche "heuristische" Punktzahl zugewiesen - eine Annäherung an den relativen Wert des Bewegens zu jedem Plättchen. Es werden verschiedene Heuristiken verwendet, wobei die einfachste der geradlinige Abstand zwischen den Mittelpunkten der gegebenen Kachel und der Endkachel ist.

  • Das aktuelle Plättchen wird dann "geschlossen" und der Agent bewegt sich zu dem benachbarten Plättchen, das offen ist, die niedrigste Bewegungsbewertung und die niedrigste heuristische Bewertung hat.

  • Dieser Vorgang wird wiederholt, bis der Zielknoten erreicht ist oder keine offenen Knoten mehr vorhanden sind (dh der Agent ist blockiert).

Diagramme, die diese Schritte veranschaulichen, finden Sie in diesem guten Tutorial für Anfänger .

Es gibt einige Verbesserungen, die hauptsächlich bei der Verbesserung der Heuristik vorgenommen werden können:

  • Berücksichtigung von Geländeunterschieden, Rauheit, Steilheit usw.

  • Manchmal ist es auch nützlich, einen "Sweep" über das Raster auszuführen, um Bereiche der Karte auszublenden, die keine effizienten Pfade sind: z. B. eine U-Form, die dem Agenten zugewandt ist. Ohne einen Wobbeltest würde der Agent zuerst das U betreten, sich umdrehen, dann das U verlassen und um den Rand des U herumgehen. Ein "echter" intelligenter Agent würde die U-förmige Falle bemerken und sie einfach vermeiden. Das Kehren kann dabei helfen, dies zu simulieren.

Sean James
quelle
1
Eine Erklärung mit Graphen, Knoten und Kanten wäre klarer als nur über Kacheln. Es hilft nicht zu verstehen, dass Sie unabhängig von der Raumstruktur Ihres Spiels denselben Algorithmus anwenden können, sofern Sie Positionsinformationen in diesem Raum verknüpft haben.
Klaim
Ich würde argumentieren, dass dies weniger klar wäre, weil es schwieriger ist, sich das vorzustellen. Aber ja, diese Erklärung sollte erwähnen, dass ein Kachelraster nicht erforderlich ist. in der Tat werde ich diesen Punkt in bearbeiten.
jhocking
14

Es ist alles andere als das Beste, aber dies ist eine Implementierung von A * in C ++, die ich vor einigen Jahren gemacht habe.

Es ist wahrscheinlich besser, dass ich Sie auf Ressourcen hinweise, als zu versuchen, den gesamten Algorithmus zu erklären. Spielen Sie beim Lesen des Wiki-Artikels mit der Demo und sehen Sie, ob Sie sich vorstellen können, wie sie funktioniert. Hinterlassen Sie einen Kommentar, wenn Sie eine bestimmte Frage haben.

  1. A * auf Wikipedia
  2. Eine * Java-Demonstration
David McGraw
quelle
4
Ihr Python-Beispiel ist in C ++.
Brötchen aus Aluminium
@finish - Schön zu sehen, dass jemand das fängt! Die alltäglichen Aktivitäten drehen sich heutzutage um Python. Vielen Dank!
David McGraw
3
Ihr C ++ Beispiel könnte auch C sein
deceleratedcaviar
4
Das Beispiel könnte genauso gut in Assembler für all die Struktur sein, die es hat. Es ist nicht einmal A *, wie ist das die akzeptierte Antwort?
4
Entschuldigung, es liegt nicht an Gleichgesinnten, es war einer meiner ersten Codierungsversuche, als ich anfing. Fühlen Sie sich frei, etwas zu den Kommentaren beizutragen / den Beitrag zu bearbeiten, um Ihre eigene Lösung mitzuteilen.
David McGraw
6

Sie könnten ActiveTut Artikel über finden Path Finding nützlich. Es geht sowohl über den A * - als auch über den Dijkstra-Algorithmus und die Unterschiede zwischen ihnen. Es richtet sich an Flash-Entwickler, sollte jedoch einen guten Einblick in die Theorie bieten, auch wenn Sie Flash nicht verwenden.

VirtuosiMedia
quelle
4

Wenn Sie sich mit A * und dem Dijkstra-Algorithmus beschäftigen, ist es wichtig zu visualisieren, dass A * gerichtet ist. es versucht, den kürzesten Weg zu einem bestimmten Punkt zu finden, indem es "errät", in welche Richtung es schauen soll. Der Dijkstra-Algorithmus findet den kürzesten Weg zu / jedem / Punkt.

Karantza
quelle
1
Dies ist keine genaue Beschreibung des Unterschieds zwischen A * und Dijkstra. Es ist wahr, dass Dijkstra alle Punkte aus einer Hand löst, aber wenn es in Spielen verwendet wird, wird es normalerweise abgeschnitten, sobald Sie einen Weg zum Ziel finden. Der wirkliche Unterschied zwischen den beiden besteht darin, dass A * durch die Heuristik informiert wird und dieses Ziel mit weniger Verzweigungen finden kann.
Um Joes Erklärung zu ergänzen: A * findet auch den Pfad zu allen Punkten, wenn Sie es zulassen, aber in Spielen möchten wir normalerweise vorzeitig aufhören. A * funktioniert wie der Dijsktra-Algorithmus, mit der Ausnahme, dass die Heuristik dabei hilft, die Knoten neu anzuordnen, um zuerst die vielversprechendsten Pfade zu erkunden. Auf diese Weise können Sie in der Regel sogar früher als mit dem Dijkstra-Algorithmus anhalten. Wenn Sie beispielsweise einen Pfad von der Kartenmitte zur Ostseite suchen möchten, durchsucht der Dijkstra-Algorithmus alle Richtungen gleich und stoppt, wenn er die Ostseite findet. Ein * wird mehr Zeit damit verbringen, nach Osten als nach Westen zu gehen und dort früher anzukommen.
amitp
3

A * ist also genau wie eine erste Aussage ein Graph-Explorations-Algorithmus. Normalerweise verwenden wir in Spielen entweder Kacheln oder eine andere Weltgeometrie als Grafik, aber Sie können A * für andere Dinge verwenden. Die beiden Ur-Algorithmen für das Durchlaufen von Graphen sind Tiefensuche und Breitensuche. In DFS durchsuchen Sie Ihren aktuellen Zweig immer vollständig, bevor Sie sich die Geschwister des aktuellen Knotens ansehen, und in BFS betrachten Sie immer zuerst die Geschwister und dann die Kinder. A * versucht, einen Mittelweg zwischen diesen zu finden, auf dem Sie einen Zweig erkunden (eher wie DFS), wenn Sie sich dem gewünschten Ziel nähern, aber manchmal anhalten und ein Geschwister versuchen, wenn es in seinem Zweig bessere Ergebnisse erzielt. Die eigentliche Mathematik ist, dass Sie eine Liste möglicher Knoten führen, um als nächstes zu erkunden, wo jeder eine "Güte" hat. Punktzahl, die angibt, wie nahe (in gewisser Weise abstrakt) das Ziel liegt, wobei niedrigere Punktzahlen besser sind (0 würde bedeuten, dass Sie das Ziel gefunden haben). Sie wählen aus, welche Option als Nächstes verwendet werden soll, indem Sie das Minimum der Punktzahl plus die Anzahl der vom Stamm entfernten Knoten ermitteln (wobei es sich im Allgemeinen um die aktuelle Konfiguration oder die aktuelle Position bei der Pfadfindung handelt). Jedes Mal, wenn Sie einen Knoten durchsuchen, fügen Sie dieser Liste alle untergeordneten Knoten hinzu und wählen dann den neuen besten aus.

coderanger
quelle
3

Auf einer abstrakten Ebene funktioniert A * wie folgt:

  • Sie behandeln die Welt als eine diskrete Anzahl verbundener Knoten, z. ein Gitter oder ein Diagramm.
  • Um einen Weg durch diese Welt zu finden, müssen Sie eine Liste benachbarter 'Knoten' in diesem Raum finden, die vom Anfang bis zum Ziel führt.
  • Der naive Ansatz wäre: Berechnen Sie jede mögliche Permutation von Knoten, die mit dem Startknoten beginnen und am Endknoten enden, und wählen Sie den günstigsten aus. Dies würde offensichtlich bis auf die kleinsten Räume ewig dauern.
  • Daher versuchen alternative Ansätze, mit etwas Wissen über die Welt zu erraten, welche Permutationen es wert sind, zuerst in Betracht gezogen zu werden, und zu wissen, ob eine bestimmte Lösung geschlagen werden kann. Diese Schätzung wird als Heuristik bezeichnet.
  • Ein * erfordert eine zulässige Heuristik . Dies bedeutet, dass es nie überschätzt.
    • Eine gute Heuristik für Pfadfindungsprobleme ist die euklidische Entfernung, da wir wissen, dass die kürzeste Route zwischen zwei Punkten eine gerade Linie ist. Dies überschätzt niemals die Distanz in realen Simulationen.
  • Ein * beginnt mit dem Startknoten und versucht sukzessive Permutationen dieses Knotens plus jedes Nachbarn und der Nachbarn seines Nachbarn usw., wobei die Heuristik verwendet wird, um zu entscheiden, welche Permutation als nächstes versucht werden soll.
  • Bei jedem Schritt sucht A * den bisher vielversprechendsten Pfad und sucht den nächsten benachbarten Knoten, der basierend auf der bisher zurückgelegten Entfernung und der Schätzung der Heuristik, wie viel davon noch übrig wäre, als am besten heraus Knoten.
  • Da die Heuristik niemals überschätzt und die bisher zurückgelegte Strecke als genau bekannt ist, wählt sie immer den optimistischsten nächsten Schritt.
    • Wenn dieser nächste Schritt das Ziel erreicht, wissen Sie, dass er von der letzten Position aus den kürzesten Weg gefunden hat, da dies die optimistischste Vermutung der verbleibenden gültigen war.
    • Wenn es das Ziel nicht erreicht hat, bleibt es als möglicher Punkt für spätere Erkundungen übrig. Der Algorithmus wählt nun die nächstversprechendste Möglichkeit aus, sodass die obige Logik weiterhin gilt.
Kylotan
quelle