Wenn ich ein Spiel mit SDL baue, ist das Erste, was ich schreibe, der Game-Loop. Input lesen, Welt um dt weiterrechnen, zeichnen, und das 60 Mal pro Sekunde. Neulich hab ich mich gefragt, wo dieser Loop eigentlich bei den Browsergames steckt, mit denen ich Mitte der 2000er meine Nächte verbracht hab. Bei OGame, Travian oder Die Stämme wird ein Gebäude um 3:14 Uhr fertig und eine Flotte schlägt um 4:02 Uhr ein, obwohl der Browser längst zu ist. Da muss doch irgendwer die ganze Zeit rechnen?
Muss er nicht. Meistens rechnet da niemand. Um das zu verstehen hab ich ein kleines Spiel gebaut, mich durch Stack Exchange, alte Foren und Mailinglisten gelesen und in den Code von acht Open-Source-Klonen geschaut. Das hier ist alles, was dabei rausgekommen ist. Ist ein langer Post geworden.
Wo ist der Loop?
Ein Spiel mit SDL sieht im Kern so aus:
while (running) { handle_input(); update(dt); // die Welt läuft weiter render(); }
Ein Server für ein Echtzeit-Multiplayerspiel macht im Prinzip dasselbe, nur ohne render(). Der tickt durch, egal ob gerade jemand was macht.
Die Browsergames der 2000er liefen meistens als PHP auf einem gemieteten Server, oft sogar auf Shared Hosting. Und PHP lebt nur so lange wie ein HTTP-Request. Request kommt rein, Skript läuft, HTML geht raus, Prozess ist weg. Da gibt es schlicht keinen Ort, an dem ein Loop laufen könnte. William Leader hat das 2010 auf Gamasutra so formuliert: "Web Servers don't normally have the luxury of running code without a page request" (Gamasutra 2010).
Viele Hoster hatten damals nicht mal Cronjobs. Auf der New Yorker PHP-Mailingliste hat Michael Haszprunar deshalb schon im November 2005 vorgeschlagen, jeden Wert mit einem Zeitstempel zu speichern, und "you just calculate the new value on access" (NYPHP, 2005). Gerechnet wird also erst, wenn jemand hinschaut. Das ist der älteste Beleg, den ich für das Muster gefunden hab, und eigentlich steht da schon die ganze Idee drin.
Grob gibt es drei Arten, wie Browsergames mit Zeit umgehen. Bei Earth: 2025 oder Kingdom of Loathing laden sich Züge oder Aktionspunkte auf, die man dann ausgibt. Bei Planetarion (stündlich) oder Hattrick (feste Termine in der Woche) wird die ganze Welt zu festen Zeitpunkten weitergerechnet. Und bei OGame, Die Stämme, Travian und fast allem, was danach kam, hat jede Aktion einen sekundengenauen Zeitpunkt, an dem sie fertig ist, und gerechnet wird nur bei Bedarf.
Ein bisschen Geschichte
Earth: 2025 (1996) von Mehul Patel war ein rundenbasiertes Strategiespiel, laut einer Rezension von 1998 "designed to be played directly on the web". Neue Spieler waren "under protection for 100 turns" und eine Runde ging ein paar Monate (Rezension, archiviert). Die Züge haben sich mit der Zeit angesammelt. Der Server musste also nur wissen, wann zuletzt Züge gutgeschrieben wurden.
Utopia (1998, laut Vice Januar 1999) ist vom selben Mehul Patel, damals 22 und Student an der University of Texas. Gebaut für Einwahlmodems, geschrieben in Python, gespielt in "Ages" von 10 bis 12 Wochen. Laut Patel hatte es zu Spitzenzeiten rund 100.000 aktive Spieler (Vice 2017, Wikipedia). Nach einem DoS-Angriff 2009 wurde es komplett neu geschrieben.
Planetarion (2000, Fifth Season AS aus Norwegen) ist das Spiel, das mir bei Ticks als Erstes einfällt. Die Welt wird jede Stunde aktualisiert und Bauten und Angriffe dauern eine feste Anzahl Ticks. Am Wochenende gab es Speedgames mit Ticks im Minutentakt. Im Oktober 2000 hatte es über 30.000 Spieler (Wikipedia).
OGame ging am 3. Oktober 2002 online. Geschrieben hat es Alexander Rösner ("Legor"), der heute Gameforge leitet. Zum 20. Geburtstag hat er der GameStar erzählt, dass das Ganze eine "Trotzreaktion" aus seiner Studentenzeit war (GameStar 2022, Wikipedia).
Die Stämme (2003) hat Hendrik Klindworth mit 19 programmiert, sein Bruder Eike hat die Grafik gemacht und Michael Zillmer kam dazu. Daraus ist InnoGames geworden (PocketGamer.biz 2017). Der erste Server stand im Zimmer von einem der Gründer (MCV 2017).
Kingdom of Loathing (2003) hat Zack "Jick" Johnson nach eigener Aussage in einer Woche gebaut: "I knew that if I took the project seriously, I'd never finish it." (Engadget 2010). Man bekommt 40 Abenteuer pro Tag, abgerechnet wird beim täglichen "Rollover" und ansammeln kann man maximal 200 (Wikipedia).
Travian (2004) kommt von Gerhard Müller, damals Chemiestudent an der TU München. Eine Runde dauert etwa 200 Tage und ist vorbei, wenn ein Weltwunder Stufe 100 erreicht. Im Januar 2011 sollen laut Betreiber rund 5,2 Millionen Leute gespielt haben (Wikipedia en, de).
Danach ging es richtig los. Gameforge hat im August 2007 40 Millionen registrierte und 6 Millionen aktive Accounts in 30 Ländern gemeldet (digitalproduction 2007) und im August 2010 schon 200 Millionen registrierte (gameswelt).
Die Zahlen sollte man aber nicht zu ernst nehmen. Registrierungen werden nur aufaddiert, da ist jeder Zweitaccount drin und jeder, der nach zehn Minuten wieder weg war. Die GameStar nennt für OGame 2022 rund 125.000 Spieler im Monat und etwa 70.000 Browser-Logins am Tag. Und genau da wird es für diesen Post interessant. Ein Server, der für 100 Millionen Accounts jede Sekunde rechnen müsste, wäre Wahnsinn. Ein Server, der nur rechnet, wenn einer von den 70.000 vorbeischaut, ist dagegen gar kein Problem.
Und dann war da noch die Spielkultur. In einer studentischen Projektdoku der Hochschule der Medien Stuttgart von etwa 2006 steht ganz trocken:
"Es ist üblich, sich nachts einen Wecker zu stellen, um weitere Aktionen starten zu können, um somit einen Vorteil gegenüber des Gegners zu haben."
Auf Hacker News erzählen ehemalige Spieler, wie sie mitten in der Nacht per IRC geweckt wurden, weil jemand "you've got incoming!" geschrieben hat, und von Angriffen, die extra so getimt waren, dass sie mitten in der Nacht des Opfers einschlagen (HN 1, HN 2). Das kommt direkt aus der Technik, dazu weiter unten mehr.
Lazy Evaluation
Die Idee ist so simpel, dass man sie fast übersieht. Man zählt den Metallstand eines Planeten nicht ständig hoch, sondern speichert drei Werte:
metal = 5000 -- Stand zum Zeitpunkt last_update metal_rate = 120 pro Stunde last_update = 12:00:00
Fragt um 14:30 jemand, wie viel Metall da ist, rechnet man einfach:
metal(jetzt) = metal + metal_rate × (jetzt - last_update)
= 5000 + 120 × 2,5 h
= 5300
Zwischen zwei Anfragen passiert auf dem Server gar nichts. Die Kurve gibt es nur als Formel.
Geschrieben wird nur an den gefüllten Punkten, also wenn der Spieler etwas ausgibt oder sich die Rate ändert. Wenn er nur die Seite aufruft (hohle Punkte), wird gerechnet, aber nichts gespeichert.
Auf Stack Exchange steht das Muster spätestens seit 2010. Andrew Russell in der akzeptierten Antwort:
"you could just store the production rates, the base resource level, and a last-updated timestamp. [...] Whenever the production rate changes, update the base level to the actual level, and the timestamp to the current time."
Sean Middleditch hat es 2013 noch kürzer gesagt, und den Satz würde ich mir glatt an die Wand hängen:
"Find the difference. Divide by speed. Add to current resources. Cap the value. Done."
In meinem Beispielspiel sieht das in JavaScript so aus:
// Reine Rechnung: wie sieht der Spieler zum Zeitpunkt t aus? Schreibt nichts. function produced(p, t) { const dt = Math.max(0, t - p.last_update) / 1000; return { ...p, metal: p.metal + BUILDINGS.metal_mine.rate(p.metal_mine) * dt, crystal: p.crystal + BUILDINGS.crystal_mine.rate(p.crystal_mine) * dt, last_update: Math.max(t, p.last_update), }; } // Abrechnen und festschreiben. Muss vor jeder Änderung am Spieler passieren. function settle(id, t) { const p = produced(getPlayer(id), t); savePlayer(p); return p; }
Das Schönste daran ist, dass die Serverlast nur von den Spielern abhängt, die gerade aktiv sind. Philipp schreibt auf gamedev.SE: "So your total server load only depends on your current active users, not your total registered users." (gamedev.SE 141103). Ein Account, der seit 2009 nicht mehr eingeloggt war, kostet genau null CPU.
Ob seit dem letzten Besuch zehn Sekunden oder zehn Tage vergangen sind, ist auch egal, es bleibt dieselbe Multiplikation. Man hat sogar weniger Rundungsfehler. Wer jede Sekunde 0,033 Metall draufaddiert, sammelt Fließkommafehler ein, eine einzelne Multiplikation über die ganze Zeit hat das Problem nicht (Stack Overflow 2081518). Und der Browser kann dieselbe Formel benutzen. Die Ressourcen, die oben im OGame-Fenster hochzählen, sind genau diese Rechnung in JavaScript, nur eben für die Anzeige.
Wo es knifflig wird
So weit die Theorie. In der Praxis hab ich drei Stellen gefunden, an denen man sich die Finger verbrennt.
Die Mine wird mittendrin fertig
Sagen wir, die Metallmine geht um 13:00 von Stufe 7 auf Stufe 8, aber der Spieler schaut erst um 15:00 wieder rein. Rechnet man jetzt einfach neue_rate × 3 Stunden, schenkt man ihm eine Stunde Produktion auf Stufe 8, die er nie hatte. Richtig ist bis 13:00 mit der alten Rate und ab da mit der neuen.
Markus von Broady hat das 2012 am Beispiel OGame durchgerechnet. Jeder Planet hat ein last_calc, und wenn zwischendurch eine Mine fertig wurde, wird der Zeitraum in zwei Segmente geteilt (gamedev.SE 37489). In der Grafik oben ist das der Knick bei 24 Sekunden. Daraus folgt eine Regel, die man sich merken sollte: Jede Änderung der Rate ist ein Zeitpunkt, an dem abgerechnet werden muss. Deshalb sind fertige Gebäude in diesen Spielen Events, dazu gleich mehr.
Von Broady erwähnt noch einen Nebeneffekt, auf den ich nie gekommen wäre. Wenn der Client beim Spionieren selbst hochrechnet, verrät last_calc, wann ein Planet zuletzt angefasst wurde: "if main planet of a user wasn't refreshed for 5 days, one can be pretty sure the user didn't login." Ein Datenleck durch ein Implementierungsdetail.
Das Lager ist voll
Die meisten dieser Spiele haben Lager mit begrenzter Kapazität. Naheliegend ist min(wert + rate × dt, kapazität). DMGregory beschreibt auf gamedev.SE den Bug, der dabei entsteht, wenn man das Lager ausbaut. Wird erst beim Lesen gekappt und dann die Kapazität erhöht, bekommt der Spieler plötzlich die Produktion zurück, die vorher abgeschnitten war. Die Lösung ist dieselbe wie bei der Mine. Bei jeder Änderung der Kapazität wird der gekappte Wert gespeichert und der Zeitstempel neu gesetzt: "we bake-out any surplus production that could have leaked through the new cap, and reset the timestamp" (gamedev.SE 160691).
Middleditch hat in seiner Antwort von oben noch einen Kniff für ganze Einheiten. Wer "alle 30 Sekunden eine Energie" gutschreibt, setzt den Zeitstempel nicht auf jetzt, sondern auf jetzt minus den Rest der Division. Sonst verliert der Spieler bei jedem Besuch ein paar Sekunden.
Truppen essen Getreide
Bei Travian essen Truppen Getreide. Ist die Produktion unterm Strich negativ, wird der Vorrat kleiner. Laut offizieller Hilfe fängt der Hunger an, sobald "the granary has no crop left" und das Dorf weniger produziert, als Truppen und Bevölkerung brauchen. Dann sterben Truppen in einer festen Reihenfolge (Travian Support).
Genau da hakt William Leader 2010 ein. Mit Rate mal Zeit passiert so ein Ereignis eben nicht von selbst, deshalb hat er die Methode verworfen und einen Timer-Dienst gebaut. Man kann den Zeitpunkt aber auch einfach ausrechnen, denn der steht ja fest:
// Wann ist das Getreide alle? Bei negativer Rate vorab berechenbar. const secondsLeft = crop / -cropRate; // cropRate < 0 schedule('starvation', village.id, null, now + secondsLeft * 1000, {});
"Speicher leer" wird dann selbst zu einem Event. Ändert sich die Rate, weil neue Truppen oder eine neue Getreidefarm dazukommen, löscht man das alte Event und rechnet neu. Dasselbe geht für "Lager voll", falls das Spiel dann etwas machen soll.
Wann die Formel nicht mehr reicht
Die Formel funktioniert, solange die Raten konstant sind und nichts verbraucht wird. Eine unbeantwortete Frage auf gamedev.SE zeigt, wo das aufhört. In einem Idle-Spiel im Stil von Melvor Idle wird Erz zu Barren verarbeitet, und wenn das Erz alle ist, bricht die Aufgabe ab (gamedev.SE 182370). Dann muss man an jedem Punkt segmentieren, an dem ein Input leer wird, und bei langen Ketten von solchen Abhängigkeiten simuliert man am Ende doch wieder Schritt für Schritt. Clicker Heroes macht laut eigenem Blog genau das. Wenn man zurückkommt, läuft ein "Idle-Run" mit der aktuellen Schadensrate, und "There's no strict time limit on how long this simulation runs" (Clicker-Heroes-Blog).
Die Event-Tabelle
Ressourcen laufen kontinuierlich. Alles andere in einem Browsergame hat einen festen Zeitpunkt. Das Gebäude ist um 16:20 fertig, die Flotte kommt um 15:03:12 an, die Forschung um 9:00. Das alles landet als Zeile in einer Tabelle:
CREATE TABLE events ( id INTEGER PRIMARY KEY, type TEXT NOT NULL, -- build_done, fleet_arrive, fleet_return, ... player_id INTEGER NOT NULL, target_id INTEGER, fires_at INTEGER NOT NULL, -- Zeitpunkt in Millisekunden