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 kilobytesSchritt 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?
quelle
Antworten:
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.
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.
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.
quelle