Framerate-unabhängige Spiellogik
In diesem Artikel wird die Frage betrachtet, wie man sein Spiel so programmiert, dass es unabhängig von der Framerate bzw. unabhängig von der Geschwindigkeit des Computers immer gleich schnell abläuft.
Inhaltsverzeichnis |
Einleitung
Wer sich noch an die Anfangszeit der Computerspiele erinnern kann, der wird sich vielleicht auch an eine Eigenart einiger damaliger Spiele erinnern. Viele von ihnen waren für spezielle Computer programmiert und an deren Rechengeschwindigkeit angepasst. Versuchte man sie auf einem neueren, schnelleren Computer zu spielen, so liefen sie dort viel schneller ab als auf dem Rechner, für den sie entwickelt wurden. Was diesen Spielen fehlte, war also eine Framerate-unabhängige Spiellogik oder eine einfache Begrenzung der Framerate. Diese Spiele berechneten ihre Spiellogik einfach so oft wie es möglich war, ohne auf die vergangene Zeit zu achten und sicherzustellen, dass sie nicht zu schnell (oder zu langsam) laufen. Heutige Computerspiele können sich so etwas nicht mehr leisten. Selbst solche für Konsolen nicht, obwohl deren Rechenleistung genau bekannt und festgelegt ist, denn auch dort kommt es vor, dass das Spiel stellenweise mehr oder weniger Zeit benötigt, um die Grafik zu zeichnen und die Spiellogik zu berechnen.
Ein typischer Main-Loop
Der Teil des Spiels, um den es in diesem Artikel geht, ist der Main-Loop. Das ist die Schleife, die während des ganzen Spiels ständig durchlaufen wird und in der die Spiellogik, Grafik, Audio usw. koordiniert werden. Ein solcher Main-Loop könnte in Pseudocode wie folgt aussehen:
Solange das Spiel nicht beendet werden soll:
SpielzustandZeichnen()
SpielzustandAktualisieren()
FertigesBildAnzeigen()
In SpielzustandZeichnen werden die Zeichenbefehle an die Grafikhardware übermittelt. Während diese dann mit dem Rendering beschäftigt ist, kann die Spiellogik in SpielzustandAktualisieren berechnet werden. Anschließend wird das fertige Bild angezeigt (zuvor muss normalerweise auf die vertikale Synchronisation gewartet werden, damit der Spieler ein komplettes einheitliches Bild präsentiert bekommt).
In der oben gezeigten Version fehlt jedoch noch die Komponente Zeit. Die Geschwindigkeit des Spiels ist direkt an die Anzahl der Schleifendurchläufe pro Sekunde gekoppelt, und das ist unerwünscht. Darum messen wir für jeden Schleifendurchlauf die benötigte Zeit Δt und teilen der Funktion SpielzustandAktualisieren im nächsten Durchlauf mit, dass sie das Spiel um genau dieses Zeitintervall weiter berechnen/simulieren soll.
Δt = 0
Solange das Spiel nicht beendet werden soll:
t0 = Zeit()
SpielzustandZeichnen()
SpielzustandAktualisieren(Δt)
FertigesBildAnzeigen()
Δt = Zeit() - t0
Nun liegt es in der Verantwortung der Funktion SpielzustandAktualisieren, dass sie das Spiel um Δt Sekunden weiter berechnet. Wie sie das tun kann, wird im nächsten Abschnitt behandelt.
Variable und feste Zeitschritte
Prinzipiell gibt es zwei Ansätze, wie man die Aufgabe "berechne das Spiel um Δt Sekunden weiter" lösen kann, nämlich mit variablen oder festen Zeitschritten.
Variable Zeitschritte
Bei der Methode der variablen Zeitschritte wird versucht, das Spiel in einem einzigen Aktualisierungszyklus um beliebige Zeitintervalle weiter zu berechnen. Betrachten wir als Beispiel den Code zur Bewegung eines Objekts:
Prozedur ObjektBewegen(Objekt, Δt):
Objekt.Position = Objekt.Position + Δt * Objekt.Geschwindigkeit
Hier wird die Geschwindigkeit des Objekts mit dem Zeitschritt multipliziert. Wie weit sich das Objekt nun bewegt, hängt jetzt vom Zeitschritt ab. Wenn das Spiel also langsam läuft (wenige Schleifendurchläufe pro Sekunde), dann wird das Objekt pro Durchlauf weiter fortbewegt als wenn das Spiel schnell läuft. Insgesamt bewegt sich das Objekt dann unabhängig von der Framerate immer gleich schnell.
Die Methode der variablen Zeitschritte funktioniert für solche einfachen Beispiele sehr gut. Betrachten wir nun einen Fall, in dem ein Objekt beschleunigt wird, also seine Geschwindigkeit ändert:
Prozedur ObjektBewegen(Objekt, Δt):
Objekt.Position = Objekt.Position + Δt * Objekt.Geschwindigkeit
Objekt.Geschwindigkeit = Objekt.Geschwindigkeit + Δt * Objekt.Beschleunigung
Obwohl diese Implementierung harmlos aussieht, leidet sie unter einem Problem. Die erste Zeile in der Prozedur geht nämlich davon aus, dass die Geschwindigkeit des Objekts während der gesamten Zeitspanne Δt gleich bleibt. Dies ist jedoch nicht der Fall, denn das Objekt wird beschleunigt, wie in der zweiten Zeile zu sehen ist. Korrekterweise müsste die aus dem Physikunterricht bekannte Formel §s = \tfrac{1}{2} \cdot a \cdot t^2§ angewendet werden. Der Fall ist also schon komplizierter geworden. Wenn zusätzlich auch noch angenommen werden muss, dass die Beschleunigung nicht konstant ist (was beispielsweise der Fall wäre, wenn das Objekt die Schwerkraft eines anderen Objekts spürt, deren Stärke von der Entfernung abhängt), dann wird es langsam unüberschaubar kompliziert.
Vorteile
Ein Vorteil bei der Verwendung variabler Zeitschritte besteht darin, dass die Aktualisierung des Spiels im Wesentlichen immer gleich viel Zeit benötigt, egal wie groß der Zeitschritt gerade ist. Dies gilt jedoch nur für einfache Spiellogik wie die oben gezeigte Bewegung eines Objekts. Dadurch ist man mit variablen Zeitschritten in der Lage, sowohl zu langsam als auch zu schnell ablaufende Spiele in den Griff zu bekommen. Zudem ist es möglich durch sehr kleine Zeitschritte eine "Zeitlupenfunktion" zu implementieren.
Nachteile
Wie bereits gezeigt, kann die Aktualisierungslogik bei der Verwendung variabler Zeitschritte sehr kompliziert werden. Im Allgemeinen machen sich die Probleme bei variablen Zeitschritten dadurch bemerkbar, dass ...
SpielzustandAktualisieren(0.1)
... und ...
SpielzustandAktualisieren(0.05) SpielzustandAktualisieren(0.05)
... zu verschiedenen Ergebnissen führen können. Eigentlich sollte es aber keinen Unterschied machen, ob das Spiel um 0.1 Sekunden weiter berechnet wird oder zweimal hintereinander um 0.05 Sekunden.
Dieses Problem besteht leider sogar dann, wenn man innerhalb der SpielzustandAktualisieren-Prozedur an allen Stellen den Zeitschritt Δt korrekt berücksichtigt. Der Grund dafür liegt in den Eigenarten der Gleitkommaarithmetik (float- und double-Datentypen in den meisten Programmiersprachen). Bei diesen Datentypen gilt nämlich weder das Assoziativ- noch das Distributivgesetz, das heißt §(x + y)+ z \neq x + (y + z)§ (gleiches für die Multiplikation) und §x \cdot (y + z) \neq (x \cdot y) + (x \cdot z)§.
Variable Zeitschritte sind auf gewisse Vorgänge eines Spiels nicht anwendbar:
- Das klassische Dreikörperproblem kann (bis heute) nicht direkt, sondern nur iterativ gelöst werden. Damit ist eine exakte Berechnung der Flugbahn von Objekten, die gravitativen Kräften ausgesetzt sind, mit rein variablen Zeitschritten unmöglich. Die iterative Berechnung würde den Geschwindigkeitsvorteil der variablen Zeitschritte wieder auslöschen.
- Eine künstliche Intelligenz, die bei jedem Aufruf von SpielzustandAktualisieren "denkt", also ihre nächste Handlung plant, wird auf einem schnellen Rechner pro Sekunde öfters aufgerufen als auf einem langsamen Rechner und darf damit auch pro Sekunde mehr "denken". Auf einem schnelleren Rechner würde sie schneller auf den Spieler reagieren können und wäre dadurch schwerer zu schlagen. Dass dieses Verhalten unerwünscht ist, muss eigentlich nicht erwähnt werden.
- Eine naiv implementierte Kollisionserkennung, die nur jeweils für den aktuellen Zeitpunkt überprüft, ob Objekte zusammenstoßen, kann bei genügend großen Zeitschritten und dünnen/schnellen Objekten Kollisionen verpassen. Die Kollisionserkennung so zu erweitern, dass sie Kollisionen während einer gegebenen Zeitspanne erkennt, ist aufwendig – ohne Unterteilung in kleinere Zeitschritte vermutlich sogar praktisch nicht umsetzbar.
Feste Zeitschritte
Im Gegensatz zu der Methode variabler Zeitschritte wird bei der Methode fester Zeitschritte das Spiel (oder ein Teil davon) immer nur in festen, diskreten Zeitschritten berechnet. Wenn die Länge des festen Zeitschritts beispielsweise §\tfrac{1}{60}\mathrm{s}§ beträgt, dann muss das Spiel dafür sorgen, dass die Aktualisierung auch 60-mal pro Sekunde stattfindet ("Logikrate"). Das kann wie folgt gelöst werden:
Konstante Logikrate = 60
Konstante Zeitschritt = 1 / Logikrate
Zeitkonto = 0
Prozedur AktualisiereSpielzustand(Δt):
Zeitkonto = Zeitkonto + Δt
Solange Zeitkonto ≥ Zeitschritt:
ZeitschrittDurchführen()
Zeitkonto = Zeitkonto - Zeitschritt
In der Variablen namens Zeitkonto merken wir uns, wie viel Zeit das Spiel noch abarbeiten muss. Sie wird in AktualisiereSpielzustand um den übergebenen Wert Δt erhöht (die Zeit, die für den vorherigen Schleifendurchlauf benötigt wurde). Wenn Zeitkonto mindestens so groß ist wie ein elementarer Zeitschritt (Konstante Zeitschritt), werden so lange elementare Zeitschritte durchgeführt, bis die abzuarbeitende Zeit wieder kleiner als Zeitschritt ist.
Betrachten wir folgendes Beispiel: Die Logikrate ist 60, die Länge eines elementaren Zeitschritts daher §\tfrac{1}{60}\mathrm{s}§, was ungefähr 16.7 Millisekunden entspricht. Wenn nun Zeitkonto den Wert 0.055 hat, also das Spiel 55 Millisekunden abzuarbeiten hat, dann werden in der Prozedur AktualisiereSpielzustand drei elementare Zeitschritte durchgeführt. Diese drei Zeitschritte decken 50 Millisekunden ab, auf dem Zeitkonto bleiben also danach noch 5 Millisekunden übrig. Auf diese Weise geht keine Zeit "verloren".
Vorteile
Dadurch, dass das Spiel immer nur um einen festen Zeitschritt weiter berechnet werden muss, ist diese Berechnung einfacher bzw. unkomplizierter. Wenn die Logikrate hoch genug gewählt ist, also der feste Zeitschritt klein genug ist, können viele Probleme vereinfacht betrachtet werden. Für den Fall des beschleunigten Objekts kann man zum Beispiel näherungsweise annehmen, dass die Geschwindigkeit innerhalb des kurzen Zeitschritts konstant ist.
Mit festen Zeitschritten ist außerdem immer gewährleistet, dass SpielzustandAktualisieren(0.1) dieselbe Wirkung hat wie ein zweifacher Aufruf von SpielzustandAktualisieren(0.05), da letztendlich bei beiden Varianten gleich viele elementare Zeitschritte ausgeführt werden.
Aus diesen Vorteilen ergibt sich eine relativ einfache Möglichkeit zur Realisierung einer Replay- oder Demo-Funktion in einem Spiel. Dazu müssen bei der Aufnahme alle Benutzereingaben (Tastendruck, Mausbewegung usw.) zusammen mit einem Zeitstempel (der logischen Frame-Nummer) abgespeichert und beim Abspielen zum entsprechenden Zeitpunkt wieder in das Spiel eingespeist werden. Vorausgesetzt, dass die Benutzereingabe das einzige maßgeblich beeinflussende Kriterium für den Ablauf des Spiels darstellt, wird die Aufnahme beim Wiederabspielen genau so aussehen wie das Original. Eventuell vorhandene Zufallsgeneratoren sollten dazu natürlich mit dem gleichen Startwert initialisiert werden. Diese Art der Implementierung ist wesentlich unkomplizierter als beispielsweise das Abspeichern der Objektzustände zu jedem Zeitpunkt.
Nachteile
Bei einer einfachen Implementierung stellt die Logikrate eine obere Schranke für die Bildwiederholrate dar. Ein Spiel, das 30 Logik-Schritte pro Sekunde durchführt, kann auch nur 30 sinnvolle Bilder pro Sekunde anzeigen, da es "dazwischen" keine neuen Spielzustände gibt. Dies kann jedoch mit einigem Aufwand umgangen werden, indem einzig für die Grafikdarstellung zwischen den letzten beiden berechneten Spielzuständen interpoliert wird (wodurch allerdings eine kleine Verzögerung entsteht).
Die Methode fester Zeitschritte erfordert, dass der Rechner prinzipiell in der Lage ist, die angeforderte Anzahl von Logik-Schritten zu berechnen. Mit anderen Worten: Das Spiel muss die Zeit auf dem Zeitkonto schneller abarbeiten als sie angesammelt wird. Ansonsten steigt der Wert auf dem Zeitkonto kontinuierlich an, und jeder Aufruf von SpielzustandAktualisieren dauert länger als der vorherige, bis das Spiel völlig unspielbar wird. Diesen Fall gilt es zu erkennen. Steigt das Zeitkonto dauerhaft an, so ist davon auszugehen, dass der Rechner für die gewählte Logikrate zu langsam ist. Die Logikrate kann jedoch nicht zur Laufzeit geändert werden, da der Vorteil fester Zeitschritte gerade darin besteht, sich auf eben diese verlassen zu können. In diesem Fall könnte dem Spieler eine Warnung angezeigt werden, oder der Detailgrad einiger rechenintensiver Effekte könnte automatisch reduziert werden. Um einen weiteren Anstieg des Zeitkontos zu verhindern, kann das gesamte Spiel verlangsamt werden, indem Δt vor dem Aufsummieren mit einem Verlangsamungsfaktor multipliziert wird.
