Header image Ingenieur, Vater, Heimwerker, Problemlöser

03 Mai, 2016

Die Engine

TL;DR:

Diesen Artikel wollte ich schon sehr, sehr lange schreiben :) Vor ca. 20 Jahren kam das Spiel Unreal auf den Markt. In Deutschland war es noch nicht erhältlich, doch ich hatte das Glück mit der Schule eine Klassenfahrt nach London machen zu dürfen :) Die komplette Busfahrt nach Hause habe ich die Schachtel beäugt und die Bedienungsanleitung gelesen. Zuhause angekommen stellte ich aber fest, dass mit meiner derzeitigen Grafikkarte nicht viel mit dem Spiel anzufangen war. Also kaufte ich zusammen mit meinem Bruder eine 3dfx Voodoo Grafikkarte mit 8MB Speicher. Das Teil war ein Monster. Die Begeisterung für FPS-Games war bei uns geboren. Schnell fanden wir heraus wie man eigene Maps baut und hatten viel Spaß damit. Ein Jahr später brachte mein kleiner Bruder das Spiel HalfLife von einem Freund mit nach Hause. Eine neue Liebe begann. Der Singleplayer-Modus war super, doch die ganzen Mods waren noch viel besser. Team Fortress Classic, Frontline Force, Science and Industry, Sven Co-Op (was für ein Spaß!), natürlich Natural Selection und Counter Strike, und und und ... und auch die Singleplayer-Episoden wie They Hunger oder das geniale Poke646 waren der Wahnsinn.

Ich wollte wissen, wie das geht. Wie man Maps baut, wie man Texturen erstellt, wie man Missionen scripted, wie man sich eine Armbrust mit aufgesetzter Bullet-Cam programmiert, wie man neue Gegner erstellt, wie man 3D-Modelle konstruiert, ... Ich habe Jahre meiner Kindheit/Jugend mit der HalfLife-Engine verbracht. Ich lebte quasi im TheWall-Forum. Ich lernte dort Freunde kennen und wir hatten alle einen großen Traum: Ein eigenes Spiel machen. Wir gingen regelmäßig auf die Dusmania und lernten andere begeisterte Spielemacher kennen. Ich wurde Teil der Developia Community und gründete sogar meine eigene Tutorial-Seite. Dies brachte mich erst richtig zum Programmieren und wurde dann schlussendlich zu meinem Beruf. Natürlich spielte ich auch andere Spiele und Unreal Tournament war lange Zeit die Nummer 1, doch hat mich die Quake-Engine von Anfang an begeistert.

Ich möchte euch auf eine kleine (mehrteilige) Reise in die Welt des Moddings nehmen. Wir werden uns die Quake 1 Engine einmal von innen ansehen und im Anschluss selbst eine kleine Mod erstellen. Quake ist dieses Jahr 20 Jahre alt geworden, was aber kein Grund ist, sich nicht mehr damit zu beschäftigen. Viele der Techniken sind in sehr ähnlicher Form auch in den heutigen Spielen vertreten. Einige Tools werden heute noch verwendet. Also nehmt euch etwas Zeit und macht mit. (Ich verwende ausschließlich Linux-Tools, vermutlich gibt es aber für jedes hier vorgestellte Tool ein Windows-Äquivalent)

Fangen wir ganz am Anfang an: 1996 programmierte John Carmack zusammen mit seinen Co-Foundern von id Software Quake. Die Engine war so gut durchdacht, dass schnell viele weitere Spiele damit entwickelt wurden -- nicht nur von id Software. Allen voran natürlich Half Life von Valve, auf deren Engine natürlich wiederum eine Unmenge von weiteren Spielen entstand. Einige Jahre später wurde die Quake 1 Engine unter die Open Source Lizenz gestellt und bald darauf entstanden daraus wieder viele Ableger der Engine.

Das Spiel besorgen

Die Original Quake 1 Engine ist auf einem heutigen PC kaum mehr lauffähig. Doch viele engagierte Programmierer haben sie auf neue Technologien und Betriebssysteme portiert oder gleich komplett neu geschrieben. Ich verwende die Darkplace Modifikation, da Sie einige Features fürs Modding bietet und weiterhin kompatibel zum original Quake 1 ist. Das Paket ist schnell installiert, dennoch ist die Engine selbst noch etwas langweilig. Die Asset-Files sind leider nicht Open Source und müssen anderweitig besorgt werden. In Deutschland ist es zudem etwas schwerer an die Assets zu kommen, da Quake 1 zwar seit 2011 nicht mehr indiziert ist, aber eine USK-Prüfung noch immer aussteht. Vermutlich findet sich aber ein Original auf jedem Flohmarkt dieser Welt und ist für ein paar EUR zu haben. Die Assets sind nicht zwingend notwendig, doch extrem praktisch wenn es später ans Modding geht. Hier können wir dann vorhandene Sounds/Texturen wiederverwenden.

