Kleine Performance-Guide

Übersicht

BlitzMax, BlitzMax NG

FAQs und Tutorials

	Fetze Betreff: Kleine Performance-Guide	Sa, Jun 24, 2006 15:13 Antworten mit Zitat
Wer kennt das nicht? Ich bin sicher: Nahezu jeder, der schon einmal an einem größeren Projekt eines echtzeitlastigen Genres gearbeitet hat, wird zumindest beim ersten Versuch schnell an die Prozessorgrenze gestoßen sein. Wo liegen die Ursachen hierfür? Und, viel wichtiger: Was tun? Gerade bei größeren Spielwelten liegt der Grund aller FPS-Abgründe häufig daran, dass einfach zu viele zu simulierende Objekte vorhanden sind, auf die man aber auch nicht so ohne weiteres ganz verzichten kann. Was aber nicht heisst, dass man den Prozessor nicht trotzdem entlasten kann: 1. UpdateRadien Der erste Schritt könnte sein, nur die Objekte zu berechnen, die nah genug am Spieler dran sind, um auch nur im entferntesten irgendeine Auswirkung auf ihn zu haben. Natürlich sollte dieser UpdateRadius nicht zu klein sein, denn wenn man eine Gruppe kämpfender NPCs verlässt, zwei Stunden später wieder zurückkehrt und sie dann noch genauso vorfindet, wie man sie verlassen hat, ist das ein übler Rückschlag für die Spieltiefe. Meine Empfehlung wäre es hier, den UpdateRadius so groß zu halten, dass der Spieler zum Durchqueren derselben Entfernung mindestens so lange braucht wie die Spielwelt, um aus ihrem nicht-berechneten Schlaf zu erwachen. So lassen sich schonmal ein paar FPS gewinnen, was aber bei entsprechender Objektanzahl innerhalb des UpdateRadius nicht unbedingt ausreicht. Aber es geht noch weiter: 2. Entfernungsbasierte Berechnungsgenauigkeit Analog zum UpdateRadius wäre es eine gute Idee, weitere Radien zu erstellen, die gemeinsam über den Detailgrad der Berechnungen eines Objekts entscheiden. Beispielsweise wäre es eine Möglichkeit, einen NPC, der weit weg in der Nähe der UpdateRadius-Grenze herumsteht zwar noch zu berechnen, teile seiner KI-Routinen jedoch auf ein maß zu vereinfachen, das in Ordnung ist, solange niemand zusieht. Auch und insbesondere Kollisionsabfragen sollten vereinfacht werden, sobald der Spieler nicht mehr direkt (Spieler verursacht Kollision) oder indirekt (Spieler kann Kollision beobachten) mit ihnen in Verbindung steht! 3. Objekt-Cluster Reicht auch das nicht aus, gibt es noch eine weitere Möglichkeit, große aber nötige Objektzahlen zu entschärfen: Ist der Spieler weit genug entfernt, kann man mehrere Objekte in einen Cluster packen und als ein Objekt berechnen, beispielsweise so: Man nehme ein Gebiet, das es zu berechnen gilt. Zwei NPC-Fraktionen kämpfen darin gegeneinander. Ist der Spieler in der Nähe, greifen die weiter oben erwähnten Berechnungstechniken und jeder NPC, jedes abgeschossene Projektil wird als eigenes Objekt simuliert. Ist nun der Spieler weit genug entfernt, sind diese Kämpfe auch vereinfacht noch zu rechenaufwändig im Verhältnis zum Nutzen, den sie bringen (= dem Spieler bei seiner Rückkehr das Gefühl geben, die Welt bewege sich auch ohne ihn). Anstatt hier gar nicht mehr zu berechnen wäre hier der eben erwähnte Cluster-Alternativweg sinnvoll: Wir löschen alle im Gebiet vorhandenen NPCs und Projektile (bzw. Nicht-Statische Objekte), merken uns aber, wie viele NPCs beider Fraktionen in diesem Sektor zugegen waren. Anschließend wird nur noch das Gebiet als Ganzes berechnet und der Kampf beider Fraktionen läuft nurnoch "auf dem Papier" ab, in Form von kleinen Zahlenspielereien, unkomplizierter Wahrscheinlichkeitsberechnung und mit der Komplexität gewichtet-gewürfelter Zahlenkämpfe. Sobald der Spieler zurückkehrt (d.h. noch außer Sichtweite ist, aber in der Nähe), nehmen wir alle Sektordaten und basteln daraus neue NPCs, die wir darin entsprechend der zuvor gespeicherten Daten darin verteilen. Fertig. Der Spieler hat den Eindruck, die Welt bewegt sich auch, wenn er nicht dabei ist und der Prozessor wird trotzdem entlastet. Wieder ein paar FPS mehr. 4. UpdateGrid Mit einem "UpdateGrid" lassen sich insbesondere Kollisionsabfragen à la "Jedes Objekt mit jedem Objekt" stark beschleunigen: Man verwendet einen kleinen UpdateManager, der alle Objekte in ein Raster einträgt. Dieses Raster besteht aus "Sektoren" mit fest definierter Größe, die ihren Ursprung in der Position 0,0(,0) haben und sich von dort aus beliebig weit in allen zwei (drei) Koordinatenachsen erstrecken. Jedes Objekt wird nun dem Sektor zugeordnet, der seine Position enthält. Ein Beispiel: Sektor A verwaltet die Objekte von Position 2000,3000 bis Position 2999,3999. Ein Objekt mit der Position 2783,3295 würde nun diesem Sektor zugeordnet werden, ein Objekt mit der Position 1943,3604 jedoch nicht. Der Vortei lder ganzen Sache: Wir müssen beispielsweise bei Kollisionsabfragen nie mehr alle Objekte durchgehen sondern lassen uns vom UpdateGrid eine Liste der Objekte erstellen, die sich in einem Bereich befinden, in dem sich potenziell mit dem aktuell zu prüfenden Objekt kollidierende Objekte aufhalten könnten. Das UpdateGrid schaut nun in WIndeseile nach, welche Sektoren den gewünschten Bereich schneiden und liefert uns alle dort enthaltenen Objekte zurück. Das braucht kaum Zeit, wenn gut gecodet und erspart uns eine Menge Distanzkontrollen, die in nahezu jedem Fall weitaus länger gebraucht hätten. Der folgende Eintrag im Codearchiv eignet sich übrigens hervorragend als Grundlage für ein zweidimensionales UpdateGrid https://www.blitzforum.de/foru...hp?t=18937 5. Caching von Funktionswerten Gehen wir nun etwas weg von den gesamtheitlichen Verbesserungsmöglichkeiten und wenden uns einer bestimmt schon dagewesenen aber trotzdem von mir selbst entdeckten (ganz stolz drauf ist ) Möglichkeit zu, Zustandsberechnungen und KI-Routinen zu beschleunigen: Mit "trägen" Funktionen und Methoden. Unter trägen Funktionen und Methoden verstehe ich solche, die nur dann neu berechnet werden, wenn die Möglichkeit besteht, dass sich ihr Rückgabewert geändert haben könnte. Träge Funktionen (und Methoden - ich werde das "und Methoden" im folgenden unterschlagen) sind im Grunde recht einfach zu realisieren: Eine Funktion übernimmt die Neuberechnung der Werte, eine Funktion übernimmt die Rückgabe der zuvor berechneten Werte. Wird ein Wert gebraucht, wird immer letztere Aufgerufen und in jeder Situation, in der sich der Rückgabewert der Funktion ändern sollte / könnte, wird die Neuberechnungs-Funktion aufgerufen. Ein Beispiel: Im Diablo-Like-Raster-Inventar eines NPCs liegen bestimmte Items herum. Jetzt würde ich gerne wissen, wie viele eines bestimmten Itemtyps darin liegen, also müsste ich das Inventar von oben bis unten durchgehen und Items dieses Typs zählen. Das ist relativ zeitaufwändig, wenn die Anzahl oft benötigt wird, daher bietet es sich heir an, die Itemanzahl der verschiedenen Itemtypen nur neu zu berechnen, wenn sich der Inventarinhalt des NPCs verändert. Da das aller Wahrscheinlichkeit nach sehr viel seltener passiert als man aus irgendeinem Grund die Itemanzahl kennen muss, hätte man hier bereits den einen oder anderen FPS gespart. Natürlich ist es nicht immer möglich oder sinnvoll, eine Funktion so zu gestalten, beispielsweise wenn sich der Rückgabewert annähernd jedes Frame verändert. Was aber hier möglich ist: Der Funktion einen individuellen Neuberechnungstimer geben und ihr sagen: Du berechnest den Rückgabewert nur neu, wenn seit dem letzten Aufruf XY Millisekunden / Frames vergangen sind. Wirst du vorher aufgerufen, lieferst du den letzten Rückgabewert zurück. Man sollte hier aber darauf achten, dass nicht alle Objekte eine dieser Funktionen simultan neu berechnen, da das sonst mitunter zu größeren FPS-Schwankungen führen kann. Stattdessen kann man einfach den Timer der entsprechenden Funktion bei der Objekterstellung auf einen Zufallswert zwischen 0 und dem Neuberechnungs-Delay setzen. Solche Functions sind insbesondere bei KI-Routinen sinnvoll, da diese meist rechenaufwändig sind, aber nicht unbedingt jedes Frame ausgeführt werden müssen. Vor allem stört es keinen Spieler, wenn eine KI mal eine Reaktionszeit von - beispielsweise - 100 Millisekunden hat. Die Reaktionszeit des Menschen liegt weit höher! 6. Feintuning Sind die obigen Verbesserungen umgesetzt, gibt es weiterhin die Möglichkeit, den gesamten Code einem ausgiebigen Feintuning zu unterziehen. Tips dazu habe ich bereits in folgendem Thread gepostet: https://www.blitzforum.de/foru...hp?t=13458 So. Ich hoffe, ich konnte jemandem helfen. Kritik und weitere Verbesserungsvorschläge sind erwünscht

