Suche…


Einführung

Dieses Thema konzentriert sich auf den A * Pathfinding-Algorithmus, wie er verwendet wird und warum er funktioniert.

Hinweis für zukünftige Mitwirkende: Ich habe ein Beispiel für A * Pathfinding ohne Hindernisse in einem 4x4-Gitter hinzugefügt. Ein Beispiel mit Hindernissen wird noch benötigt.

Einfaches Beispiel für A * Pathfinding: Ein Labyrinth ohne Hindernisse

Nehmen wir an, wir haben das folgende 4: 4-Raster:

Beginn des 4x4-Gitters

Nehmen wir an, dies ist ein Irrgarten . Es gibt jedoch keine Mauern / Hindernisse. Wir haben nur einen Startpunkt (das grüne Quadrat) und einen Endpunkt (das rote Quadrat). Nehmen wir auch an, dass wir uns nicht diagonal bewegen können, um von grün nach rot zu gelangen. Schauen wir uns also vom grünen Quadrat aus an, zu welchen Feldern wir gehen können, und heben Sie sie blau hervor:

Gitter 2

Um zu entscheiden, welches Feld als nächstes bewegt werden soll, müssen wir 2 Heuristiken berücksichtigen:

  1. Der "g" -Wert - Dies ist, wie weit dieser Knoten vom grünen Quadrat entfernt ist.
  2. Der "h" -Wert - Dies ist, wie weit dieser Knoten vom roten Quadrat entfernt ist.
  3. Der "f" -Wert - Dies ist die Summe aus dem "g" -Wert und dem "h" -Wert. Dies ist die letzte Zahl, die uns sagt, zu welchem ​​Knoten wir gehen sollen.

Um diese Heuristiken zu berechnen, verwenden wir folgende Formel: distance = abs(from.x - to.x) + abs(from.y - to.y)

Dies ist als "Manhattan Distance" -Formel bekannt.

Wir berechnen den "g" -Wert für das blaue Quadrat unmittelbar links vom grünen Quadrat: abs(3 - 2) + abs(2 - 2) = 1

Großartig! Wir haben den Wert: 1. Versuchen wir nun den Wert "h" zu berechnen: abs(2 - 0) + abs(2 - 0) = 4

Perfekt. Lassen Sie uns nun den "f" -Wert erhalten: 1 + 4 = 5

Der endgültige Wert für diesen Knoten ist also "5".

Machen wir dasselbe für alle anderen blauen Quadrate. Die große Zahl in der Mitte jedes Quadrats ist der Wert "f", während die Zahl oben links der Wert "g" und die Zahl oben rechts der Wert "h" ist:

Gitter Nr. 3

Wir haben die g-, h- und f-Werte für alle blauen Knoten berechnet. Nun, welche wählen wir aus?

Welcher auch immer den niedrigsten f-Wert hat.

In diesem Fall haben wir jedoch 2 Knoten mit demselben f-Wert. 5. Wie wählen wir zwischen ihnen aus?

Wählen Sie einfach eine nach dem Zufallsprinzip aus, oder legen Sie eine Priorität fest. Ich ziehe es vor, eine Priorität wie diese zu haben: "Right> Up> Down> Left"

Einer der Knoten mit dem f-Wert von 5 führt uns in Richtung "Abwärts" und der andere bringt uns nach "Links". Da Down eine höhere Priorität hat als Left, wählen wir das Quadrat, das uns "Down" bringt.

Ich markiere nun die Knoten, für die wir die Heuristiken berechnet haben, aber nicht verschoben haben, als orangefarbene Knoten und den Knoten, den wir als Cyan ausgewählt haben:

Gitter Nr. 4

Okay, lassen Sie uns jetzt die gleichen Heuristiken für die Knoten um den Cyan-Knoten berechnen:

Gitter Nr. 5

Wieder wählen wir den Knoten aus, der vom Cyan-Knoten aus nach unten geht, da alle Optionen denselben f-Wert haben:

Gitter Nr. 6

Berechnen Sie die Heuristiken für den einzigen Nachbarn, den der Cyan-Knoten hat:

Gitter Nr. 7

In Ordnung, da wir dem gleichen Muster folgen werden, haben wir Folgendes beachtet:

Gitter Nr. 8

Lassen Sie uns noch einmal die Heuristiken für den Nachbarn des Knotens berechnen:

Raster Nr. 9

Lass uns dorthin ziehen:

Raster Nr. 10

Schließlich können wir sehen, dass wir ein Gewinnerfeld neben uns haben, also ziehen wir dorthin und sind fertig.



Modified text is an extract of the original Stack Overflow Documentation
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow