Wie kann ich A * schneller beenden, wenn das Ziel unpassierbar ist?

31

Ich mache ein einfaches kachelbasiertes 2D-Spiel, das den A * -Pfadfindungsalgorithmus ("A Star") verwendet. Ich habe alles richtig gemacht, aber ich habe ein Leistungsproblem mit der Suche. Einfach ausgedrückt, wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden - auch wenn ich daneben stehe.

Wie kann ich das umgehen? Ich denke, ich könnte die Pfadfindung zum Bildschirmbereich reduzieren, aber vielleicht fehlt hier etwas Offensichtliches?

user2499946
quelle
2
Wissen Sie, welche Kacheln unpassierbar sind oder wissen Sie es einfach aufgrund des AStar-Algorithmus?
user000user
Wie speichern Sie Ihre Navigationsgrafik?
Anko
Wenn Sie durchquerte Knoten in Listen speichern, möchten Sie möglicherweise Binärheaps verwenden, um die Geschwindigkeit zu verbessern.
ChrisC
Wenn es einfach zu langsam ist, kann ich eine Reihe von Optimierungen vorschlagen - oder versuchen Sie, Suchanfragen ganz zu vermeiden?
Steven
1
Diese Frage wäre wahrscheinlich besser für die Informatik geeignet gewesen .
Raphael

Antworten:

45

Einige Ideen zum Vermeiden von Suchvorgängen, die zu fehlgeschlagenen Pfaden führen:

Insel ID

Eine der billigsten Möglichkeiten, A * -Suchen effektiv zu beenden, besteht darin, überhaupt keine Suchvorgänge durchzuführen. Wenn die Bereiche für alle Agenten wirklich unpassierbar sind, füllen Sie jeden Bereich unter Last (oder in der Pipeline) mit einer eindeutigen Insel-ID . Überprüfen Sie beim Ermitteln des Pfads , ob die Insel-ID des Ursprungs des Pfads mit der Insel-ID des Ziels übereinstimmt . Wenn sie nicht übereinstimmen, macht die Suche keinen Sinn - die beiden Punkte befinden sich auf unterschiedlichen, nicht verbundenen Inseln. Dies hilft nur, wenn es wirklich unpassierbare Knoten für alle Agenten gibt.

Obergrenze einschränken

Ich beschränke die Obergrenze der maximalen Anzahl von Knoten, die durchsucht werden können. Dies verhindert, dass unpassierbare Suchvorgänge für immer ausgeführt werden. Es bedeutet jedoch, dass einige sehr lange passierbare Suchvorgänge verloren gehen können. Diese Nummer muss angepasst werden und löst das Problem nicht wirklich , verringert jedoch die mit langen Suchvorgängen verbundenen Kosten.

Wenn Sie feststellen, dass es zu lange dauert , sind die folgenden Techniken hilfreich:

Machen Sie es asynchron und begrenzen Sie Iterationen

Lassen Sie die Suche in einem separaten Thread oder in einem Teil jedes Frames ablaufen, damit das Spiel nicht auf die Suche wartet. Zeigen Sie eine Animation des Charakters an, der den Kopf kratzt oder die Füße stampft, oder was auch immer angebracht ist, während Sie darauf warten, dass die Suche endet. Um dies effektiv zu tun, würde ich den Status der Suche als separates Objekt beibehalten und zulassen, dass mehrere Status existieren. Wenn ein Pfad angefordert wird, greifen Sie auf ein Objekt mit freiem Status zu und fügen Sie es der Warteschlange der aktiven Statusobjekte hinzu. Ziehen Sie in Ihrem Pfadfindungs-Update das aktive Element von der Vorderseite der Warteschlange und führen Sie A * aus, bis A. abgeschlossen ist oder B. eine bestimmte Anzahl von Iterationen ausgeführt wird. Wenn Sie fertig sind, fügen Sie das Statusobjekt wieder in die Liste der freien Statusobjekte ein. Wenn es noch nicht abgeschlossen ist, setzen Sie es an das Ende der aktiven Suche und fahren Sie mit der nächsten fort.

Wählen Sie die richtigen Datenstrukturen