Fetze

Betreff: Kleine Performance-Guide

Sa, Jun 24, 2006 15:13
Antworten mit Zitat

Wer kennt das nicht? Ich bin sicher: Nahezu jeder, der schon einmal an einem größeren Projekt eines echtzeitlastigen Genres gearbeitet hat, wird zumindest beim ersten Versuch schnell an die Prozessorgrenze gestoßen sein. Wo liegen die Ursachen hierfür? Und, viel wichtiger: Was tun?

Gerade bei größeren Spielwelten liegt der Grund aller FPS-Abgründe häufig daran, dass einfach zu viele zu simulierende Objekte vorhanden sind, auf die man aber auch nicht so ohne weiteres ganz verzichten kann. Was aber nicht heisst, dass man den Prozessor nicht trotzdem entlasten kann:

1. UpdateRadien

Der erste Schritt könnte sein, nur die Objekte zu berechnen, die nah genug am Spieler dran sind, um auch nur im entferntesten irgendeine Auswirkung auf ihn zu haben. Natürlich sollte dieser UpdateRadius nicht zu klein sein, denn wenn man eine Gruppe kämpfender NPCs verlässt, zwei Stunden später wieder zurückkehrt und sie dann noch genauso vorfindet, wie man sie verlassen hat, ist das ein übler Rückschlag für die Spieltiefe. Meine Empfehlung wäre es hier, den UpdateRadius so groß zu halten, dass der Spieler zum Durchqueren derselben Entfernung mindestens so lange braucht wie die Spielwelt, um aus ihrem nicht-berechneten Schlaf zu erwachen.
So lassen sich schonmal ein paar FPS gewinnen, was aber bei entsprechender Objektanzahl innerhalb des UpdateRadius nicht unbedingt ausreicht. Aber es geht noch weiter:

