hrxdev#2 Eine Welt, Spielstände, Replays und ein Fehler, der sich im Speicherformat versteckte
· Nick
Seit dem ersten Eintrag hat der Kern eine Welt bekommen, in die man Dinge stellen kann, Dateien, in denen sie aufbewahrt wird, und einen Weg zu beweisen, dass zwei Läufe übereinstimmen. Noch immer keine Grafik und keine Figuren. Der Großteil dieses Eintrags ist Rohrleitungsbau, und ein Teil davon ist ein Fehler, der die Geschichte wert war.
Eine Welt aus Kacheln
Die Welt ist ein Raster aus Kacheln von 1×1 m auf diskreten Ebenen, von null aufwärts nummeriert. Eine Wand oder eine Tür ist eine Kachel; eine Treppe wird eine besondere Verbindung zwischen zwei Ebenen sein, aber Treppen gibt es noch nicht. Intern ist die Welt eine Reihe flacher Schichten (Boden, Struktur, Struktur-Flags) für die ganze Karte plus eine abgeleitete Schicht für die Begehbarkeit. Die Karte wird in Chunks von 16×16 mit Versionszählern verfolgt, damit ein Renderer oder eine Wegsuche fragen kann „hat sich dieser Bereich geändert?“, ohne Kacheln zu vergleichen.
Die Größe der Welt wird beim Erstellen festgelegt. Gebaut wird mit Befehlen, die ein Rechteck nehmen: Boden, Wand oder Tür über eine Fläche setzen oder entfernen. Ist ein Teil des Rechtecks blockiert, wird der Rest trotzdem gebaut, und der Befehl meldet, was er übersprungen hat. Vorerst gibt es drei eingebaute Kachelarten: Boden, Wand, Tür. Ab jetzt ist die Karte Teil des Welt-Hashs und der Spielstände. Sie wird an Tausenden zufälliger Befehle gegen ein langsames, offensichtlich korrektes Referenzmodell geprüft.
Spielstände und Replays
Spielstand und Replay teilen sich einen Dateicontainer. Er ist in beschriftete Abschnitte mit Typ und Version unterteilt, sodass neue Teile der Welt (Figuren, Bedürfnisse, Beziehungen) später neue Abschnitte werden können, ohne alte Dateien zu brechen. Es gibt Prüfsummen über Kopf und Inhalt, der Inhalt ist komprimiert, und jede Größe wird gegen eine Grenze geprüft, bevor Speicher reserviert wird. So kann eine beschädigte oder böswillige Datei das Spiel nicht dazu bringen, den ganzen Arbeitsspeicher zu fressen. Kachelarten werden mit Namen statt Nummern gespeichert, damit ein Spielstand weiter funktioniert, wenn sich die Liste der Arten ändert.
Ein Replay ist das, was ich von Anfang an wollte: ein Seed plus das Befehlsprotokoll. Beim Aufzeichnen schreibt der Kern zusätzlich alle 100 Ticks einen Kontroll-Hash. Beim Abspielen vergleicht er unterwegs das Ergebnis jedes Befehls und jeden Kontroll-Hash und hält beim ersten Tick an, an dem sie abweichen. Ein Replay merkt sich außerdem, welcher Build des Kerns es aufgezeichnet hat, sodass ein Replay aus einem anderen Build abgelehnt wird, statt still auseinanderzulaufen.
Der Kern selbst fasst nie Dateien an: Er liest und schreibt Streams, und das Spiel entscheidet, wo Spielstände liegen. Diese Grenze wird von derselben Maschinerie für verbotene APIs durchgesetzt wie zuvor.
Noch nicht fertig: ein Kommandozeilenwerkzeug, das eine Replay-Datei abspielt, und die Spielseite des Speicherns (ein Spielstandordner, automatisches Speichern, sicheres Schreiben).
Beweisen, dass zwei Läufe übereinstimmen
Der Determinismustest lässt jetzt ein Szenario in zwei getrennten Prozessen laufen: ein Seed, ein Skript aus Baubefehlen (einige absichtlich ungültig) und ein Testsystem, das aus jedem Zufallsstrom zieht. Jeder Prozess führt es auf drei Arten aus — direkt durch, über Speichern und Laden und über ein Replay der aufgezeichneten Bytes — und vergleicht die Hashes in jedem Tick. Danach vergleichen die beiden Prozesse ihre Hashes in jedem 10. Tick miteinander.
Ich habe ihn absichtlich kaputt gemacht, um sicherzugehen, dass er scheitern kann. Ein ungeseedetes Random, in den Tick geschmuggelt, färbte den Test rot. Ein randomisierter String-Hash, den .NET in jedem Prozess anders seedet, fiel innerhalb eines Prozesses nicht auf und wurde erst beim Vergleich zweier Prozesse gefunden. Genau dafür gibt es zwei Prozesse.
Die Regel, die ich festgeschrieben habe: Ein Build des Kerns muss auf x64- und arm64-Prozessoren dieselben Hashes liefern, also muss ein Replay, das auf einem Mac mit Apple-Chip aufgenommen wurde, auf einem Windows-PC laufen. Genau für diese Prüfung gibt es festgeschriebene Referenz-Hashes und Beispieldateien für Spielstand und Replay. Gleitkomma-Trigonometrie und Exponentialfunktionen unterscheiden sich zwischen Plattformen und sind deshalb überall tabu, wo sie die Welt beeinflussen; sobald ein System sie braucht, werde ich einen deterministischen Ersatz brauchen. Diese Referenzdateien ändern sich nur absichtlich: Weicht ein Hash ab, muss die Änderung erklärt werden, bevor sie akzeptiert wird.
Ein Benchmark, der Nein sagen kann
Es gibt jetzt einen Runner ohne Oberfläche, der ein Szenario, einen Seed und eine Anzahl Ticks nimmt und einen JSON-Bericht ausgibt: Median und 99. Perzentil der Zeit pro Tick, die Zahl der Agenten, den Welt-Hash und wie viele Bytes pro Tick alloziert wurden. Das erste Szenario baut eine Karte von 512×512 auf 16 Ebenen mit etwa 52.000 Baubefehlen.
Die Basislinie wird pro Rechner geführt, denn Zeiten von einem Laptop sagen auf einem Desktop nichts. Eine Regression ist ein Median mehr als 10 % über der Basislinie oder ein 99. Perzentil mehr als 35 % darüber, und nur wenn der Anstieg größer als 0,05 ms ist, denn ein fast leerer Tick liegt an der Auflösungsgrenze des Timers. Eine Schranke gilt auf jedem Rechner: null allozierte Bytes pro Tick. Ich sollte ehrlich sagen, was das heute misst. Ohne Systeme und Figuren dauert ein Tick etwa 35 Nanosekunden, die Zeitschranke schläft also meist, bis im Bewegungs-Meilenstein die ersten echten Systeme kommen. Die Allokationsschranke ist die, die jetzt arbeitet.
Der wackelige Test, der gar nicht wackelig war
Während ich den Benchmark baute, begann ein Test des Speicherformats bei manchen Builds zu scheitern, obwohl sich der Kern nicht geändert hatte. Der Test kippt nacheinander jedes Byte eines komprimierten Replays und verlangt, dass der Lader jedes einzelne ablehnt. Bei einem Build wurde ein Byte nahe dem Dateiende akzeptiert. Beim vorherigen Build bestand derselbe Test.
Warum es kam und ging: Ein Replay trägt die Kennung des Builds, der es geschrieben hat, also unterscheiden sich die komprimierten Bytes von Build zu Build, und mit ihnen das Byte, das gekippt wird. Das Loch war immer da; der Test bemerkte es nur, wenn die Würfel so fielen.
Das Loch selbst: Die Prüfsumme deckte die Daten nach dem Entpacken ab, und der Dekompressor von .NET erwies sich als nachsichtig. Er akzeptiert einen Stream, der nie sagt, dass er zu Ende ist, und ignoriert alles nach dem Ende. Kippt man ein Füllbit im letzten Byte, entsteht ein anderer, weiterhin gültiger Stream, der zu denselben Daten entpackt. Die Prüfsumme passte also noch, und eine beschädigte Datei wurde als gut geladen.
Die Lösung ist eine neue Container-Version. Die Prüfsumme deckt jetzt die Bytes so ab, wie sie in der Datei stehen, und wird vor dem Entpacken geprüft, und das Entpacken muss genau dort enden, wo der Kopf es sagt. Ein leerer Inhalt wird unkomprimiert gespeichert, weil der Kompressor für eine leere Eingabe nichts schreibt. Die Prüfungen nutzen jetzt feste komprimierte Streams, die nicht vom Build abhängen, plus Fuzzing beschädigter Dateien. Die Beispieldateien wurden für die neue Version neu erzeugt; die Welt-Hashes haben sich nicht geändert.
Sonst noch
Die Website, die du gerade liest, zeigt auf der Startseite jetzt zwei Besucherzähler: eindeutige Besucher insgesamt und in den letzten 24 Stunden. Gezählt wird aus dem Seitenprotokoll des Webservers, ohne JavaScript, ohne Cookies und ohne fremde Dienste. Eine Adresse wird nur als gesalzener Hash gespeichert, Bots werden über ihren User-Agent herausgefiltert, und die Zahlen hinken ein paar Minuten hinterher. Mehrere Leute hinter einem Netzwerk zählen als einer.
Als Nächstes
Der erste Meilenstein, das Kerngerüst, ist fertig. Als Nächstes kommt M1, die Bauansicht in Godot: Wände, Türen und Räume aus dem Weltmodell, Etagenschnitt, eine Kamera, die sich in 90°-Schritten dreht, und einfache Würfel statt Grafik. Die Arbeit daran hat noch nicht begonnen. Siehe die Roadmap.