Stellen Sie sicher, dass Sie die richtigen Datenstrukturen verwenden. So funktioniert mein StateObject. Alle meine Knoten sind aus Leistungsgründen einer endlichen Zahl (z. B. 1024 oder 2048) zugeordnet. Ich verwende einen Knotenpool, der die Zuweisung von Knoten beschleunigt und es mir auch ermöglicht, Indizes anstelle von Zeigern in meinen Datenstrukturen zu speichern, die u16s sind (oder u8, wenn ich 255 maximale Knoten habe, was ich bei einigen Spielen mache). Für die Pfadfindung verwende ich eine Prioritätswarteschlange für die offene Liste, in der Zeiger auf Knotenobjekte gespeichert sind. Es ist als binärer Heap implementiert und ich sortiere die Gleitkommawerte als Ganzzahlen, da sie immer positiv sind und meine Plattform langsame Gleitkommavergleiche hat. Ich verwende eine Hashtabelle für meine geschlossene Karte, um die Knoten zu verfolgen, die ich besucht habe. Es speichert NodeIDs, nicht Nodes, um Cache-Größen zu sparen.

Cache was du kannst

Wenn Sie einen Knoten zum ersten Mal besuchen und die Entfernung zum Ziel berechnen, speichern Sie die im Statusobjekt gespeicherten Werte im Cache. Wenn Sie den Knoten erneut besuchen, verwenden Sie das zwischengespeicherte Ergebnis, anstatt es erneut zu berechnen. In meinem Fall hilft es, keine Quadratwurzel auf neu besuchten Knoten zu machen. Möglicherweise gibt es andere Werte, die Sie vorberechnen und zwischenspeichern können.

Weitere Bereiche, die Sie untersuchen könnten: Verwenden Sie die bidirektionale Pfadfindung, um von beiden Seiten aus zu suchen. Ich habe dies nicht getan, aber wie andere bemerkt haben, könnte dies helfen, ist aber nicht ohne Einschränkungen. Die andere Sache auf meiner Liste, die ich versuchen möchte, ist die hierarchische Pfadfindung oder die Cluster-Pfadfindung. Es gibt eine interessante Beschreibung in der HavokAI Dokumentation Hier ihr Clustering - Konzept beschreibt, die als die HPA unterscheiden * Implementierungen beschrieben hier .

Viel Glück und lassen Sie uns wissen, was Sie finden.

Steven
quelle
Wenn es verschiedene Agenten mit unterschiedlichen Regeln gibt, aber nicht zu viele, kann dies durch die Verwendung eines ID-Vektors (einer pro Agentenklasse) relativ effizient verallgemeinert werden.
MSalters
4
+1 Um zu erkennen, dass es sich bei dem Problem wahrscheinlich um abgeschottete Bereiche handelt (nicht nur um unpassierbare Kacheln), und dass diese Art von Problem mit frühen Berechnungen der Ladezeit einfacher gelöst werden kann.
Slipp D. Thompson
Fülle jeden Bereich mit Flood oder BFS.
Wolfdawn
Insel-IDs müssen nicht statisch sein. Es gibt einen einfachen Algorithmus, der für den Fall geeignet wäre, dass zwei separate Inseln verbunden werden müssen, eine Insel danach jedoch nicht mehr geteilt werden kann. Seite 8 bis 20 in diesen Folien erläutern diesen speziellen Algorithmus: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf
kasperd
@kasperd Natürlich steht der Neuberechnung von Island-IDs, die zur Laufzeit zusammengeführt werden, nichts mehr im Wege. Der Punkt ist, dass die Insel-IDs es Ihnen ermöglichen, schnell zu bestätigen, ob ein Pfad zwischen zwei Knoten existiert, ohne eine Sternensuche durchzuführen.
Steven
26

AStar ist ein vollständiger Planungsalgorithmus. Wenn also ein Pfad zum Knoten vorhanden ist, wird er von AStar garantiert gefunden. Folglich muss er jeden Pfad aus dem Startknoten heraus überprüfen, bevor er entscheiden kann, dass der Zielknoten nicht erreichbar ist. Dies ist sehr unerwünscht, wenn Sie zu viele Knoten haben.