2. Entfernungsbasierte Berechnungsgenauigkeit

Analog zum UpdateRadius wäre es eine gute Idee, weitere Radien zu erstellen, die gemeinsam über den Detailgrad der Berechnungen eines Objekts entscheiden. Beispielsweise wäre es eine Möglichkeit, einen NPC, der weit weg in der Nähe der UpdateRadius-Grenze herumsteht zwar noch zu berechnen, teile seiner KI-Routinen jedoch auf ein maß zu vereinfachen, das in Ordnung ist, solange niemand zusieht.
Auch und insbesondere Kollisionsabfragen sollten vereinfacht werden, sobald der Spieler nicht mehr direkt (Spieler verursacht Kollision) oder indirekt (Spieler kann Kollision beobachten) mit ihnen in Verbindung steht!

3. Objekt-Cluster

Reicht auch das nicht aus, gibt es noch eine weitere Möglichkeit, große aber nötige Objektzahlen zu entschärfen:
Ist der Spieler weit genug entfernt, kann man mehrere Objekte in einen Cluster packen und als ein Objekt berechnen, beispielsweise so:
Man nehme ein Gebiet, das es zu berechnen gilt. Zwei NPC-Fraktionen kämpfen darin gegeneinander. Ist der Spieler in der Nähe, greifen die weiter oben erwähnten Berechnungstechniken und jeder NPC, jedes abgeschossene Projektil wird als eigenes Objekt simuliert. Ist nun der Spieler weit genug entfernt, sind diese Kämpfe auch vereinfacht noch zu rechenaufwändig im Verhältnis zum Nutzen, den sie bringen (= dem Spieler bei seiner Rückkehr das Gefühl geben, die Welt bewege sich auch ohne ihn). Anstatt hier gar nicht mehr zu berechnen wäre hier der eben erwähnte Cluster-Alternativweg sinnvoll: Wir löschen alle im Gebiet vorhandenen NPCs und Projektile (bzw. Nicht-Statische Objekte), merken uns aber, wie viele NPCs beider Fraktionen in diesem Sektor zugegen waren.
Anschließend wird nur noch das Gebiet als Ganzes berechnet und der Kampf beider Fraktionen läuft nurnoch "auf dem Papier" ab, in Form von kleinen Zahlenspielereien, unkomplizierter Wahrscheinlichkeitsberechnung und mit der Komplexität gewichtet-gewürfelter Zahlenkämpfe. Sobald der Spieler zurückkehrt (d.h. noch außer Sichtweite ist, aber in der Nähe), nehmen wir alle Sektordaten und basteln daraus neue NPCs, die wir darin entsprechend der zuvor gespeicherten Daten darin verteilen. Fertig. Der Spieler hat den Eindruck, die Welt bewegt sich auch, wenn er nicht dabei ist und der Prozessor wird trotzdem entlastet. Wieder ein paar FPS mehr.

