Teil 1. Allgemeiner Suchalgorithmus
Einführung
Einen Pfad zu finden ist eines der Themen, die für Spieleentwickler normalerweise am schwierigsten sind. Besonders schlecht verstehen die Leute den
A * -Algorithmus und viele denken, dass dies eine Art unverständliche Magie ist.
Der Zweck dieses Artikels ist es, die Suche nach dem Pfad im Allgemeinen und
A * im Besonderen auf sehr verständliche und zugängliche Weise zu erläutern und damit dem weit verbreiteten Missverständnis ein Ende zu setzen, dass dieses Thema komplex ist. Mit der richtigen Erklärung ist alles ganz einfach.
Bitte beachten Sie, dass wir in diesem Artikel die Suche nach einem Weg
für Spiele betrachten werden . Im Gegensatz zu eher wissenschaftlichen Artikeln werden Suchalgorithmen wie "Tiefe zuerst" oder "Breite zuerst" weggelassen. Stattdessen werden wir versuchen, so schnell wie möglich von Null auf
A * zu gelangen.
Im ersten Teil werden die einfachsten Konzepte zum Finden eines Pfades erläutert. Wenn Sie diese Grundkonzepte verstehen, werden Sie feststellen, dass
A * überraschend offensichtlich ist.
Einfache Schaltung
Obwohl Sie diese Konzepte auf beliebig komplexe 3D-Umgebungen anwenden können, beginnen wir mit einem äußerst einfachen Schema: einem 5 x 5-Quadrat-Raster. Der Einfachheit halber habe ich jede Zelle mit einem Großbuchstaben markiert.
Einfaches Netz.Das allererste, was wir tun werden, ist, uns diese Umgebung als Grafik vorzustellen. Ich werde nicht im Detail erklären, was ein Graph ist; Einfach ausgedrückt ist dies eine Reihe von Kreisen, die durch Pfeile verbunden sind. Die Kreise werden
"Knoten" genannt, und die Pfeile werden
"Kanten" genannt.Jeder Knoten repräsentiert einen
"Zustand", in dem sich das Zeichen befinden kann. In unserem Fall ist der Status des Charakters seine Position, daher erstellen wir einen Knoten für jede Gitterzelle:
Knoten, die Gitterzellen darstellen.Fügen Sie nun die Rippen hinzu. Sie geben die Zustände an, die von jedem gegebenen Zustand
"erreicht" werden können; In unserem Fall können wir von jeder Zelle zur nächsten wechseln, mit Ausnahme der blockierten:
Bögen bezeichnen zulässige Bewegungen zwischen Gitterzellen.Wenn wir von
A nach
B gelangen können , sagen wir, dass
B ein
„Nachbar“ des
A- Knotens ist.
Es ist erwähnenswert, dass die Rippen eine
Richtung haben ; Wir brauchen Kanten von
A nach
B und von
B nach
A. Dies mag überflüssig erscheinen, aber nicht, wenn komplexere „Bedingungen“ auftreten können. Zum Beispiel kann ein Charakter vom Dach auf den Boden fallen, kann aber nicht vom Boden auf das Dach springen. Sie können vom Zustand "lebendig" in den Zustand "tot" wechseln, aber nicht umgekehrt. Usw.
Beispiel
Angenommen, wir möchten von
A nach
T wechseln
. Wir beginnen mit
A. Sie können genau zwei Aktionen ausführen: Gehen Sie zu
B oder gehen Sie zu
F.Nehmen wir an, wir sind nach
B gezogen. Jetzt können wir zwei Dinge tun: zu
A zurückkehren oder zu
C gehen
. Wir erinnern uns, dass wir bereits in
A waren und die Optionen dort in Betracht gezogen haben, daher macht es keinen Sinn, es erneut zu tun (andernfalls können wir den ganzen Tag damit verbringen,
A →
B →
A →
B ... zu bewegen). Deshalb gehen wir zu
C.Wenn wir in
C sind , können wir uns nirgendwo bewegen. Die Rückkehr zu
B ist sinnlos, das heißt, es ist eine Sackgasse. Den Übergang zu
B zu wählen, als wir in
A waren, war eine schlechte Idee; Vielleicht solltest du stattdessen
F versuchen?
Wir wiederholen diesen Vorgang nur so lange, bis wir in
T landen
. In diesem Moment erstellen wir einfach den Pfad von
A neu und kehren in unseren Schritten zurück. Wir sind in
T ; Wie sind wir dorthin gekommen? Von
o ? Das heißt, das Ende des Pfades hat die Form
O →
T. Wie sind wir zu
O gekommen ? Usw.
Denken Sie daran, dass wir uns nicht wirklich
bewegen . Das alles war nur ein Denkprozess. Wir stehen weiterhin in
A und werden uns nicht davon entfernen, bis wir den ganzen Weg gefunden haben. Wenn ich "nach
B gezogen " sage, meine ich "stell dir vor, wir sind nach
B gezogen ".
Allgemeiner Algorithmus
Dieser Abschnitt ist der wichtigste Teil des gesamten Artikels . Sie
müssen es unbedingt verstehen, um die Suche nach dem Weg realisieren zu können; Der Rest (einschließlich
A * ) sind nur Details. In diesem Abschnitt werden Sie verstehen, bis Sie
die Bedeutung verstehen .
Darüber hinaus ist dieser Abschnitt unglaublich einfach.
Versuchen wir, unser Beispiel zu formalisieren und es in einen Pseudocode umzuwandeln.
Wir müssen die Knoten verfolgen, die wir vom Startknoten aus erreichen können. Zu Beginn ist dies nur der Startknoten, aber beim „Erkunden“ des Rasters lernen wir, wie Sie zu anderen Knoten gelangen. Nennen wir diese Liste der
reachable Knoten:
reachable = [start_node]
Wir müssen auch die bereits überprüften Knoten verfolgen, um sie nicht erneut zu berücksichtigen. Nennen
explored sie
explored :
explored = []
Als nächstes werde ich den Kern des Algorithmus skizzieren : Bei jedem Schritt der Suche wählen wir einen der Knoten aus, die wir erreichen können, und schauen uns an, welche neuen Knoten wir daraus erhalten können. Wenn wir bestimmen, wie der letzte (Ziel-) Knoten erreicht werden soll, ist das Problem gelöst! Ansonsten setzen wir die Suche fort.
So einfach, was enttäuscht überhaupt? Und das ist wahr. Aber das ist der ganze Algorithmus. Schreiben wir es Schritt für Schritt mit Pseudocode auf.
Wir suchen weiter, bis wir entweder zum Endknoten gelangen (in diesem Fall finden wir den Pfad vom Anfangsknoten zum Endknoten) oder bis uns die Knoten ausgehen, in denen Sie suchen können (in diesem Fall gibt es keinen Weg zwischen dem Start- und dem Endknoten). .
while reachable is not empty:
Wir wählen einen der Knoten aus, zu denen wir gelangen können und der noch nicht untersucht wurde:
node = choose_node(reachable)
Wenn wir gerade gelernt haben, wie man zum letzten Knoten kommt, ist die Aufgabe abgeschlossen! Wir müssen nur den Pfad erstellen, indem wir den
previous Links zurück zum Startknoten folgen:
if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path
Es macht keinen Sinn, den Knoten mehr als einmal zu untersuchen, daher werden wir Folgendes verfolgen:
reachable.remove(node) explored.add(node)
Wir identifizieren Knoten, die wir von hier aus nicht erreichen können. Wir beginnen mit einer Liste von Knoten neben dem aktuellen und löschen die bereits untersuchten Knoten:
new_reachable = get_adjacent_nodes(node) - explored
Wir nehmen jeden von ihnen:
for adjacent in new_reachable:
Wenn wir bereits wissen, wie wir den Knoten erreichen können, ignorieren Sie ihn. Andernfalls fügen Sie es der
reachable Liste hinzu und verfolgen Sie, wie es hineingekommen ist:
if adjacent not in reachable: adjacent.previous = node
Das Finden des Endknotens ist eine Möglichkeit, die Schleife zu verlassen. Das zweite ist, wenn das
reachable leer wird: Wir haben keine Knoten mehr, die erkundet werden können, und wir haben den Endknoten nicht erreicht, dh es gibt keinen Weg vom Anfang zum Endknoten:
return None
Und ... das war's. Dies ist der gesamte Algorithmus, und der Pfadkonstruktionscode wird in einer separaten Methode zugewiesen:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Hier ist die Funktion, die den Pfad erstellt und den
previous Links zurück zum Startknoten folgt:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Das ist alles.
Dies ist der Pseudocode
jedes Pfadsuchalgorithmus, einschließlich
A * .
Lesen Sie diesen Abschnitt erneut, bis Sie verstanden haben, wie alles funktioniert und, was noch wichtiger ist,
warum alles funktioniert. Es wäre ideal, ein Beispiel von Hand auf Papier zu zeichnen, aber Sie können sich auch eine interaktive Demo ansehen:
Interaktive Demo
Hier ist eine Demo und ein Beispiel für die Implementierung des oben gezeigten Algorithmus (Sie können ihn auf der
Seite des Originalartikels ausführen).
choose_node wählt nur einen zufälligen Knoten aus. Sie können den Algorithmus Schritt für Schritt starten und die Liste der
reachable und
explored sowie die Verweise auf die
previous Links anzeigen.
Beachten Sie, dass die Suche beendet wird, sobald ein Pfad erkannt wird. Es kann vorkommen, dass einige Knoten nicht einmal berücksichtigt werden.
Fazit
Der hier vorgestellte Algorithmus ist ein allgemeiner Algorithmus für
jeden Pfadsuchalgorithmus.
Aber was unterscheidet jeden Algorithmus von einem anderen, warum ist
A * A * ?
Hier ist ein Tipp: Wenn Sie die Suche in der Demo mehrmals ausführen, werden Sie feststellen, dass der Algorithmus nicht immer denselben Pfad findet. Er findet
einen Weg, und dieser Weg ist nicht unbedingt der
kürzeste . Warum?
Teil 2. Suchstrategien
Wenn Sie den im vorherigen Abschnitt beschriebenen Algorithmus nicht vollständig verstehen, kehren Sie zu ihm zurück und lesen Sie ihn erneut, da dies zum Verständnis weiterer Informationen erforderlich ist. Wenn Sie es herausfinden, erscheint Ihnen
A * völlig natürlich und logisch.
Geheime Zutat
Am Ende des vorherigen Teils habe ich zwei Fragen offen gelassen: Wenn jeder Suchalgorithmus denselben Code verwendet, warum verhält sich
A * dann wie
A * ? Und warum findet die Demo manchmal andere Wege?
Die Antworten auf beide Fragen hängen miteinander zusammen. Obwohl der Algorithmus gut definiert ist, habe ich einen Aspekt ungelöst gelassen, und wie sich herausstellt, ist er der Schlüssel zur Erklärung des Verhaltens von Suchalgorithmen:
node = choose_node(reachable)
Es ist diese unschuldig aussehende Zeichenfolge, die alle Suchalgorithmen voneinander unterscheidet.
choose_node hängt von der Implementierungsmethode von
choose_node .
Warum findet die Demo unterschiedliche Wege? Weil die Methode
choose_node einen Knoten zufällig auswählt.
Länge ist wichtig
Bevor wir uns mit den Unterschieden im Verhalten der Funktion
choose_node , müssen wir ein kleines Versehen in dem oben beschriebenen Algorithmus beheben.
Bei der Betrachtung der an den Strom angrenzenden Knoten haben wir diejenigen ignoriert, die bereits wissen, wie dies erreicht werden kann:
if adjacent not in reachable: adjacent.previous = node
Dies ist ein Fehler: Was wäre, wenn wir gerade den
besten Weg finden würden, dorthin zu gelangen? In diesem Fall muss die
previous Knotenverbindung geändert werden, um diesen kürzeren Pfad widerzuspiegeln.
Dazu müssen wir die Länge des Pfades vom Startknoten zu jedem erreichbaren Knoten kennen. Wir werden dies die Kosten des Pfades nennen. Im Moment gehen wir davon aus, dass der Wechsel von einem Knoten zu einem der benachbarten Knoten konstante Kosten von
1 .
Bevor wir mit der Suche beginnen, weisen wir den
cost jedes Knotens der
infinity . Dank dessen wird
jeder Weg kürzer sein. Wir werden auch die
cost den Knoten
start_node auf
0 .
Dann sieht der Code folgendermaßen aus:
if adjacent not in reachable: reachable.add(adjacent)
Gleiche Suchkosten
Schauen wir uns nun die Methode
choose_node . Wenn wir versuchen, den kürzestmöglichen Weg zu finden, ist es keine gute Idee, einen Knoten zufällig auszuwählen.
Es ist besser, einen Knoten auszuwählen, den wir vom Anfangsknoten auf dem kürzesten Weg erreichen können. Aus diesem Grund bevorzugen wir in der Regel kürzere Wege gegenüber längeren. Dies bedeutet nicht, dass längere Pfade überhaupt nicht berücksichtigt werden, sondern dass kürzere Pfade zuerst berücksichtigt werden. Da der Algorithmus unmittelbar nach dem Finden eines geeigneten Pfades beendet wird, sollten wir kurze Pfade finden können.
Hier ist ein mögliches Beispiel für die Funktion
choose_node :
function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node
Intuitiv erweitert sich die Suche nach diesem Algorithmus "radial" vom Startknoten bis zum Endknoten. Hier ist
eine interaktive Demo dieses Verhaltens:
Fazit
Eine einfache Änderung der Methode zur Auswahl des Knotens, die im Folgenden berücksichtigt wird, ermöglichte es uns, einen ziemlich guten Algorithmus zu erhalten: Er findet den kürzesten Weg vom Start- zum Endknoten.
Aber dieser Algorithmus bleibt bis zu einem gewissen Grad "dumm". Er sucht überall weiter, bis er auf einen Endknoten stößt. Was ist beispielsweise der Punkt in dem oben gezeigten Beispiel, um in Richtung
A zu suchen, wenn es offensichtlich ist, dass wir uns vom Endknoten entfernen?
Ist es möglich,
choose_node intelligenter zu machen? Können wir
die Suche auf den Endknoten richten , ohne vorher den richtigen Pfad zu kennen?
Es stellt sich heraus, dass wir es können - im nächsten Teil gelangen wir schließlich zu
choose_node , wodurch wir den allgemeinen Pfad-Suchalgorithmus in
A * choose_node können.
Teil 3. Entfernen Sie den Schleier der Geheimhaltung von A *
Der im vorherigen Teil erhaltene Algorithmus ist recht gut: Er findet den kürzesten Weg vom Startknoten zum letzten. Er verschwendet jedoch seine Energie: Er betrachtet die Art und Weise, wie eine Person offensichtlich als falsch bezeichnet - sie
bewegt sich normalerweise vom Ziel
weg . Wie kann dies vermieden werden?
Magischer Algorithmus
Stellen Sie sich vor, wir führen einen Suchalgorithmus auf einem speziellen Computer mit einem Chip aus, der
Magie kann . Dank dieses erstaunlichen Chips können wir
choose_node sehr einfache Weise ausdrücken, wodurch garantiert der kürzeste Pfad erstellt wird, ohne Zeit damit zu verschwenden,
choose_node erkunden, die nirgendwohin führen:
function choose_node (reachable): return magic(reachable, " , ")
Klingt verlockend, aber Magic Chips benötigen immer noch eine Art Low-Level-Code. Hier ist eine gute Annäherung:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, " ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Dies ist eine großartige Möglichkeit, den nächsten Knoten auszuwählen: Sie wählen einen Knoten aus, der uns den kürzesten Weg vom Start- zum Endknoten bietet, was wir brauchen.
Wir haben auch die Menge an Magie minimiert: Wir wissen genau, wie
node.cost die Kosten für den Umzug vom Startknoten zu jedem Knoten sind (dies ist
node.cost ), und wir verwenden Magie nur, um die Kosten für den Umzug vom Knoten zum Endknoten vorherzusagen.
Nicht magisch, aber ziemlich großartig A *
Leider sind Magic Chips neu und wir brauchen Unterstützung von veralteten Geräten. Der größte Teil des Codes passt zu uns, mit Ausnahme dieser Zeile:
Das heißt, wir können keine Magie verwenden, um die Kosten eines unerforschten Pfades herauszufinden. Dann machen wir eine Vorhersage. Wir werden optimistisch sein und annehmen, dass zwischen dem aktuellen und dem endgültigen Knoten nichts ist, und wir können uns einfach direkt bewegen:
cost_node_to_goal = distance(node, goal_node)
Beachten Sie, dass der
kürzeste Weg und der
Mindestabstand unterschiedlich sind: Der Mindestabstand impliziert, dass zwischen dem aktuellen und dem Endknoten absolut keine Hindernisse bestehen.
Diese Schätzung ist recht einfach zu erhalten. In unseren Gitterbeispielen ist dies der
Abstand von Stadtblöcken zwischen zwei Knoten (d. H.
abs(Ax - Bx) + abs(Ay - By) ). Wenn wir uns diagonal bewegen könnten, wäre der Wert gleich
sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) und so weiter. Am wichtigsten ist, dass wir niemals eine
zu hohe Wertschätzung erhalten.
Hier ist also eine nicht
choose_node Version von
choose_node :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Eine Funktion, die die Entfernung vom Strom zum Endknoten schätzt, wird als
Heuristik bezeichnet , und dieser Suchalgorithmus, meine Damen und Herren, wird als ...
A * bezeichnet .
Interaktive Demo
Während Sie sich von dem Schock erholen, der durch die Erkenntnis verursacht wurde, dass das mysteriöse
A * tatsächlich
so einfach ist , können Sie sich die Demo ansehen (oder sie im
Originalartikel ausführen). Sie werden feststellen, dass die Suche im Gegensatz zum vorherigen Beispiel nur sehr wenig Zeit damit verbringt, sich in die falsche Richtung zu bewegen.
Fazit
Schließlich kamen wir zum
A * -Algorithmus, der nichts anderes ist als der im ersten Teil des Artikels beschriebene allgemeine Suchalgorithmus mit einigen im zweiten Teil beschriebenen Verbesserungen und unter Verwendung der Funktion
choose_node , die den Knoten auswählt, der uns nach unserer Schätzung näher bringt Endknoten. Das ist alles.
Hier ist ein vollständiger Pseudocode der Hauptmethode als Referenz:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
build_path Methode:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Und hier ist die Methode
choose_node , die daraus
A * macht :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Das ist alles.
Aber warum brauchen wir
Teil 4 ?
Nachdem Sie nun verstanden haben, wie
A * funktioniert, möchte ich auf einige erstaunliche Bereiche seiner Anwendung eingehen, die weit davon entfernt sind, Pfade in einem Zellenraster zu finden.
Teil 4. A * in der Praxis
Die ersten drei Teile des Artikels beginnen mit den Grundlagen der Pfadsuchalgorithmen und enden mit einer klaren Beschreibung des
A * -Algorithmus. All dies ist theoretisch großartig, aber zu verstehen, wie dies in der Praxis anwendbar ist, ist ein völlig anderes Thema.
Was passiert zum Beispiel, wenn unsere Welt kein Gitter ist?
Was ist, wenn sich ein Charakter nicht sofort um 90 Grad drehen kann?
Wie erstelle ich ein Diagramm, wenn die Welt endlos ist?
Was ist, wenn uns die Länge des Weges egal ist, wir aber auf Sonnenenergie angewiesen sind und so viel wie möglich unter Sonnenlicht stehen müssen?
Wie finde ich den kürzesten Weg zu einem der beiden Endknoten?
Kostenfunktion
In den ersten Beispielen haben wir nach dem kürzesten Weg zwischen dem Start- und dem Endknoten gesucht. Anstatt jedoch Teilpfadlängen in der variablen
length speichern, haben wir es
cost . Warum?
Wir können
A * nicht nur nach dem
kürzesten , sondern auch nach dem
besten Weg suchen lassen, und die Definition von „am besten“ kann basierend auf unseren Zielen gewählt werden. Wenn wir den kürzesten Weg benötigen, sind die Kosten die Länge des Weges. Wenn wir jedoch beispielsweise den Kraftstoffverbrauch minimieren möchten, müssen wir ihn als Kosten verwenden. Wenn wir die „Zeit unter der Sonne“ maximieren möchten, sind die Kosten die Zeit ohne Sonne. Usw.
Im allgemeinen Fall bedeutet dies, dass jeder Kante des Diagramms entsprechende Kosten zugeordnet sind. In den oben gezeigten Beispielen wurde der Wert implizit festgelegt und immer als
1 , da wir die Schritte auf dem Weg gezählt haben. Aber wir können die Kosten der Rippe entsprechend dem ändern, was wir minimieren möchten.
Kriteriumsfunktion
Nehmen wir an, unser Objekt ist ein Auto, und er muss zur Tankstelle. Jegliches Auftanken passt zu uns. Es ist der kürzeste Weg zur nächsten Tankstelle.
Der naive Ansatz besteht darin, nacheinander den kürzesten Weg zu jeder Betankung zu berechnen und den kürzesten auszuwählen. Dies wird funktionieren, aber es wird ein ziemlich kostspieliger Prozess sein.
Was wäre, wenn wir einen
goal_node durch eine Methode ersetzen
goal_node , die auf einem bestimmten Knoten erkennen kann, ob er endlich ist oder nicht. Dank dessen können wir gleichzeitig nach mehreren Zielen suchen. Wir müssen auch die Heuristik so ändern, dass sie die geschätzten Mindestkosten aller möglichen Endknoten zurückgibt.
Abhängig von den Besonderheiten der Situation können wir das Ziel möglicherweise nicht
perfekt erreichen , oder es kostet zu viel (wenn wir den Charakter durch eine halbe große Karte senden, ist der Unterschied einen Zoll wichtig?). Die Methode
is_goal_node kann also
true wenn wir Wir sind "nah genug".
Volle Sicherheit ist nicht erforderlich.
Die Darstellung der Welt als diskretes Gitter reicht für viele Spiele möglicherweise nicht aus. Nehmen Sie zum Beispiel einen Ego-Shooter oder ein Rennspiel. Die Welt ist diskret, kann aber nicht als Gitter dargestellt werden.
Aber es gibt ein ernsthafteres Problem: Was ist, wenn die Welt endlos ist? In diesem Fall können wir, selbst wenn wir es in Form eines Gitters darstellen können, einfach kein dem Gitter entsprechendes Diagramm erstellen, da es unendlich sein muss.
Es ist jedoch nicht alles verloren. Natürlich brauchen wir für den Graph-Suchalgorithmus definitiv einen Graph. Aber niemand sagte, dass die Grafik
umfassend sein sollte !
Wenn Sie sich den Algorithmus genau ansehen, werden Sie feststellen, dass wir mit dem gesamten Diagramm nichts anfangen. Wir untersuchen den Graphen lokal und erhalten Knoten, die wir vom betreffenden Knoten aus erreichen können. Wie aus der Demo
A * ersichtlich ist, werden einige Knoten des Graphen überhaupt nicht untersucht.
Warum erstellen wir das Diagramm nicht einfach im Forschungsprozess?
Wir machen die aktuelle Position des Charakters zum Startknoten. Beim Aufrufen von
get_adjacent_nodes kann ermittelt werden, auf welche Weise sich der Charakter von einem bestimmten Knoten aus bewegen und im
get_adjacent_nodes benachbarte Knoten erstellen kann.
Jenseits von drei Dimensionen
Auch wenn Ihre Welt
wirklich ein 2D-Netz ist, müssen andere Aspekte berücksichtigt werden. Was ist zum Beispiel, wenn sich ein Zeichen nicht sofort um 90 oder 180 Grad drehen kann, wie dies normalerweise der Fall ist?
Der von jedem Suchknoten dargestellte
Zustand muss nicht nur eine
Position sein . im Gegenteil, es kann einen beliebig komplexen Satz von Werten enthalten. Wenn beispielsweise 90-Grad-Drehungen so lange dauern wie der Übergang von einer Zelle zur anderen, kann der Status des Charakters als
[position, heading] . Jeder Knoten kann nicht nur die Position des Charakters darstellen, sondern auch die Richtung seines Blicks. und die neuen Kanten des Diagramms (explizit oder indirekt) spiegeln dies wider.
Wenn Sie zum ursprünglichen 5x5-Raster zurückkehren, kann die anfängliche Suchposition jetzt
[A, East] . Die benachbarten Knoten sind jetzt
[B, East] und
[A, South] Wenn wir
F erreichen möchten, müssen wir zuerst die Richtung so anpassen, dass der Pfad die Form
[A, East] ,
[A, South] ,
[F, South] .
Ego-Shooter? Mindestens vier Dimensionen:
[X, Y, Z, Heading] . Vielleicht sogar
[X, Y, Z, Heading, Health, Ammo] .
Beachten Sie, dass die heuristische Funktion umso komplexer sein sollte, je komplexer der Zustand ist.
A * selbst ist einfach; Kunst entsteht oft aus guten Heuristiken.
Fazit
Der Zweck dieses Artikels ist es, den Mythos ein für alle Mal zu zerstreuen, dass
A * ein mystischer Algorithmus ist, der nicht entschlüsselt werden kann. Im Gegenteil, ich habe gezeigt, dass nichts Geheimnisvolles darin ist, und tatsächlich kann es ganz einfach abgeleitet werden, indem man von vorne anfängt.
Weiterführende Literatur
Amit Patel hat eine exzellente
„Einführung in den A * -Algorithmus“ [
Übersetzung auf Habré] (und seine anderen Artikel zu verschiedenen Themen sind ebenfalls exzellent!).