Möglichkeiten, dies zu mildern:

  • Wenn Sie a priori wissen, dass ein Knoten nicht erreichbar ist (z. B. hat er keine Nachbarn oder ist markiert UnPassable), kehren Sie zurück, No Pathohne AStar aufzurufen.

  • Begrenzen Sie die Anzahl der Knoten, die AStar vor dem Beenden erweitern soll. Überprüfen Sie den offenen Satz. Wenn es jemals zu groß wird, kündigen Sie und kehren Sie zurück No Path. Dies schränkt jedoch die Vollständigkeit von AStar ein. es können also nur Pfade mit maximaler Länge geplant werden.

  • Begrenzen Sie die Zeit, die AStar benötigt, um einen Pfad zu finden. Wenn die Zeit knapp wird, beenden Sie das Programm und kehren Sie zurück No Path. Dies schränkt die Vollständigkeit wie bei der vorherigen Strategie ein, skaliert jedoch mit der Geschwindigkeit des Computers. Beachten Sie, dass dies für viele Spiele unerwünscht ist, da Spieler mit schnelleren oder langsameren Computern das Spiel anders erleben.

mklingen
quelle
13
Ich möchte darauf hinweisen, dass das Ändern der Spielmechanik in Abhängigkeit von der CPU-Geschwindigkeit (ja, Routensuche ist eine Spielmechanik) möglicherweise eine schlechte Idee ist, da dies das Spiel ziemlich unvorhersehbar und in einigen Fällen sogar unspielbar machen kann auf Computern in 10 Jahren. Daher würde ich eher empfehlen, A * durch Begrenzen des offenen Satzes als durch CPU-Zeit zu begrenzen.
Philipp
@Philipp. Die Antwort wurde geändert, um dies widerzuspiegeln.
Mklingen
1
Beachten Sie, dass Sie für ein bestimmtes Diagramm den maximalen Abstand zwischen zwei Knoten bestimmen können (relativ effizient, O (Knoten)). Dies ist das Problem mit dem längsten Pfad und bietet Ihnen eine korrekte Obergrenze für die Anzahl der zu überprüfenden Knoten.
MSalters
2
@MSalters Wie machst du das in O (n)? Und was ist "einigermaßen effizient"? Wenn dies nur für Knotenpaare gilt, duplizieren Sie dann nicht einfach die Arbeit?
Steven
Laut Wikipedia ist das längste Pfadproblem leider NP-schwer.
Desty
21
  1. Führen Sie eine doppelte A * -Suche vom Zielknoten aus gleichzeitig in derselben Schleife in umgekehrter Reihenfolge durch und brechen Sie beide Suchvorgänge ab, sobald eine unlösbar ist

Wenn das Ziel nur 6 Kacheln hat, auf die zugegriffen werden kann, und der Ursprung 1002 Kacheln hat, stoppt die Suche bei 6 (doppelten) Iterationen.

Sobald eine Suche die besuchten Knoten der anderen findet, können Sie den Suchbereich auch auf die besuchten Knoten der anderen Suche beschränken und schneller beenden.

Stephane Hockenhull
quelle
2
Die Implementierung einer bidirektionalen A-Stern-Suche ist mehr als Ihre Aussage impliziert, einschließlich der Überprüfung, ob die Heuristik unter diesen Umständen zulässig bleibt. (Links: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf )
Pieter Geerkens
4
@StephaneHockenhull: Nachdem Sie eine bidirektionale A- * auf einer Geländekarte mit asymmetrischen Kosten implementiert haben, versichere ich Ihnen, dass das Ignorieren des akademischen Blabla zu einer fehlerhaften Pfadauswahl und falschen Kostenberechnungen führt.
Pieter Geerkens
1
@MooingDuck: Die Gesamtzahl der Knoten bleibt unverändert, und jeder Knoten wird nur einmal besucht. Daher ist der schlimmste Fall einer genau in zwei Hälften geteilten Karte identisch mit unidirektionalem A- *.
Pieter Geerkens
1
@PieterGeerkens: Im klassischen A * sind nur die Hälfte der Knoten erreichbar und damit besucht. Wenn die Karte genau in zwei Hälften geteilt ist, berühren Sie (fast) jeden Knoten, wenn Sie bidirektional suchen. Auf jeden Fall ein
Randfall
1
@MooingDuck: Ich habe falsch gesprochen. Die schlimmsten Fälle sind unterschiedliche Graphen, weisen jedoch dasselbe Verhalten auf - der schlimmste Fall für unidirektionale ist ein vollständig isolierter Zielknoten, für den alle Knoten besucht werden müssen.
Pieter Geerkens
12

