Framerate-unabhängige Spiellogik

Aus Spieleprogrammierer-Wiki
Wechseln zu: Navigation, Suche

In diesem Artikel wird die Frage betrachtet, wie man sein Spiel so programmiert, dass es weitestgehend unabhängig von der Framerate bzw. unabhängig von der Geschwindigkeit des Computers gleich schnell abläuft. Im Wesentlichen werden wir uns mit zwei Methoden befassen, mit denen dies umgesetzt werden kann.

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, auf den sich dieser Artikel fokussiert, 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 bewegt, hängt von der Länge des Zeitschritts 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:

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".

Die oben gezeigte Implementierung tut nichts für den Fall, dass noch nicht genügend Zeit auf dem Zeitkonto ist. In diesem Fall sollte auch noch sichergestellt werden, dass anschließend kein neues Frame gezeichnet wird, denn es hat sich ja nichts verändert. Ein Aufruf von der betriebssystemabhängigen Sleep-Funktion könnte den Thread des Spiels für eine kurze Zeit schlafen legen. Insbesondere auf mobilen Geräten kann dies zu wichtigen Energieeinsparungen führen. Es muss jedoch beachtet werden, dass ein solcher Aufruf von Sleep nie exakt nach der angegebenen Zeit wieder zurückkehrt, sondern dass er auch länger dauern kann. Darum sollte lieber mehrfach kurz geschlafen werden als einmal lang.

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. Hier gilt es jedoch zu beachten, dass Berechnungen mit Gleitkommazahlen oft verschiedene Ergebnisse produzieren, abhängig vom Prozessor, dem Compiler und seinen Optimierungseinstellungen[1].

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)[2].

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. Alternativ kann eine obere Grenze für das Zeitkonto festgelegt werden.

Diese beiden Probleme erfordern eine vorsichtige Auswahl der Logikrate. Ist sie zu gering, so läuft das Spiel (ohne Interpolation) optisch nicht flüssig. Ist sie zu hoch, steigt die Gefahr, dass ein Rechner die geforderte Anzahl von Aktualisierungen pro Sekunde nicht bewältigen kann.

Diskussion

Sowohl die Methode variabler Zeitschritte als auch die Methode fester Zeitschritte hat ihre Vor- und Nachteile. Variable Zeitschritte sind potenziell schneller, dafür geht jedoch Determinismus verloren, und die Implementierung ist aufwändiger. Feste Zeitschritte sind einfacher zu implementieren, funktionieren generell immer, sind jedoch tendenziell langsamer. Zudem können sie mit dem Fall eines zu langsamen Rechners nicht gut umgehen.

In der Praxis können beide Ansätze kombiniert werden. Dabei können die verschiedenen Komponenten eines Spiels jeweils selbst entscheiden, welche Variante sie nutzen. Es empfiehlt sich dann, die für die Spiellogik relevanten Komponenten (Physik, künstliche Intelligenz, Eingabe) mit festen Zeitschritten zu behandeln und die übrigen, die nicht zur Spiellogik beitragen, mit variablen Zeitschritten. Dazu zählen beispielsweise rein optische Effekte wie Partikelsysteme. Bei diesen spielt es normalerweise keine Rolle, ob sie sich deterministisch verhalten, sondern es kommt in erster Linie auf die Geschwindigkeit an.

Erweiterungen

Erkennen kurzzeitiger Aussetzer

Ein Sonderfall, den es ggf. zu erkennen gilt, ist ein kurzzeitiger "Aussetzer" des Systems, auf dem das Spiel ausgeführt wird. Auf einem PC könnte dies durch einen Auslagerungsvorgang bedingt sein, auf einer mobilen Plattform wie Android machen sich Durchläufe des Garbage Collectors oft durch längere Pausen bemerkbar. Nach einem solchen Aussetzer muss entschieden werden, ob die verpasste Zeit aufgeholt werden soll. Wird sie aufgeholt, so wird beim nächsten Mal eine längere Aktualisierung folgen (großes Δt). Das Spiel macht damit einen längeren Sprung, bei dem der Spieler keine Gelegenheit hat auf Spielereignisse zu reagieren. Wenn das nicht erwünscht ist, muss ein solcher Aussetzer erkannt und anschließend die übersprungene Zeit ignoriert werden. Diese Erkennung ist beispielsweise möglich, indem ein gleitender Mittelwert über Δt berechnet wird. Ist ein gegebenes Δt deutlich größer als dieser Mittelwert (wie viel größer, sollte experimentell ermittelt werden), so kann dies als kurzzeitiger Aussetzer behandelt werden.

Einzelnachweise

  1. Floating Point Determinism. Glenn Fiedler. gafferongames.com – Glenn Fiedler's Game Development Articles and Tutorials. 24. Februar 2010.
  2. Fix Your Timestep!. Glenn Fiedler. gafferongames.com – Glenn Fiedler's Game Development Articles and Tutorials. 2. September 2006.
Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Werkzeuge