quake 1

Die Engine

1996 waren die meisten PCs nicht in der Lage, aufwändige 3D-Szenen in Echtzeit zu berechnen. Es mussten also ein paar Tricks angewendet werden, um ein solches Spiel überhaupt möglich zu machen. Die Berechnung der Vertexes und deren Kollision mit anderen Entities musste auf ein Minimum reduziert werden, damit das Spiel bei den Spielern ruckelfrei lief -- auch mit einem nicht so gut ausgestatteten PC.

Der erste Trick ist die Reduktion der Brushes (Einzelne Quader in einer Map) auf sichtbare Faces (Flächen). Es werden also alle Seiten des Quaders entfernt, die sowieso nicht sichtbar wären. Diese Optimierung bringt aber den Nachteil, dass die Map dicht sein muss, sonst sähe man unter Umständen die Rückseite, die gar nicht da ist. Diesen Effekt sieht man manchmal wenn man im Spiel an einer Wand steht und den Kamerawinkel entsprechend wählt. Plötzlich hat es den Anschein man könnte durch die Wand schauen.

quake optimizing

Zuerst wird ermittelt, was außerhalb und was innerhalb der Map liegt. (Der Himmel ist übrigens nur eine spezielle animierte Textur.) Mit dieser Information lassen sich alle Faces berechnen, die nicht sichtbar sind. Diese werden dann gelöscht. Übrig bleiben die Faces, die innen liegen. Die einzelnen Faces werden dann in einem speziellen Binärbaum gespeichert, dazu aber später mehr. Ist die Map nicht 100% nach außen abgeschlossen (ein leak), kann diese Optimierung nicht erfolgen und der Compiler bricht ab.

Die zweite wichtige Optimierung ist die Aufteilung der Map in sichtbare Bereiche. So muss nur ein Bruchteil der Map zur gleichen Zeit verarbeitet und gerendert werden. Hier redet man von vis. Dieser Schritt ist optional, beschleunigt aber das Rendering um ein vielfaches. Auch macht es sich später extrem bei der Kollisionserkennung bemerkbar, da nicht mehr alles geprüft werden muss.

Die dritte Optimierung ist die Vorberechnung von Licht. Alle (statischen) Lichtquellen in der Map werden schon zur Compilezeit berechnet. Das spart unglaublich viel Rechenzeit zur Laufzeit. Führt man diese Optimierung nicht durch, ist die Map überall gleich ausgeleuchtet. Der Optimierungsschritt wird oft light oder rad genannt.

Durch diese Optimierungen ist es möglich, die Map in Echtzeit zu Rendern und nebenbei noch KI und Netzwerkkommunikation zu machen. Dies war für die damalige Zeit unglaublich und brachte zusammen mit Doom das FPS-Genere zutage. Einen kleinen Blick in den Sourcecode der Quake 1 Engine gibt Fabian Sanglard in seinem Artikel. Auch sehr spannend ist die Artikelserie von Michael Abrash zum Entstehungprozess der Engine.

Das Mapformat

Eine wirklich sehr spannende Sache ist das Format, in der die Map vorberechnet/gespeichert wird. Es nennt sich BSP29 und ist eine erweiterte Version eines BSP-Trees (Binary Space Partitioning, oder auch binäre Raumpartitionierung). Vermutlich hat jeder der irgend was mit Informatik studiert hat schon einmal davon gehört. Es ist ein Binärbaum, der einzelne Abschnitte (Hyperplanes) eines Raumes trennt und zudem festlegt was davor und dahinter liegt.

bsp tree (Copyright © 1995-97, Bretton Wade. source)

Jeder Knoten enthält ein Teilbereich der Map, dessen Kinder die Teilbereiche davor und dahinter entsprechen. Diese Teilbereiche (subspaces) können wieder beliebig oft rekursiv geteilt werden. Als einfaches Beispiel wird ein Raum A in die Teilbereiche B und C an der Linie X geteilt. Der Bereich B wird dann weiter in D und E an der Linie Y geteilt. Der Vorgang wird abgebrochen, wenn der erforderliche Teilungsgrad erreicht ist. Als Ergebnis erhält man dann die Hyperplanes C, D und E, schön geordnet in einem Binärbaum. Auf Wikipedia ist der Vorgang gut erklärt.

