Erklärung zu "fixed time steps"

daniel

Hallo,
in einer Dokumentation zu SFML wird das Prinzip von "fixed time steps" mit Beispiel erklärt. "Variable time steps" habe ich oft benutzt und verstehe sie, aber dieses Prinzip mag mir sich nicht erschließen. Was getan wird, erkenne ich, aber nicht warum.
Das Beispiel sieht folgendermaßen aus:

void Game::run()
{
    sf::Clock clock;
    sf::Time timeSinceLastUpdate = sf::Time::Zero;
    while (mWindow.isOpen())
    {
        processEvents();
        timeSinceLastUpdate += clock.restart();
        while (timeSinceLastUpdate > TimePerFrame)
        {
            timeSinceLastUpdate -= TimePerFrame;
            processEvents();
            update(TimePerFrame);
        }
    render();
    }
}

Zeile 8, 9 und 11 sind die Ursachen der Verwirrung

Danke für eure Antworten

hustbaer

Das ist zwar relativ einfach sobald man es mal verstanden hat, aber für mich relativ schwer in geschriebener Sprache und noch dazu ohne direktes Feedback zu erklären.

Die Ziele sind:

So oft wie möglich render() aufrufen
Dazwischen update() so oft aufrufen dass die Logik-Zeit möglichst nah an der realen Zeit bleibt

Nehmen wir mal der Einfachkeit halber an wir wollen 100 Logik-Frames pro Sekunde, also einen alle 10ms. Angenommen das Rendern des 1. Frames braucht 30ms. Für Variable Time Steps würdest du jetzt einfach update(30) aufrufen. Wollen wir aber nicht, wir wollen update(10) aufrufen. D.h. wir müssen update(10) 3x aufrufen. Sagen wir die drei Aufrufe von update(10) und das Rendern des nächsten Frames brauchen in Summe 50ms. Dann müssen wir update(10) 5x aufrufen damit der Zustand des Spiels "aufholen" kann.

Nur... was machen wir wenn die update und render Aufrufe z.B. immer 15ms brauchen? Wenn wir update pro Frame nur 1x aufrufen läuft das Spiel zu langsam und wenn wir update pro Frame 2x aufrufen zu schnell. Noch schlimmer wäre es wenn das ganze nur z.B. 3ms braucht und wir update daher gar nicht mehr aufrufen - das Spiel würde stehen bleiben. Also müssen wir das irgendwie fixen.

Die einfachste Weise wie wir das fixen können, ist wenn wir uns die Zeit merken die wir schon an update übergeben haben. Also die Zeit die dem internen, logischen Zustand des Spiels entspricht. Nennen wir diese logicTime. Und nennen wir die echte Zeit realTime.

Dann könnten wir z.B. folgenden Loop schreiben (Pseudocode, ich hab keine Ahnung wie die Funktionen in SFML wirklich heissen):

void run() {
	Clock clock; // Startet *jetzt* bei 0 zu zählen
	Time logicTime = 0;
	while (true) {
		Time realTime = clock.now(); // Aktuelle Zeit auslesen ohne die Clock zu resetten
		// So oft update() aufrufen bis die logic-time zur real-time aufgeholt hat
		while (logicTime < realTime) {
			processEvents();
			update(TimePerFixedLogicFrame);
			logicTime += TimePerFixedLogicFrame;
		}
		render();
	}
}

Der von dir gezeigte Code macht im Prinzip genau das selbe. Es gibt bloss zwei Unterschiede:

Er verwendet keine absoluten Zeitstempel sondern Merkt sich bloss wie sehr die Logic-Time hinter der echten Zeit zurückhinkt. timeSinceLastUpdate entspricht realTime - logicTime in meinem Beispiel.
In meinem Beispiel rufe ich update so lange auf bis die Logic-Time die echte Zeit überholt hat (oder exakt den gleichen Wert hat). In deinem Beispiel wird verhindert dass die Logic-Time die echte Zeit überholt. Macht aber im Prinzip keinen Unterschied.

Oder anders gesagt: timeSinceLastUpdate enthält in deinem Beispiel bei jedem render() Aufruf die Zeitdauer mit der wir update() noch ein weiteres mal hätten aufrufen wollen, es aber nicht konnten weil es weniger als unser fixer Timestep für die Gamelogik war.

BTW: Das allgemeine Prinzip hinter der timeSinceLastUpdate Variable nennt sich Error-Diffusion. Das wird z.B. auch verwendet um Linien in einem Pixel-Raster zu zeichnen die eine Steigung haben die nicht genau 1:N oder N:1 ist (also 2/3, 3/4, 42/31415 etc.). Bzw. zum Erzeugen von Mischfarben in Bildern, wenn einem nur eine begrenzte Anzahl an möglichen Farben zur Verfügung steht.
Siehe
https://en.wikipedia.org/wiki/Error_diffusion
https://en.wikipedia.org/wiki/Bresenham's_line_algorithm
https://en.wikipedia.org/wiki/Floyd–Steinberg_dithering

