Die Engine

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.

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.

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.

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

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

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.