Angenommen, das Problem ist, dass das Ziel nicht erreichbar ist. Und dass das Navigationsnetz nicht dynamisch ist. Der einfachste Weg, dies zu tun, ist ein viel spärlicheres Navigationsdiagramm (spärlich genug, damit ein vollständiger Durchlauf relativ schnell vonstatten geht) und die Verwendung des detaillierten Diagramms nur, wenn das Verfolgen möglich ist.

ClassicThunder
quelle
6
Das ist gut. Indem Sie Kacheln in "Regionen" gruppieren und zuerst prüfen, ob die Region, in der sich Ihre Kachel befindet, mit der Region verbunden werden kann, in der sich die andere Kachel befindet, können Sie Negative viel schneller wegwerfen.
Konerak
2
Richtig - fällt in der Regel unter HPA *
Steven
@Steven Danke Ich war mir sicher, dass ich nicht der erste war, der an einen solchen Ansatz dachte, wusste aber nicht, wie er genannt wurde. Erleichtert die Nutzung bereits vorhandener Forschungsergebnisse erheblich.
ClassicThunder
3

Verwenden Sie mehrere Algorithmen mit unterschiedlichen Eigenschaften

A * hat einige feine Eigenschaften. Insbesondere findet es immer den kürzesten Weg, falls vorhanden. Leider haben Sie auch einige schlechte Eigenschaften festgestellt. In diesem Fall muss es vollständig nach allen möglichen Pfaden suchen, bevor zugegeben wird, dass keine Lösung vorhanden ist.

Der "Fehler", den Sie in A * entdecken, besteht darin, dass die Topologie nicht bekannt ist. Sie haben vielleicht eine 2-D-Welt, aber das weiß es nicht. Nach allem, was es weiß, befindet sich in der äußersten Ecke Ihrer Welt eine Treppe, die es unter der Welt ans Ziel bringt.

Erwägen Sie, einen zweiten Algorithmus zu erstellen, der die Topologie berücksichtigt. In einem ersten Durchgang können Sie die Welt alle 10 oder 100 Felder mit "Knoten" füllen und dann eine Konnektivitätsgrafik zwischen diesen Knoten erstellen. Dieser Algorithmus findet den Pfad, indem zugängliche Knoten in der Nähe von Anfang und Ende gefunden werden und anschließend versucht wird, einen Pfad zwischen ihnen im Diagramm zu finden, falls einer vorhanden ist.

Eine einfache Möglichkeit, dies zu tun, besteht darin, jede Kachel einem Knoten zuzuweisen. Es ist trivial zu zeigen, dass Sie jeder Kachel nur einen Knoten zuweisen müssen (Sie können niemals auf zwei Knoten zugreifen, die in der Grafik nicht verbunden sind). Dann werden die Graphenkanten so definiert, dass zwei Kacheln mit unterschiedlichen Knoten benachbart sind.

Diese Grafik hat einen Nachteil: Sie findet nicht den optimalen Pfad. Es findet nur einen Weg. Es hat sich jedoch gezeigt, dass A * einen optimalen Weg finden kann.

Es bietet auch eine Heuristik zur Verbesserung der für die Funktion von A * erforderlichen Unterschätzungen, da Sie jetzt mehr über Ihre Landschaft wissen. Es ist weniger wahrscheinlich, dass Sie eine Sackgasse vollständig erkunden müssen, bevor Sie feststellen, dass Sie einen Schritt zurücktreten müssen, um vorwärts zu gehen.