@hustbaer sagte in Erklärung zu "fixed time steps":

TimePerFixedLogicFrame

Wo wird dieser Wert gesetzt, in der Update Funktion z.B. per Referenz?

daniel

@hustbaer Ah Vielen vielen Dank, ich glaube, ich habe es verstanden. Wenn immer die gleiche Zeit an update übergeben wird, kann ich die Übergabe ja auch weglassen, wenn meine Berechnungen z.B so : player. x += vel.x * distancePerFrame aussehen. Wenn mein Update öfter als render aufgerufen wird, kann der Bildschirm doch anfangen dem tatsächlichen Zustand hinterherzuhinken, so dass es rucklige Übergänge gibt?
Danke für die Links

daniel

@chris4cpp Ich glaube vorher z.B am Funktionsanfang oder im Header, wo man einfach mit z.B 1 / 60 seine präferierte FPS setzt.

Ah danke, aber was ist wenn dann die Logik mehr als ein FPS braucht, weil z.B. mehr Einheiten berechnet werden müssen, dann sollte doch der Wert dynamisch in der Update Funktion beschrieben werden?

daniel

@chris4cpp Ich bin mir nicht sicher, aber wenn (Ausgehend vom ersten Beispiel)
TimePerFrame = 0.1s ist, das Updaten 1s dauert und das Rendern 0.1s, was sehr unwahrscheinlich ist:

Durchlauf:
render()
Durchlauf:
update()
render()
Durchlauf:
11 x update()
render()
Durchlauf:
111 x update()
render()

Update soll immer die gleiche TimePerFrame bekommen (Hier 0.1s). Wenn update() 1s und render() 0.1s dauern, ist die timeSinceLastUpdate also 1.1s. Daher wird im nächsten durchgang 11 x die while Schleife durchgegangen, weil solange 0.1s abgezogen werden, bis die timeSinceLastUpdate kleiner als TimePerFrame ist.
Das braucht aber jetzt wieder 11 x 1s, so dass immer öfter update() und nur ganz selten render() aufgerufen wird. Das verhältnis von Update- zu Renderaufrufen steigt bei dieser Ausgangsituation circa um den Faktor 10x pro neuem Durchgang. Aber update() bekommt immer die gleiche Zeit
Ich hoffe ich rede keinen Unsinn

TGGC

Und deswegen wird das in keinen realen Projekt so umgesetzt. Wenn die gemessene vergangene Zeit zu gross ist, wird man die clampen, so das es z.B. max 5 Updates gibt und das Programm in dem Moment einfach langsamer läuft.

hustbaer

@daniel sagte in Erklärung zu "fixed time steps":

Wenn immer die gleiche Zeit an update übergeben wird, kann ich die Übergabe ja auch weglassen

Richtig. Ausser wenn du ein Framework verwendest wo im Gerüst bereits eine Update-Funktion enthalten ist die einen Delta-Time Wert als Parameter hat. Ich kenne SFML nicht, daher weiss ich nicht wie das bei SFML ist.

hustbaer

@TGGC sagte in Erklärung zu "fixed time steps":

Wenn die gemessene vergangene Zeit zu gross ist, wird man die clampen, so das es z.B. max 5 Updates gibt und das Programm in dem Moment einfach langsamer läuft.

Interessanterweise ist das in der timeSinceLastUpdate Version ~~viel~~ etwas einfacher umzusetzen als in meinem Beispiel. Vielleicht ist ja das der Grund dass das SFML Beispiel so aussieht wie es aussieht. Nur wäre dann gut den Punkt in dem Beispiel auch zu erwähnen oder gleich mit in den Code aufzunehmen.

TGGC

Naja, man kann oben einfach noch eine Zeile einfügen, das reichte ja. Direkt nach der Zeitmessung: logicTime = max(realTime - 200, logicTime);

hustbaer

@TGGC
Ja, hast recht.

Dann verstehe ich weiterhin nicht warum man den Code mit timeSinceLastUpdate schreiben würde, ich finde meine Variante nämlich einfacher zu verstehen. Aber gut, mega-kompliziert sind jetzt beide nicht.

Finnegan

@daniel sagte in Erklärung zu "fixed time steps":

player. x += vel.x * distancePerFrame

Wo du schon dabei bist: Weisst du auch, weshalb du überhaupt feste Zeitschritte eventuell einsetzen möchtest? Es kann mehrere Gründe geben, die obige Zeile zeigt einen davon auf: Bei variablen Schritten kann diese nämlich dazu führen, dass sich der player z.B. auf zwei unterschiedlich schnellen Rechnern selbst bei frame-exakten, identischen Eingaben nachher an verschiedenen Positionen befindet.

