Ist die vorausberechnete Wegfindung noch relevant?

12

Kontext

Alte Lucas Arts (ScummVM-Ära) zeigen und klicken Sie Grafik-Adventure-Spiele verwendet vorberechnete Wegfindung. Hier ist eine grobe Übersicht über die Technik.

Schritt 1

Der Boden in jedem Raum war in sogenannte "Walkboxen" unterteilt, die den Knoten in einem Navigationsnetz ziemlich gleichwertig waren, sich jedoch auf Trapezformen beschränkten. Z.B:

 ______ _____ _________ _____
\   A  |  B  |    C    |  D   \
 \_____|     |         |_______\
       |_____|         |
             |_________|

Schritt 2

Ein Offline-Algorithmus (z. B. Dijkstra oder A *) berechnet den kürzesten Pfad zwischen jedem Knotenpaar und speichert den ersten Pfadschritt in einer 2D-Matrix, die in jeder Dimension durch den verwendeten Start- und Endknoten indiziert wird. ZB mit den oben stehenden Walkboxen:

      ___ ___ ___ ___
     | A | B | C | D | <- Start Node
  ___|___|___|___|___|
 | A | A | A | B | C |  ---
 |___|___|___|___|___|     |
 | B | B | B | B | C |     |
 |___|___|___|___|___|     |-- Next node in shortest path
 | C | B | C | C | C |     |   from Start to End
 |___|___|___|___|___|     | 
 | D | B | C | D | D |  ---
 |___|___|___|___|___| 
   ^
   |
End Node

Wie Sie sich vorstellen können, steigt der Speicherbedarf mit zunehmender Anzahl von Knoten (N ^ 2) schnell an. Da ein Short normalerweise groß genug ist, um jeden Eintrag in der Matrix zu speichern, führt eine komplexe Zuordnung von 300 Knoten dazu, dass ein zusätzlicher gespeichert wird:

300^2 * sizeof(short) = 176 kilobytes

Schritt 3

Andererseits war das Berechnen des kürzesten Pfades zwischen zwei Knoten extrem schnell und trivial, nur eine Reihe von Suchen in der Matrix. Etwas wie:

// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
    Current = LookUp[Current, End]
    Path.Add(Current)
ENDWHILE

Verwenden Sie diesen einfachen Algorithmus, um den kürzesten Weg von C nach A zu finden:

1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit

Frage

Ich vermute, dass mit der heutigen leistungsfähigen Hardware und den Speicheranforderungen für jedes Level alle Vorteile, die diese Technik einst hatte, durch einfaches Ausführen eines A * zur Laufzeit aufgewogen werden.

Ich habe auch gehört, dass die Speichersuche heutzutage möglicherweise sogar langsamer ist als die allgemeine Berechnung, weshalb das Erstellen von Sinus- und Cosinus-Nachschlagetabellen nicht mehr so ​​beliebt ist.

Ich muss jedoch zugeben, dass ich noch nicht allzu gut mit diesen Fragen der niedrigen Hardwareeffizienz vertraut bin. Daher nutze ich diese Gelegenheit, um die Meinung derjenigen zu erfragen, die mit dem Thema besser vertraut sind.

Bei meiner Engine musste ich auch die Möglichkeit haben, zur Laufzeit Knoten dynamisch zum Diagramm hinzuzufügen und zu entfernen ( siehe dies ), damit die vorberechnete Route die Dinge nur komplizierter machte. Daher habe ich sie verschrottet (ganz zu schweigen von meiner Laufzeit). Eine * -Lösung lief bereits einwandfrei ). Trotzdem fragte ich mich ...

Fazit: Ist diese Technik heutzutage in jedem Szenario noch relevant?

David Gouveia
quelle
2
Ich denke, es ist immer noch relevant, wenn Sie ein knappes CPU-Budget haben. Wenn Sie jedoch dynamische Pfade möchten, ist dies nicht mehr sinnvoll. Übrigens habe ich mir angesehen, woher Sie Ihren A * -Algorithmus haben und Sie können ihn mit einem Minheap und einigen anderen Tricks noch weiter optimieren. Ich habe einige Iterationen zur Verbesserung von A * in C # durchgeführt, die Sie hier sehen können: roy-t.nl/index.php/2011/09/24/… könnte nützlich sein.
Roy T.
1
Danke, ich habe es mit einem Lesezeichen versehen und werde es prüfen, wenn ich mit der Optimierung meiner Anwendung beginne. Ich habe Eric Lipperts Lösung mit ein paar kleinen Änderungen verwendet, weil sie so sauber und leicht zu verfolgen war ... Und für alle meine Testfälle lief sie so ziemlich "augenblicklich", also habe ich mich nicht einmal darum gekümmert, sie zu optimieren.
David Gouveia
1
Übrigens, wenn Sie sich für eine Vorberechnung entscheiden, sollten Sie sich den Floyd-Warshall-Algorithmus ansehen . Es erstellt die Matrix für den nächsten Schritt effizienter als wiederholt unter Verwendung von Dijkstra / A *.
amitp
@amitp Danke für den Tipp, es ist immer gut, über diese Alternativen Bescheid zu wissen! Obwohl die Vorberechnung in den meisten Fällen offline erfolgen würde, wäre nicht viel zu gewinnen, wenn sie effizienter gestaltet würde. Es sei denn, Sie sind wirklich ungeduldig. :-)
David Gouveia
Einverstanden, obwohl Floyd-Warshall auch viel einfacher zu implementieren ist als der Dijkstra-Algorithmus. Wenn Sie also Dijkstra noch nicht implementiert haben, ist es einen Blick wert :)
amitp 08.02.12