Cort Ammon
quelle
Ich habe Grund zu der Annahme, dass Algorithmen wie die für Google Maps auf ähnliche (wenn auch fortgeschrittenere) Weise funktionieren.
Cort Ammon
Falsch. A * ist sich der Topologie durch die Wahl der zulässigen Heuristik sehr bewusst.
MSalters
Bei Google haben wir in meinem vorherigen Job die Leistung von Google Maps analysiert und festgestellt, dass es nicht A * gewesen sein kann. Wir glauben, dass sie ArcFlags oder ähnliche Algorithmen verwenden, die auf der Kartenvorverarbeitung basieren.
MSalters
@MSalters: Das ist eine interessante feine Linie. Ich behaupte, A * ist sich der Topologie nicht bewusst, da es sich nur um die nächsten Nachbarn handelt. Ich würde argumentieren, dass es fairer ist zu sagen, dass der Algorithmus, der die zulässige Heuristik erzeugt, die Topologie kennt, und nicht A * selbst. Stellen Sie sich einen Fall vor, in dem sich ein Diamant befindet. Ein * nimmt einen Pfad für eine Weile, bevor es ein Backup durchführt, um die andere Seite des Diamanten zu testen. Es gibt keine Möglichkeit, A * mitzuteilen, dass der einzige "Exit" aus diesem Zweig über einen bereits besuchten Knoten (Speichern der Berechnung) mit der Heuristik erfolgt.
Cort Ammon
1
Ich kann nicht für Google Maps sprechen, aber Bing Map verwendet einen parallelen bidirektionalen A-Stern mit Orientierungspunkten und Dreieck-Ungleichung (ALT) mit vorberechneten Entfernungen von (und zu) einer kleinen Anzahl von Orientierungspunkten und jedem Knoten.
Pieter Geerkens
2

Einige weitere Ideen zusätzlich zu den Antworten oben:

  1. Cache-Ergebnisse der A * -Suche. Speichern Sie die Pfaddaten von Zelle A zu Zelle B und verwenden Sie sie nach Möglichkeit erneut. Dies gilt vor allem für statische Karten, und Sie müssen mehr mit dynamischen Karten arbeiten.

  2. Cache die Nachbarn jeder Zelle. Eine * -Implementierung muss jeden Knoten erweitern und dem zu durchsuchenden offenen Satz seine Nachbarn hinzufügen. Wenn diese Nachbarn jedes Mal berechnet und nicht zwischengespeichert werden, kann dies die Suche erheblich verlangsamen. Und wenn Sie dies noch nicht getan haben, verwenden Sie eine Prioritätswarteschlange für A *.

user55564
quelle
1

Wenn Ihre Karte statisch ist, können Sie jeden Abschnitt mit einem eigenen Code versehen und diesen zuerst überprüfen, bevor Sie A * ausführen. Dies kann bei der Erstellung der Karte oder sogar in der Karte codiert werden.

Unpassierbare Kacheln sollten eine Flagge haben und wenn Sie sich auf eine Kachel wie diese bewegen, können Sie sich dafür entscheiden, A * nicht auszuführen oder eine Kachel daneben auszuwählen, die erreichbar ist.

Wenn Sie dynamische Karten haben, die sich häufig ändern, haben Sie ziemlich viel Pech. Sie müssen entscheiden, ob Ihr Algorithmus vor dem Abschluss gestoppt werden soll oder ob Überprüfungen von Abschnitten häufig abgeschlossen werden.

Madmenyo
quelle
Dies ist genau das, was ich mit einer Gebiets-ID in meiner Antwort vorgeschlagen habe.
Steven
Sie können auch den CPU- / Zeitaufwand reduzieren, wenn Ihre Map dynamisch ist, sich jedoch nicht häufig ändert. Das heißt, Sie können Gebiets-IDs neu berechnen, wenn eine verschlossene Tür entriegelt oder verschlossen wird. Da dies normalerweise als Reaktion auf die Aktionen eines Spielers geschieht, schließen Sie zumindest gesperrte Bereiche eines Dungeons aus.
uliwitness
1

Wie kann ich A * schneller zu dem Schluss bringen, dass ein Knoten unpassierbar ist?

Profilieren Sie Ihre Node.IsPassable()Funktion, finden Sie die langsamsten Teile heraus und beschleunigen Sie sie.

Stellen Sie bei der Entscheidung, ob ein Knoten passierbar ist, die wahrscheinlichsten Situationen in den Vordergrund, damit die Funktion die meiste Zeit sofort zurückkehrt, ohne sich die Mühe zu machen, die unklareren Möglichkeiten zu prüfen.

