algorithm
Ein * Pathfinding-Algorithmus

Einführung

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

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

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:

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:

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:

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

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

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

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

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

Lass uns dorthin ziehen:

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