Datenstrukturen für Interpolation und Threading?

20

Ich habe in letzter Zeit einige Probleme mit Bildfrequenz-Jitter bei meinem Spiel behoben, und es scheint, dass die beste Lösung die von Glenn Fiedler (Gaffer on Games) im klassischen Fix Your Timestep! Artikel.

Jetzt - ich benutze bereits einen festen Zeitschritt für mein Update. Das Problem ist, dass ich nicht die vorgeschlagene Interpolation für das Rendern mache. Das Ergebnis ist, dass ich doppelte oder übersprungene Frames bekomme, wenn meine Renderrate nicht mit meiner Aktualisierungsrate übereinstimmt. Diese können optisch auffällig sein.

Deshalb möchte ich meinem Spiel Interpolation hinzufügen - und ich bin gespannt, wie andere ihre Daten und ihren Code strukturiert haben, um dies zu unterstützen.

Natürlich muss ich (wo? / Wie?) Zwei Kopien der Spielstatusinformationen speichern, die für meinen Renderer relevant sind, damit er zwischen ihnen interpolieren kann.

Außerdem scheint dies ein guter Ort zu sein, um Threading hinzuzufügen. Ich stelle mir vor, dass ein Update-Thread auf einer dritten Kopie des Spielstatus funktionieren könnte und die anderen beiden Kopien für den Render-Thread schreibgeschützt bleiben. (Ist das eine gute Idee?)

Es scheint, dass zwei oder drei Versionen des Spielzustands Probleme mit der Leistung und - was noch wichtiger ist - mit der Zuverlässigkeit und der Entwicklerproduktivität hervorrufen könnten , verglichen mit nur einer einzigen Version. Ich interessiere mich daher besonders für Methoden zur Minderung dieser Probleme.

Von besonderer Bedeutung ist meines Erachtens das Problem, wie das Hinzufügen und Entfernen von Objekten aus dem Spielstatus gehandhabt wird.

Schließlich scheint es, dass ein Status entweder nicht direkt für das Rendern benötigt wird oder dass es zu schwierig ist, verschiedene Versionen zu verfolgen (z. B. eine Physik-Engine eines Drittanbieters, die einen einzelnen Status speichert). Daher wäre ich interessiert zu wissen, wie Menschen haben diese Art von Daten in einem solchen System gehandhabt.

Andrew Russell
quelle

Antworten:

4

Versuchen Sie nicht, den gesamten Spielstatus zu replizieren. Interpolieren wäre ein Albtraum. Isolieren Sie einfach die Teile, die variabel sind und durch Rendern benötigt werden (nennen wir dies einen "visuellen Zustand").

Erstellen Sie für jede Objektklasse eine zugehörige Klasse, die das Objekt Visual State aufnehmen kann. Dieses Objekt wird von der Simulation erzeugt und vom Rendering verbraucht. Die Interpolation wird leicht dazwischen gesteckt. Wenn der Status unveränderlich ist und als Wert übergeben wird, treten keine Threading-Probleme auf.

Das Rendern muss normalerweise nichts über logische Beziehungen zwischen den Objekten wissen, daher ist die für das Rendern verwendete Struktur ein einfacher Vektor oder höchstens ein einfacher Baum.

Beispiel

Traditionelles Design

class Actor
{
  Matrix4x3 position;
  float fuel;
  float armor;
  float stamina;
  float age;

  void Simulate(float deltaT)
  {
    age += deltaT;
    armor -= HitByAWeapon();
  }
}

Verwenden des visuellen Status

class IVisualState
{
  public:
  virtual void Interpolate(const IVisualState &newVS, float f) {}
};
class Actor
{
  struct VisualState: public IVisualState
  {
    Matrix4x3 position;
    float fuel;
    float armor;
    float stamina;
    float age;

    virtual auto_ptr<IVisualState> Interpolate(const IVisualState &newVS, float f)
    {
      const VisualState &newState = static_cast<const VisualState &>(newVS);
      IVisualState *ret = new VisualState;
      ret->age = lerp(this->age,newState.age);
      // ... interpolate other properties as well, using any suitable interpolation method
      // liner, spline, slerp, whatever works best for the given property
      return ret;
    };
  };

  auto_ptr<VisualState> state_;