Dies dient jedoch dazu, die Überprüfung eines einzelnen Knotens zu beschleunigen. Sie können ein Profil erstellen, um zu sehen, wie viel Zeit für die Abfrage von Knoten aufgewendet wird. Es scheint jedoch, als ob Ihr Problem darin besteht, dass zu viele Knoten überprüft werden.

Wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden

Wenn das Zielplättchen selbst nicht passierbar ist, sollte der Algorithmus überhaupt keine Plättchen prüfen. Bevor überhaupt mit der Pfadfindung begonnen wird, sollte die Zielkachel abgefragt werden, um zu überprüfen, ob dies möglich ist. Andernfalls wird ein Ergebnis ohne Pfad zurückgegeben.

Wenn Sie meinen, dass das Ziel selbst passierbar ist, aber von unpassierbaren Kacheln umgeben ist, sodass es keinen Pfad gibt, ist es normal, dass A * die gesamte Karte überprüft. Woher sollte es sonst wissen, dass es keinen Weg gibt?

Wenn letzteres der Fall ist, können Sie es durch eine bidirektionale Suche beschleunigen. Auf diese Weise kann die Suche ab dem Zielort schnell feststellen, dass es keinen Pfad gibt, und die Suche stoppen. Sehen Sie sich dieses Beispiel an , umgeben Sie das Ziel mit Wänden und vergleichen Sie bidirektionale und einzelne Richtungen.

Super
quelle
0

Machen Sie die Wegfindung rückwärts.

Wenn Ihre Karte nur keine großen zusammenhängenden Bereiche mit nicht erreichbaren Kacheln enthält, funktioniert dies. Anstatt die gesamte erreichbare Karte zu durchsuchen, durchsucht die Wegsuche nur den umschlossenen nicht erreichbaren Bereich.

aaaaaaaaaaa
quelle
Dies ist noch langsamer, wenn die nicht erreichbaren Kacheln die erreichbaren Kacheln
übersteigen
1
@MooingDuck Die verbundenen nicht erreichbaren Kacheln, die Sie meinen. Dies ist eine Lösung, die mit so ziemlich jedem vernünftigen Kartendesign funktioniert und sehr einfach zu implementieren ist. Ich werde nichts Besonderes vorschlagen, ohne das genaue Problem besser zu kennen, wie zum Beispiel, dass die A * -Implementierung so langsam sein kann, dass der Besuch aller Kacheln tatsächlich ein Problem darstellt.
aaaaaaaaaaa
0

Wenn die Bereiche, mit denen der Player verbunden ist (keine Teleports usw.) und die nicht erreichbaren Bereiche im Allgemeinen nicht sehr gut verbunden sind, können Sie das A * einfach ab dem Knoten ausführen, den Sie erreichen möchten. Auf diese Weise können Sie immer noch eine mögliche Route zum Ziel finden, und A * hört schnell auf, nach unerreichbaren Bereichen zu suchen.

ent
quelle
Der Punkt sollte schneller sein als normales A *.
Heckel
0

Wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden - auch wenn ich daneben stehe.

Andere Antworten sind großartig, aber ich muss auf das Offensichtliche hinweisen - Sie sollten die Wegfindung zu einem unpassierbaren Plättchen überhaupt nicht ausführen.

Dies sollte ein früher Ausstieg aus dem Algo sein:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
Kromster sagt Unterstützung Monica
quelle
0

So überprüfen Sie die größte Entfernung in einem Diagramm zwischen zwei Knoten:

(vorausgesetzt alle Kanten haben das gleiche Gewicht)

  1. Führen Sie BFS von einem beliebigen Scheitelpunkt aus v.
  2. Verwenden Sie die Ergebnisse, um einen Scheitelpunkt auszuwählen, der am weitesten entfernt ist v, wir nennen ihn d.
  3. Führen Sie BFS von aus u.
  4. Finden Sie den am weitesten entfernten Scheitelpunkt u, wir nennen ihn w.
  5. Der Abstand zwischen uund wist der längste Abstand in der Grafik.

Beweis:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)
  • Sagen wir, der Abstand zwischen yund xist größer!
  • Dann dementsprechend D2 + R < D3
  • Dann D2 < R + D3
  • Dann ist der Abstand zwischen vund xgrößer als der von vund u?
  • Dann uwäre in der ersten Phase nicht gepflückt worden.