4. UpdateGrid

Mit einem "UpdateGrid" lassen sich insbesondere Kollisionsabfragen à la "Jedes Objekt mit jedem Objekt" stark beschleunigen: Man verwendet einen kleinen UpdateManager, der alle Objekte in ein Raster einträgt. Dieses Raster besteht aus "Sektoren" mit fest definierter Größe, die ihren Ursprung in der Position 0,0(,0) haben und sich von dort aus beliebig weit in allen zwei (drei) Koordinatenachsen erstrecken. Jedes Objekt wird nun dem Sektor zugeordnet, der seine Position enthält. Ein Beispiel: Sektor A verwaltet die Objekte von Position 2000,3000 bis Position 2999,3999. Ein Objekt mit der Position 2783,3295 würde nun diesem Sektor zugeordnet werden, ein Objekt mit der Position 1943,3604 jedoch nicht.
Der Vortei lder ganzen Sache: Wir müssen beispielsweise bei Kollisionsabfragen nie mehr alle Objekte durchgehen sondern lassen uns vom UpdateGrid eine Liste der Objekte erstellen, die sich in einem Bereich befinden, in dem sich potenziell mit dem aktuell zu prüfenden Objekt kollidierende Objekte aufhalten könnten. Das UpdateGrid schaut nun in WIndeseile nach, welche Sektoren den gewünschten Bereich schneiden und liefert uns alle dort enthaltenen Objekte zurück. Das braucht kaum Zeit, wenn gut gecodet und erspart uns eine Menge Distanzkontrollen, die in nahezu jedem Fall weitaus länger gebraucht hätten. Der folgende Eintrag im Codearchiv eignet sich übrigens hervorragend als Grundlage für ein zweidimensionales UpdateGrid Wink