hustbaer

@Finnegan sagte in Erklärung zu "fixed time steps":

dass sich der player z.B. auf zwei unterschiedlich schnellen Rechnern selbst bei frame-exakten, identischen Eingaben nachher an verschiedenen Positionen befindet

Frame-exakte, identische Eingaben sind irgendwie schwer wenn die Rechner nicht gleich schnell sind, nen? (Weil ja dann die Frames zu unterschiedlichen Zeiten anfangen und es auch unterschiedlich viele Frames sind.) Man kann maximal die Inputs zur exakt identischen Zeit (relativ zum Spielstart) machen. Und: selbst bei nem fixed time step Game-Loop kann das dann passieren. Da man auf unterschiedlich schnellen Rechnern die Inputs nicht immer zur selben Zeit abgreift.

Das ist also weniger der Grund. Es wäre schön wenn man es erreichen könnte, aber man schafft es nicht.

Gibt aber andere Vorteile die man sehrwohl erreicht. z.B. bekommt man mit variablen Steps so Sachen wie unterschiedliche Sprung-Höhe oder -Weite, andere Kurvenradien, z.T. kann man bei krassen Spikes durch Wände laufen etc. Das alles lässt sich mit fixed time steps fixen.

TGGC

Zur "gleichen Zeit" -> im selben lock-step

Finnegan

@hustbaer sagte in Erklärung zu "fixed time steps":

Frame-exakte, identische Eingaben sind irgendwie schwer wenn die Rechner nicht gleich schnell sind, nen?

Ich gebe zu, der Audruck "Frame" war hier etwas unglücklich gewählt. Nennen wir es mal besser "zeitgleich" bezüglich der Granularität der clock. Oder lassen wier die Eingaben mal gänzlich weg und lassen die Simulation einfach von einem vorgegebenen Ausgangszustand aus laufen.

Worauf ich eigentlich hinaus wollte, ist, dass man vielleicht gerne hätte, dass äquivalente Berechnungen - wie hier die der Spielerposition - zu identischen Ergebnissen führen, egal wie flott der Rechner ist. Ist distancePerFrame jedoch besonders klein oder groß, bekommt man es mit sehr unterschiedlichen Fließkomma-Rundungsfehlern zu tun, die durch die Addition auch noch akkumuliert werden. Die selbe Simulation driftet auf unterschiedlichen Rechnern also immer weiter auseinander...

Gibt aber andere Vorteile die man sehrwohl erreicht. z.B. bekommt man mit variablen Steps so Sachen wie unterschiedliche Sprung-Höhe oder -Weite, andere Kurvenradien, z.T. kann man bei krassen Spikes durch Wände laufen etc. Das alles lässt sich mit fixed time steps fixen.

... und das ist im Prinzip auch dasselbe, was du hier beschreibst. Mathematisch sind diese Berechnungen äquivalent, die Unterschiede kommen hier eben durch Rundungsfehler und unterschiedlich große Steps zustande.

hustbaer

@Finnegan sagte in Erklärung zu "fixed time steps":

Mathematisch sind diese Berechnungen äquivalent, die Unterschiede kommen hier eben durch Rundungsfehler und unterschiedlich große Steps zustande.

Ich würde das nicht mathematisch äquivalent nennen. Das Problem sind nämlich weniger die Rundungsfehler sondern die Fehler die bei der numerischen Integration entstehen. Die sind nämlich normalerweise sehr viel grösser.

Wenn du z.B. deine Spielfigur springen lässt, dann machst du z.B. etwas wie

this->position += this->speed * dT;
this->speed.y -= g * dT;

Und dabei kommt halt was anderes raus wenn du es 1x mit dT=X ausführst bzw. 10x mit dT=X/10 -- selbst wenn du mit unendlicher Genauigkeit rechnest.

Finnegan

@hustbaer sagte in Erklärung zu "fixed time steps":

Ich würde das nicht mathematisch äquivalent nennen.

Ja das stimmt, die hatte ich dabei nicht auf dem Schirm. Habe mich zu sehr auf die eine zitierte Zeile fixiert und nicht an dieses größere Problem gedacht. So ist es das natürlich nicht äquivalent. Bin hier auch von einem (urealistischen) konstanten vel ausgegangen. Rundungsfehler sind durchaus ein anderes Problem, aber wie du schon sagst, ein eher kleineres.

this->position += this->speed * dT;
this->speed.y -= g * dT;

Jo, schon klar. Die Geschwindigkeit ist hierbei stückweise konstant und ignoriert die Beschleuinigung zwischen den Steps ("springt" also direkt auf eine neue Geschwindigkeit). Man integriert also eigentlich eine annähernde Treppenfunktion.

hustbaer

@Finnegan Genau. Und da sich in Spielen Geschwindigkeiten oft quasi-stetig und nicht sprunghaft ändern, hat man das relativ oft