Gutschrift an prof. Shlomi Rubinstein

Wenn Sie gewichtete Kanten verwenden, können Sie dasselbe in Polynomialzeit erreichen, indem Sie Dijkstra anstelle von BFS ausführen, um den am weitesten entfernten Scheitelpunkt zu finden.

Bitte beachten Sie, dass ich davon ausgehe, dass es sich um ein zusammenhängendes Diagramm handelt. Ich gehe auch davon aus, dass es ungerichtet ist.


Ein * ist nicht wirklich nützlich für ein einfaches 2-D-Spiel, da, wenn ich richtig verstehe, vorausgesetzt, die Kreaturen bewegen sich in vier Richtungen, BFS die gleichen Ergebnisse erzielen wird. Selbst wenn sich Kreaturen in 8 Richtungen bewegen können, erzielen faule BFS, die Knoten bevorzugen, die näher am Ziel sind, dieselben Ergebnisse. A * ist eine Modifikation von Dijkstra, die viel rechenintensiver ist als die Verwendung von BFS.

BFS = O (| V |) angeblich O (| V | + | E |), aber nicht wirklich im Fall einer Top-Down-Karte. A * = O (| V | log | V |)

Wenn wir eine Karte mit nur 32 x 32 Kacheln haben, kostet BFS höchstens 1024 und ein echtes A * kann Sie satte 10.000 kosten. Dies ist die Differenz zwischen 0,5 Sekunden und 5 Sekunden, möglicherweise mehr, wenn Sie den Cache berücksichtigen. Stellen Sie also sicher, dass sich Ihr A * wie ein fauler BFS verhält, der Kacheln bevorzugt, die näher am gewünschten Ziel sind.

Ein * ist nützlich für Navigationskarten, wenn die Kosten für Kanten bei der Entscheidungsfindung wichtig sind. Bei einfachen Overhead-Spielen auf Kachelbasis spielen die Kosten für Kanten wahrscheinlich keine wichtige Rolle. Falls dies der Fall ist (verschiedene Kacheln kosten unterschiedlich), können Sie eine modifizierte Version von BFS ausführen, die Pfade, die durch Kacheln verlaufen, die den Charakter verlangsamen, verschiebt und benachteiligt.

Also ja BFS> A * in vielen Fällen, wenn es um Fliesen geht.

wolfdawn
quelle
Ich bin mir nicht sicher, ob ich diesen Teil verstehe. "Wenn wir eine Karte mit nur 32 x 32 Kacheln haben, kostet BFS höchstens 1024 und ein echtes A * kann Sie satte 10.000 kosten." Können Sie erklären, wie Sie zu den 10k gekommen sind nummer bitte
Kromster sagt Unterstützung Monica
Was genau meinen Sie mit "faulem BFS, das Knoten näher am Ziel bevorzugt"? Meinen Sie Dijkstra, einfaches BFS oder eines mit einer Heuristik (gut, Sie haben A * hier neu erstellt, oder wie wählen Sie den nächstbesten Knoten aus einer offenen Menge aus)? Das liegt log|V|in der Komplexität von A * daran, dass diese offene Menge oder die Größe des Randes beibehalten wird und dass sie für Rasterkarten extrem klein ist - etwa log (sqrt (| V |)) unter Verwendung Ihrer Notation. Das Protokoll | V | Wird nur in überverbundenen Diagrammen angezeigt. Dies ist ein Beispiel, bei dem eine naive Anwendung der Worst-Case-Komplexität zu einer falschen Schlussfolgerung führt.
Congusbongus
@congusbongus Genau das meine ich. Verwenden Sie keine Vanille-Implementierung von A *
wolfdawn
@KromStern Angenommen, Sie verwenden die Vanilla-Implementierung von A * für ein Spiel auf Kacheln, dann erhalten Sie eine V * logV-Komplexität, wobei V die Anzahl der Kacheln ist und für ein Raster von 32 mal 32 1024 logV, also ungefähr die Anzahl der Bits benötigt, um 1024 darzustellen, was 10 ist. Sie laufen also unnötigerweise länger. Wenn Sie sich auf die Implementierung spezialisieren, um die Tatsache auszunutzen, dass Sie auf einem Raster von Kacheln laufen, überwinden Sie
natürlich