https://www.blitzforum.de/foru...hp?t=18937

5. Caching von Funktionswerten

Gehen wir nun etwas weg von den gesamtheitlichen Verbesserungsmöglichkeiten und wenden uns einer bestimmt schon dagewesenen aber trotzdem von mir selbst entdeckten (*ganz stolz drauf ist* Laughing

) Möglichkeit zu, Zustandsberechnungen und KI-Routinen zu beschleunigen:
Mit "trägen" Funktionen und Methoden. Unter trägen Funktionen und Methoden verstehe ich solche, die nur dann neu berechnet werden, wenn die Möglichkeit besteht, dass sich ihr Rückgabewert geändert haben könnte. Träge Funktionen (und Methoden - ich werde das "und Methoden" im folgenden unterschlagen) sind im Grunde recht einfach zu realisieren: Eine Funktion übernimmt die Neuberechnung der Werte, eine Funktion übernimmt die Rückgabe der zuvor berechneten Werte. Wird ein Wert gebraucht, wird immer letztere Aufgerufen und in jeder Situation, in der sich der Rückgabewert der Funktion ändern sollte / könnte, wird die Neuberechnungs-Funktion aufgerufen. Ein Beispiel:
Im Diablo-Like-Raster-Inventar eines NPCs liegen bestimmte Items herum. Jetzt würde ich gerne wissen, wie viele eines bestimmten Itemtyps darin liegen, also müsste ich das Inventar von oben bis unten durchgehen und Items dieses Typs zählen. Das ist relativ zeitaufwändig, wenn die Anzahl oft benötigt wird, daher bietet es sich heir an, die Itemanzahl der verschiedenen Itemtypen nur neu zu berechnen, wenn sich der Inventarinhalt des NPCs verändert. Da das aller Wahrscheinlichkeit nach sehr viel seltener passiert als man aus irgendeinem Grund die Itemanzahl kennen muss, hätte man hier bereits den einen oder anderen FPS gespart.
Natürlich ist es nicht immer möglich oder sinnvoll, eine Funktion so zu gestalten, beispielsweise wenn sich der Rückgabewert annähernd jedes Frame verändert. Was aber hier möglich ist: Der Funktion einen individuellen Neuberechnungstimer geben und ihr sagen: Du berechnest den Rückgabewert nur neu, wenn seit dem letzten Aufruf XY Millisekunden / Frames vergangen sind. Wirst du vorher aufgerufen, lieferst du den letzten Rückgabewert zurück. Man sollte hier aber darauf achten, dass nicht alle Objekte eine dieser Funktionen simultan neu berechnen, da das sonst mitunter zu größeren FPS-Schwankungen führen kann. Stattdessen kann man einfach den Timer der entsprechenden Funktion bei der Objekterstellung auf einen Zufallswert zwischen 0 und dem Neuberechnungs-Delay setzen.
Solche Functions sind insbesondere bei KI-Routinen sinnvoll, da diese meist rechenaufwändig sind, aber nicht unbedingt jedes Frame ausgeführt werden müssen. Vor allem stört es keinen Spieler, wenn eine KI mal eine Reaktionszeit von - beispielsweise - 100 Millisekunden hat. Die Reaktionszeit des Menschen liegt weit höher!

6. Feintuning

Sind die obigen Verbesserungen umgesetzt, gibt es weiterhin die Möglichkeit, den gesamten Code einem ausgiebigen Feintuning zu unterziehen. Tips dazu habe ich bereits in folgendem Thread gepostet:
https://www.blitzforum.de/foru...hp?t=13458

So. Ich hoffe, ich konnte jemandem helfen. Kritik und weitere Verbesserungsvorschläge sind erwünscht Smile