Antworten:

3

Auf meiner Engine musste ich außerdem die Möglichkeit haben, zur Laufzeit Knoten dynamisch zum Diagramm hinzuzufügen und zu entfernen (siehe dies), damit die vorberechnete Route die Dinge nur noch komplizierter machte. Daher habe ich sie verschrottet (ganz zu schweigen von meiner Laufzeit-A * -Lösung, die bereits einwandfrei lief ). Trotzdem fragte ich mich ...

Fazit: Ist diese Technik heutzutage in jedem Szenario noch relevant?

Ich kann keinen Nutzen aus einer solchen Technik ziehen.

Mir fehlt die Flexibilität eines Graphen (Sie können verschiedene LODs haben, sie müssen keine bestimmte Form haben, ect ...). Jeder Benutzer Ihrer Engine wird auch wissen, was ein Graph ist und wie man einen benutzt. Wenn sie also zusätzliche Funktionen hinzufügen möchten, müssen sie lernen, wie sie ihre Erweiterung in einer für sie völlig neuen Situation implementieren.

Wie du erwähnt hast, sieht es so aus, als würde es schrecklich skalieren. Es ist auch erwähnenswert, dass, wenn ein Diagramm auf das Bargeld passt und Sie alle Ihre Pfadermittlungen nacheinander ausführen, die IO-Zeit erheblich verkürzt wird. Es sieht so aus, als würde Ihre Implementierung bald zu groß werden, um in einen Cache zu passen.

Ich habe auch gehört, dass die Speichersuche heutzutage möglicherweise sogar langsamer ist als die allgemeine Berechnung, weshalb das Erstellen von Sinus- und Cosinus-Nachschlagetabellen nicht mehr so ​​beliebt ist.

Wenn Sie nicht Ihr gesamtes Programm und den erforderlichen Speicherplatz in den Cache packen können, werden Sie den Flaschenhals füllen, indem Sie Dinge in den Speicher hinein- und herausziehen, bevor Sie den Prozessor aus dem Flaschenhals nehmen.

Ich vermute, dass mit der heutigen leistungsfähigen Hardware und den Speicheranforderungen für jedes Level alle Vorteile, die diese Technik einst hatte, durch einfaches Ausführen eines A * zur Laufzeit aufgewogen werden

Beachten Sie auch, dass viele Spiele separate Loops zum Aktualisieren der KI haben. Ich glaube, dass mein Projekt so eingerichtet ist, dass es eine Aktualisierungsschleife für Benutzereingaben bei 60 Hz gibt, die KI nur 20 Hz beträgt und die Spiele so schnell wie möglich gezeichnet werden.

Auch als Randnotiz habe ich ein bisschen GBA-Programmierung nur zum Spaß gemacht und nichts überträgt sich auf die Verwendung eines modernen Geräts. Für den GBA ging es nur darum, die Arbeitsbelastung des Prozessors zu minimieren (weil sie erbärmlich war). Sie müssen auch erkennen, dass die meisten Hochsprachen C # und Java (nicht so sehr C ++ oder C) Unmengen von Optimierungen für Sie durchführen. Um Ihren Code zu optimieren, müssen Sie nur so wenig wie möglich auf den Arbeitsspeicher zugreifen und wenn Sie so viele Berechnungen wie möglich ausführen, bevor Sie neuen Arbeitsspeicher einspielen, der ihn aus dem Cache holt und sicherstellt, dass Sie es sind nur einmal Dinge tun.

Bearbeiten: Auch um deinen Titel zu beantworten ist es ja. Das Vorberechnen häufig verwendeter Pfade ist eine hervorragende Idee und kann mit A * überall außerhalb Ihrer Spielrunde durchgeführt werden. Zum Beispiel von Ihrer Basis zu einer Ressource in einem RTS, damit die Gather nicht jedes Mal neu berechnen müssen, wenn sie abreisen oder zurückkehren möchten.

ClassicThunder
quelle
Bei Ihrer Bearbeitung ging es nicht wirklich um das Vorberechnen häufig verwendeter Pfade, sondern ausschließlich um die Technik, mit der alle möglichen Pfade vorberechnet werden . Ich bin auch ein bisschen verwirrt darüber, wie die meisten Ihrer Antworten gegen die Verwendung von vorberechneter Pfadfindung waren, aber am Ende sagten Sie, es wäre eine hervorragende Idee. Wäre es in einer Umgebung mit eingeschränkter CPU wie dem GBA nützlich?
David Gouveia
1
Mein schlechtes Ich wollte darauf hinweisen, dass die Antwort auf Ihren Titel aus dem Kontext genommen ist ja. Während die Antwort in Bezug auf den in Ihrer Frage beschriebenen spezifischen Algorithmus Nein lautet. Kurz gesagt, die Vorausberechnung aller möglichen Pfade ist eine schlechte Idee, aber die Vorausberechnung einiger sehr häufig verwendeter Pfade kann eine gute Idee sein.
ClassicThunder
2
@ClassicThunder: Diese Technik zur Vorausberechnung aller Pfade von wenigen Orientierungspunkten wird häufig als ALT ( A-Stern mit Orientierungspunkten und Dreieckungleichheit) bezeichnet
Pieter Geerkens