Mit diesen Informationen kann die Engine dann genau das rendern, das sichtbar ist, und muss keinen Pixel doppelt berechnen. Das folgende Youtube Video demonstriert das nochmal gut:

Den BSP-Tree kann man sich auch im Spiel live ansehen. Dazu auf der Console sv_cheats 1, gefolgt von r_showsurfaces 1 eingeben (zumindest bei der darkplaces Engine). Jede farbige Fläche ist eine Hyperplane, die sich im BSP-Baum befindet.

BSP Tree

Mit r_drawportals 1 lassen sich die Blätter des BSP-Baums ansehen -- auch Portale genannt.

BSP Tree

Netzwerk

Das Netzwerkprotokoll ist im Grunde recht simpel, hat aber einige sehr intelligente Ansätze, die mit Quake das FPS Genere erst möglich gemacht hat. Details zur Implementierung ist ebenfalls bei Fabien Sanglard zu finden.

Entscheidend bei FPS Spielen ist die Latenz. Sprich, wie lange braucht mein Tastendruck bis er bei den Mitspielern ankommt? Der Server (ein dediziertes Stück Software) übernimmt die Logik des Spiels, während die Clients im Grunde nur die Anzeige übernehmen und Eingaben vom Spieler weiterleiten. (Es ist etwas komplizierter, dazu aber gleich mehr.) Der Tastendruck muss also vom Client entgegengenommen und an den Server gesendet werden. Dieser validiert die Eingabe und sendet dann die darauf folgende Reaktion an alle Spieler (auch an den, der sie gesendet hat).

Um die Latenz zu berechnen, werden die letzten X Befehle mit Zeitstempel und deren Antwort (ebenfalls mit Zeitstempel) in einem Buffer gespeichert. Vergleicht man die Zeitstempel und bildet den Mittelwert aus allen, ergibt sich so die Latenz. Unter Gamern ist oft die Rede vom Ping, was eigentlich der Latenz entspricht.

Doch auch mit dem schnellsten Netzwerk wäre der Spielspaß sehr begrenzt, da bei jedem Tastendruck ein kleines Delay entstehen würde. Um dieses Delay zu eliminieren wurde eine Technik mit dem Namen Client Side Prediction entwickelt. Dabei führt der Client die Aktion sofort aus und sendet dann den Befehl zum Server. Braucht der Server zu lange für eine Antwort, berechnet der Client mit Hilfe der letzten Antworten vom Server eine mögliche nächste Position anhand der vergangenen Werte durch Extrapolation. Das gleiche Prinzip gilt natürlich auch für alle anderen Spieler. Diese muss der Client ebenfalls durch Extrapolation berechnen.

Kommt ein neues Update vom Server, muss der Game-State vom Server mit dem des vom Client vorgerechneten Game-State vereint werden. Dies wird durch Interpolation der selbstberechneten Werte mit dem neuen Game-State des Servers gemacht. Kam lange kein Update vom Server mehr, kommt es vor, dass der Client unter (sehr) falschen Annahmen das Spiel weiterlaufen ließ und so der Game-State drastischer korrigiert werden muss. Man bemerkt das im Spiel dann, wenn Mitspieler sprunghaft die Position wechseln. Das berühmte Lag.

Besonders interessant bei einem FPS Spiel sind Latenz-kritische Events wie bspw. die Schüsse auf die Gegner/Mitspieler. Der Spieler hat immer den Zustand von sich selbst in der Gegenwart, aber den Zustand der Welt und der anderen Spieler aus der Vergangenheit. Schießt der Spieler auf einen Gegner, ist dieser vielleicht schon lange hinter einer Mauer. Um dieses Problem zu lösen schickt der Client in regelmäßigen Abständen seinen kompletten Game-State an den Server. Der Server kennt also den Game-State aller Clients zu jedem Zeitpunkt und kann so die Sicht der Clients rekonstruieren. Hat also der Spieler einen Gegner zwar getroffen, aber auf Basis falscher Daten (da er ja mit den Daten aus der Vergangenheit arbeitet und sich die aktuelle Position usw. selbst berechnet), kann der Server dies dennoch als Treffer werten. Denn der Client hat ja den Gegner getroffen, auch wenn dies nicht der Wahrheit entspricht. Diesen Effekt bemerkt man manchmal, wenn man von einem Gegner noch getroffen wird, obwohl man bereits außerhalb des Schussfeldes steht oder sich bereits hinter eine Wand bewegt hat.

Soviel zur Theorie. Im nächsten Teil werden wir anfangen eine eigene Map zu bauen. Dabei werden wir uns zuerst die Quake-Engine ansehen wie sie Modifikationen am Spiel erlaubt und anschließend den Map-Editor anwerfen.