  void Simulate(float deltaT)
  {
    state_->age += deltaT;
    state_->armor -= HitByAWeapon();
  }
}
Suma
quelle
1
Ihr Beispiel wäre einfacher zu lesen, wenn Sie nicht "new" (ein reserviertes Wort in C ++) als Parameternamen verwenden würden.
Steve S
3

Meine Lösung ist weit weniger elegant / kompliziert als die meisten. Ich verwende Box2D als meine Physik-Engine, so dass es nicht möglich ist, mehr als eine Kopie des Systemstatus zu verwalten (klonen Sie das Physik-System und versuchen Sie dann, sie synchron zu halten. Es könnte einen besseren Weg geben, aber ich konnte mir nichts einfallen lassen eins).

Stattdessen halte ich einen laufenden Zähler der Physikgeneration . Jedes Update erhöht die Physikgeneration, wenn das Physiksystem doppelt aktualisiert wird, und der Generationszähler doppelt aktualisiert wird.

Das Wiedergabesystem verfolgt die letzte wiedergegebene Generation und das Delta seit dieser Generation. Beim Rendern von Objekten, deren Position interpoliert werden soll, können diese Werte zusammen mit ihrer Position und Geschwindigkeit verwendet werden, um zu erraten, wo das Objekt gerendert werden soll.

Ich habe nicht angesprochen, was zu tun ist, wenn die Physik-Engine zu schnell ist. Ich würde fast argumentieren, dass man nicht für schnelle Bewegungen interpolieren sollte. Wenn Sie beides tun, müssen Sie darauf achten, dass die Sprites nicht herumspringen, indem Sie zu langsam und dann zu schnell raten.

Als ich das Interpolationsmaterial schrieb, ließ ich die Grafiken bei 60 Hz und die Physik bei 30 Hz laufen. Es stellt sich heraus, dass Box2D viel stabiler ist, wenn es mit 120 Hz betrieben wird. Aus diesem Grund wird mein Interpolationscode sehr wenig genutzt. Durch die Verdoppelung der Ziel-Framerate wird die Physik durchschnittlich zweimal pro Frame aktualisiert. Mit Jitter könnte das auch 1 oder 3 mal sein, aber fast nie 0 oder 4+. Die höhere Physikrate behebt das Interpolationsproblem irgendwie von selbst. Wenn sowohl die Physik als auch die Framerate bei 60 Hz laufen, erhalten Sie möglicherweise 0-2 Updates pro Frame. Der visuelle Unterschied zwischen 0 und 2 ist im Vergleich zu 1 und 3 sehr groß.

deft_code
quelle
3
Ich habe das auch gefunden. Eine 120-Hz-Physikschleife mit einem Frame-Update von nahezu 60 Hz macht die Interpolation nahezu wertlos. Leider funktioniert dies nur für Spiele, die sich eine 120-Hz-Physikschleife leisten können.
Ich habe gerade versucht, auf eine 120-Hz-Update-Schleife umzuschalten. Dies scheint den doppelten Vorteil zu haben, dass meine Physik stabiler wird und mein Spiel bei Bildraten von nicht ganz 60 Hz flüssig aussieht. Der Nachteil ist, dass es meine sorgfältig abgestimmte Gameplay-Physik zerstört - dies ist also definitiv eine Option, die früh in einem Projekt ausgewählt werden muss.
Andrew Russell
Außerdem: Ich verstehe Ihre Erklärung Ihres Interpolationssystems nicht wirklich. Es klingt ein bisschen nach Extrapolation, oder?
Andrew Russell
Guter Anruf. Ich habe tatsächlich ein Extrapolationssystem beschrieben. Angesichts der Position, der Geschwindigkeit und der Zeit, die seit dem letzten Physik-Update vergangen ist, extrapoliere ich, wo sich das Objekt befinden würde, wenn die Physik-Engine nicht zum Stillstand gekommen wäre.
deft_code
2

Ich habe diese Herangehensweise an Zeitschritte häufig vorgeschlagen, aber in 10 Jahren in Spielen habe ich noch nie an einem realen Projekt gearbeitet, das sich auf einen festen Zeitschritt und eine feste Interpolation stützte.

Dies scheint im Allgemeinen aufwändiger zu sein als ein variables Zeitschrittsystem (unter der Annahme eines vernünftigen Bereichs von Frameraten im Bereich von 25 Hz bis 100 Hz).

Für einen sehr kleinen Prototyp habe ich einmal den festen Zeitschritt + Interpolationsansatz ausprobiert - kein Threading, sondern eine Logikaktualisierung mit festem Zeitschritt und ein möglichst schnelles Rendern, wenn dies nicht aktualisiert wird. Mein Ansatz bestand darin, ein paar Klassen wie CInterpolatedVector und CInterpolatedMatrix zu haben, die vorherige / aktuelle Werte speicherten und einen Accessor aus dem Rendercode verwendeten, um den Wert für die aktuelle Renderzeit abzurufen (der immer zwischen dem vorherigen und dem aktuellen Wert liegen würde aktuelle Zeiten)

Jedes Spielobjekt würde am Ende seiner Aktualisierung seinen aktuellen Zustand auf einen Satz dieser interpolierbaren Vektoren / Matrizen setzen. Diese Art von Dingen könnte erweitert werden, um das Threading zu unterstützen. Sie benötigen mindestens 3 Sätze von Werten - einen, der aktualisiert wird, und mindestens 2 vorherige Werte, um zwischen ... zu interpolieren.

Beachten Sie, dass einige Werte nicht trivial interpoliert werden können (z. B. 'Sprite-Animationsrahmen', 'Spezialeffekt aktiv'). Je nach den Anforderungen Ihres Spiels können Sie die Interpolation möglicherweise vollständig überspringen oder Probleme verursachen.

Meiner Meinung nach ist es am besten, einen variablen Zeitschritt zu wählen - es sei denn, Sie erstellen ein RTS oder ein anderes Spiel, in dem Sie eine große Anzahl von Objekten haben, und müssen 2 unabhängige Simulationen für Netzwerkspiele synchron halten (nur Befehle über das Internet senden) Netzwerk statt Objektpositionen). In dieser Situation ist ein fester Zeitschritt die einzige Option.

Bluescrn
quelle
1
Es scheint, dass mindestens Quake 3 diesen Ansatz verwendet hat, wobei der Standardwert für "tick" 20 fps (50 ms) ist.
Suma
Interessant. Ich nehme an, es hat seine Vorteile für hart umkämpfte Multiplayer-PC-Spiele, um sicherzustellen, dass schnellere PCs / höhere Frameraten nicht zu viel von Vorteil sind (reaktionsfreudigere Steuerung oder kleine, aber ausnutzbare Unterschiede im Physik- / Kollisionsverhalten). ?
Bluescrn
1
Hast du in 10 Jahren noch kein Spiel kennengelernt, bei dem die Physik nicht im Gleichschritt mit der Simulation und dem Renderer lief? Denn in dem Moment, in dem Sie dies tun, müssen Sie die wahrgenommenen Ruckler in Ihren Animationen interpolieren oder akzeptieren.
Kaj,
2

Natürlich muss ich (wo? / Wie?) Zwei Kopien der Spielstatusinformationen speichern, die für meinen Renderer relevant sind, damit er zwischen ihnen interpolieren kann.

Ja, zum Glück ist der Schlüssel hier "relevant für meinen Renderer". Dies ist möglicherweise nicht mehr als das Hinzufügen einer alten Position und eines Zeitstempels dafür zum Mix. Bei 2 vorgegebenen Positionen können Sie auf eine Position zwischen diesen interpolieren. Wenn Sie ein 3D-Animationssystem haben, können Sie die Pose in der Regel trotzdem genau zu diesem Zeitpunkt anfordern.

Das ist ganz einfach - stellen Sie sich vor, Ihr Renderer muss in der Lage sein, Ihr Spielobjekt zu rendern. Früher wurde das Objekt gefragt, wie es aussieht, jetzt muss es gefragt werden, wie es zu einem bestimmten Zeitpunkt aussieht. Sie müssen nur die Informationen speichern, die zur Beantwortung dieser Frage erforderlich sind.

Außerdem scheint dies ein guter Ort zu sein, um Threading hinzuzufügen. Ich stelle mir vor, dass ein Update-Thread auf einer dritten Kopie des Spielstatus funktionieren könnte und die anderen beiden Kopien für den Render-Thread schreibgeschützt bleiben. (Ist das eine gute Idee?)

Es klingt nur nach einem Rezept für zusätzlichen Schmerz. Ich habe nicht über die gesamten Auswirkungen nachgedacht, aber ich gehe davon aus, dass Sie auf Kosten einer höheren Latenz möglicherweise ein bisschen mehr Durchsatz erzielen. Oh, und Sie können einige Vorteile aus der Verwendung eines anderen Kerns ziehen, aber ich weiß nicht.

Kylotan
quelle
1

Beachten Sie, dass ich mich nicht wirklich mit Interpolation befasse, sodass diese Antwort nicht darauf eingeht. Es geht mir nur darum, eine Kopie des Spielstatus für den Rendering-Thread und eine andere für den Update-Thread zu haben. Daher kann ich das Problem der Interpolation nicht kommentieren, obwohl Sie die folgende Lösung für die Interpolation ändern könnten.

Ich habe mich darüber gewundert, als ich über eine Multithread-Engine nachgedacht habe. Also stellte ich eine Frage zu Stack Overflow, wie ein Entwurfsmuster für "Journaling" oder "Transaktionen" implementiert werden kann . Ich habe einige gute Antworten erhalten, und die akzeptierte Antwort hat mich wirklich zum Nachdenken gebracht.

Es ist schwierig, ein unveränderliches Objekt zu erstellen, da alle seine Kinder auch unveränderlich sein müssen und Sie wirklich darauf achten müssen, dass wirklich alles unveränderlich ist. Aber wenn Sie in der Tat vorsichtig sind, können Sie eine Superklasse erstellen, GameStatedie alle Daten (und Unterdaten usw.) in Ihrem Spiel enthält. der "Modell" -Teil des Organisationsstils von Model-View-Controller.

Dann, wie Jeffrey sagt , sind Instanzen Ihres GameState-Objekts schnell, speichereffizient und threadsicher. Der große Nachteil ist, dass Sie das Modell neu erstellen müssen, um Änderungen am Modell vorzunehmen. Sie müssen also wirklich darauf achten, dass Ihr Code nicht zu einem großen Durcheinander wird. Das Setzen einer Variablen im GameState-Objekt auf einen neuen Wert ist nicht nur var = val;in Bezug auf Codezeilen von Bedeutung.

Ich bin furchtbar fasziniert davon. Sie müssen nicht bei jedem Frame Ihre gesamte Datenstruktur kopieren. Sie kopieren einfach einen Zeiger auf die unveränderliche Struktur. Das allein ist sehr beeindruckend, stimmst du nicht zu?

Ricket
quelle
Es ist in der Tat eine interessante Struktur. Ich bin mir jedoch nicht sicher, ob es für ein Spiel gut funktionieren würde - da der allgemeine Fall ein ziemlich flacher Baum von Objekten ist, die sich jeweils genau einmal pro Frame ändern. Auch weil die dynamische Speicherzuweisung ein großes Nein ist.
Andrew Russell
Eine dynamische Zuordnung ist in einem solchen Fall sehr einfach und effizient durchzuführen. Sie können einen kreisförmigen Puffer verwenden, von einer Seite wachsen und von der zweiten wieder ablösen.
Suma
... das wäre keine dynamische Zuweisung, sondern nur eine dynamische Verwendung des vorab zugewiesenen Speichers;)
Kaj
1

Ich begann damit, drei Kopien des Spielstatus jedes Knotens in meinem Szenendiagramm zu haben. Einer wird vom Szenengrafenthread beschrieben, einer wird vom Renderer gelesen, und ein dritter steht zum Lesen / Schreiben zur Verfügung, sobald einer dieser Threads ausgetauscht werden muss. Das hat gut funktioniert, war aber zu kompliziert.

Dann wurde mir klar, dass ich nur drei Zustände von dem behalten muss, was gerendert werden sollte. Mein Update-Thread füllt jetzt einen von drei viel kleineren Puffern von "RenderCommands", und der Renderer liest aus dem neuesten Puffer, in den gerade nicht geschrieben wird, wodurch verhindert wird, dass die Threads jemals aufeinander warten.

In meinem Setup verfügt jeder RenderCommand über die 3D-Geometrie / -Materialien, eine Transformationsmatrix und eine Liste von Lichtquellen, die sich darauf auswirken (wobei weiterhin das Forward-Rendering ausgeführt wird).

Mein Render-Thread muss keine Culling- oder Light-Distance-Berechnungen mehr durchführen, und dies beschleunigt die Arbeit bei großen Szenen erheblich.

Dwayne
quelle