Game Programming Primer

 

Allgemeines

Aller Anfang ist schwer, vor allem die Entwicklung eines eigenen Computerspiels, da hier viele unterschiedliche Teilbereiche ausgearbeitet werden müssen. Um euch den Einstieg zu erleichtern, haben wir diese Seiten ins Leben gerufen, die auf die einzelnen Aspekte eines Spiels genauer eingehen.

Grundsätzliches

• Mathematik: Da ihr im 3D-Bereich sowohl beim Rendering als auch bei anderen Dingen wie Collision Detection, Physik, etc. immer wieder Vektoren/Matrizen/etc. benötigt, ist ein Hintergrundwissen in bestimmten Gebieten der Mathematik sicher notwendig. Auch wenn manche Leute immer wieder etwas anderes behaupten: ohne Mathematik geht im 3D-Bereich gar nichts!
• C++: Wir können jedem nur nahe legen, sich mit den Konzepten von C++ auseinanderzusetzen (seht euch dazu auch noch mal die Folien des 1. Repetitorium an). Es gibt sehr viele Dinge, die einem das Leben später einfacher machen können, z.B. das Erstellen einer Template-Vektor-Klasse - wer sich mit Templates, Operator-Overloading und OOP im Allgemeinen auskennt, ist hier klar im Vorteil, da man durch Ausnutzen dieser Klassen später mit Vektoren und Matrizen rechnen kann, als wären es gewöhnliche Zahlen, sprich Built-In-Types. Das Implementieren einer solchen Vektor-Klasse lohnt sich auf alle Fälle! Ihr könnt, wie schon erwähnt auch Imath oder GLM für eure Matrix/Vektor-Operationen verwenden.
• OOP: Man sollte grundsätzlich versuchen, sich ein objekt-orientiertes Design zu überlegen, wie die einzelnen Komponenten später zusammenspielen sollen. Das ist unserer Meinung nach extrem wichtig und kostet einen weniger Nerven als ein unüberlegter Ansatz. Passt trotzdem auf dass ihr euch nicht verrennt! Gutes Design kann Nerven schonen, aber auch viel Zeit kosten. Haltet euer Software-Design so einfach dass es zeitlich im Rahmen der Übung Sinn macht. Es macht keinen Sinn ein schönes Design zu haben aber kein Spiel, aus Erfahrung häuft sich die Anzahl der "Dirty Hacks" gegen Ende der Abgabe sowieso!

Für alle diejenigen, die sich gerade erst ihren Weg in die Welt von C++ und OpenGL schlagen, empfehlen wir die Beginners Section, in der darauf eingegangen wird, wie man sich den Aufbau eines Computerspiels grundsätzlich vorstellen kann. Außerdem bietet dieser Abschnitt ein paar Ideen/Tips, wie ihr eure Implementierung grob strukturieren könnt.

Solltet ihr im Bereich 3D-Programmierung/C++/OpenGL schon etwas an Erfahrung haben und euer Spiel dementsprechend um andere Bereiche erweitern wollen, so empfehlen wir die Advanced Section, in der auch Themen wie Sound, Collision Detection, AI und Physik behandelt werden. Beachtet dabei bitte, dass diese Komponenten zwar Teil eines Computerspiels sind, es die Übung an sich aber nicht erfordert, diese Dinge im Übermaß zu implementieren.

Studenten mit wenig C++/OpenGL-Erfahrung brauchen sich also nicht zu fürchten, die CG23LU nicht positiv absolvieren zu können!

Beginner Section

Um die einzelnen Teilbereiche eines Spiels besser erklären zu können, stellen wir uns vor, ein 3D-PacMan zu programmieren. Grundsätzlich geht es bei einem 3D-Spiel darum, eine virtuelle Welt darzustellen, die vom Benutzer interaktiv beeinflussbar ist. In unserem Beispiel wäre die virtuelle Welt unser Labyrinth, durch das sich PacMan bewegen kann - dieser kann dabei vom Benutzer z.B. über die Tastatur gesteuert werden. Anhand dieser Tatsache lassen sich die meisten Objekte, die in einem Spiel vorkommen, schon in bestimmte Gruppen einteilen, z.B. in statische und dynamische Objekte. Ein statisches Objekt wäre das Labyrinth, dynamische Objekte wären PacMan und seine Verfolger, die Geister. Durch Einteilung der im Spiel vorkommenden Objekte in einzelne Untergruppen fällt es einem später leichter, diese am Bildschirm darzustellen.

Um die Objekte später darzustellen, d.h. zu rendern, empfiehlt es sich zu Beginn, einfach alle Objekte einer bestimmten Gruppe in einer Liste (z.B. einem std::vector) zu speichern. Unsere Liste der statischen Objekte hätte somit ein Element (das Labyrinth), die Liste der dynamischen Objekte hätte fünf Elemente (PacMan und vier Geister).

Wollen wir nun unsere virtuelle Welt darstellen, so iterieren wir durch die Liste/n aller Objekte, und zeichnen diese mit den entsprechenden OpenGL-Kommandos.

Wie stelle ich meine Objekte dar?

Um Objekte darstellen zu können, benötigen wir zumindest Informationen über die Eckpunkte, die Dreiecke/Polygone, die Farbe und (fast immer) auch Normalvektoren, um eine korrekte Beleuchtung zu bewerkstelligen. Dabei gibt es mehrere Möglichkeiten, sich diese Informationen zu beschaffen: im einfachsten Fall könnt ihr euch diese selber erstellen, z.B. wenn unser PacMan nur als eine Kugel dargestellt werden soll. Meistens wird man die geometrischen Modelle der darzustellenden Objekte jedoch aus Dateien laden, die in einem bestimmten Format gespeichert wurden, z.B. .md2 (Quake2), .md3 (Quake3), ms3d (Milkshape), etc. Mehr zum Thema Modelling erfahrt ihr hier.

Angenommen wir hätten bereits ein geometrisches Modell unseres PacMan geladen, so könnten wir über OpenGL-Kommandos diesen auf den Bildschirm bringen, indem wir z.B. jedes Dreieck an seiner entsprechenden Position zeichnen. Links und Informationen zum Thema OpenGL findet ihr hier im Bereich Unterlagen.

In (sehr vereinfachtem) Pseudocode könnte unser bisheriges Spiel vielleicht so aussehen:

main
{
    ladeStatischeModelle();
    ladeDynamischeModelle();

    erzeugeFenster();

    while (spiel läuft)
    {
        zeichneAlleStatischenObjekte();
        zeichneAlleDynamischenObjekte();
    }
    schliesseFenster();
}


Die while-Schleife wird dabei allgemein als Game-Loop bezeichnet.

Hilfe, meine Welt ist statisch!

Was uns an dieser Stelle klarerweise noch fehlt ist die Interaktivität. Darum wollen wir uns nun kümmern. Die einfachste Methode ist es, im Game Loop bestimmte Tastatur-/Mouse-Infos abzufragen, und entsprechend zu reagieren. Wir könnten z.B. die Position unseres PacMan nach links verschieben, sobald der Spieler die linke Cursor-Taste drückt. So kann unser PacMan vom Spieler durch das Labyrinth manövriert werden.

Pseudocode dazu:

...;
// game loop
while (...)
{
...;
    if (CursorLinksGedrückt)
       SetzePacmanPosition(AltePositionX - 1);
    if (CursorRechtsGedrückt)
       SetzePacmanPosition(AltePositionX + 1);
    if (CursorUntenGedrückt)
       SetzePacmanPosition(AltePositionY - 1);
    if (CursorObenGedrückt)
       SetzePacmanPosition(AltePositionY + 1);
...;
}
...;


Mehr zum Thema Steuerung findet ihr auf den Tips&Tricks-Seiten.

PacMan kann durch Wände gehen?!

In jedem Spiel werden die meisten Objekte in irgendeiner Art und Weise eingeschränkt sein - unser PacMan sollte z.B. nicht durch Wände hindurchgehen können. Wir müssen uns also überlegen, wie wir dies verhindern können. In unserem Fall wird es wohl das einfachste sein, das Labyrinth so anzulegen, dass es von oben wie ein rechteckiges Spielfeld mit einzelnen Feldern aussieht. Dadurch können wir sehr einfach feststellen, ob sich PacMan an einer gültigen Position befindet oder nicht.

Im Allgemeinen ist es sehr viel schwieriger, solche "Kollisionen" zu erkennen - dieses Problem wird als "Collision Detection" bezeichnet und soll verhindern, dass sich Objekte in einem Spiel an "ungültigen" Positionen befinden.

Wir könnten in unserer Methode SetzePacmanPosition() also einen weiteren Methodenaufruf einbauen, der die zukünftige Position von PacMan überprüft und feststellt, ob diese gültig ist oder nicht. Wenn nicht, so bleibt die bisherige Position unverändert.

Die Geister bewegen sich nicht!

Um auch den Geistern Leben einzuhauchen, müssen diese irgendwie vom Computer gesteuert werden. Wir müssen also eine Art künstliche Intelligenz (AI - Artificial Intelligence) implementieren, die es dem Computer ermöglicht, für den Spieler eine Herausforderung zu sein. Je nach Spielgenre kommen hierbei komplizierte bzw. weniger-komplizierte Algorithmen zum Einsatz. Im Rahmen der CG23LU müsst/solltet ihr euch nicht allzu lange den Kopf darüber zerbrechen, da dies sowieso nicht Hauptaugenmerk der Übung ist. Es reicht also, wenn eure Geister z.B. irgendwie durchs Labyrinth irren und auf PacMan zugehen, sobald sie ihn "gesehen" haben.

PacMan ist spielbar - wie designe meine Klassen?

Für Anfänger ist es sicher sinnvoll, sich nicht in komplizierten Konstrukten wie z.B. einem Szenengraphen zu verirren, sondern stattdessen alle Spielelemente sinnvoll in Klassen aufzuteilen und diese der Reihe nach zu implementieren. Sehen wir einmal von unserem PacMan-Beispiel ab, so könnte man sich folgendes überlegen:

Welche Ressourcen werden benötigt?

• Grafik (Bitmaps, Texturen, etc.)
• Sound (Soundeffekte, Musik)
• Spieldaten (Levels, Missionen, etc.)

Was kommt in unserem Spiel vor?

• statische Objekte (Levelgeometrie, Terrain, etc.)
interaktive Objekte, so genannte Entities

Welche Interaktivität soll das Spiel dem Benutzer ermöglichen?

Anhand dieser und anderer Fragen lässt sich vielleicht schon eine grobe Klassenstruktur festlegen.

Advanced Section

Die hier beschriebenen Dinge sind vor allem für die 3. Abgabe relevant, wenn euer Spiel vielleicht schon spielbar ist und ihr am einen oder anderen Spezialeffekt basteln wollt. Außerdem möchten wir darauf hinweisen, dass diese Themen auch in den Repetitorien behandelt werden!

Advanced Section - Graphik

Scene-Graph

Zu jeder Rendering-Pipeline gehört ein Scene-Graph, der die einzelnen zu zeichnenden Objekte in einem Graphen vereint. Der Vorteil an einem solchen Graphen ist, dass man Hierarchien erzeugen und auch entsprechend ausnutzen kann, z.B. beim Culling oder der Collision Detection. Nachfolgend wollen wir eine Möglichkeit darstellen, wie man einen Scene-Graph konzeptionieren könnte.

Im Wesentlichen besteht ein solcher Graph aus mehreren Nodes, die miteinander verbunden sind. Ist ein Node ein Child eines anderen Node, wirken sich z.B. sämtliche Transformationen des Parent-Nodes auf die Position/Orientierung des/der Child-Nodes aus. Nodes können dabei gerenderte Objekte (z.B. Geometrie) aber auch nicht-renderbare Objekte (z.B. Lichtquellen) sein. Das hat den Vorteil, dass man Objekte an anderen Objekten "befestigen" kann - z.B. ein Licht an einem Auto. Vereinfacht gesagt: Ist die Lichtquelle ein Child des Autos, so bewegt sie sich automatisch mit dem Auto mit, sobald sich dessen Position ändert.

Ein weiteres Konzept bei Scene-Graphs sind die so genannten Animators bzw. Controllers, mit denen sich einzelne Nodes in diesem Graphen "verändern" lassen. Ein Controller kann im Prinzip das Aussehen, die Farbe, die Beleuchtung, etc. eines Nodes verändern. In den einzelnen Nodes kann man im Prinzip soviel Information speichern wie man will: Aussehen (Material, Shader, etc.), Animation (keine Animation, Modell, Partikelsystem), Verhalten (Türen, Lift) und vieles mehr.

Einfaches Beispiel:

Ein animiertes Modell soll sich unabhängig von allen anderen Objekten in einer virtuellen Welt bewegen. Damit das Modell unabhängig ist, wird es am Root-Node des Scene-Graphs befestigt, der keinerlei Transformation besitzt. Zusätzlich wird ein "AnimationController" an diesem Node "befestigt", der sich um die Animation des Modells kümmert. Dieser AnimationController wird beim Traversieren des Baumes aufgerufen, sodass der Controller entsprechend auf der Scene-Node arbeiten kann.

Meistens ist es sehr wichtig, ein durchdachtes Konzept für einen Scene-Graph zu haben. Um euch den Einstieg zu erleichtern, können wir euch das exzellente Buchkapitel aus David H. Eberly's "3D Game Engine Architecture" nahe legen.

Tipp: Erstellt für die einzelnen Nodes eines Scene-Graphs ein abstraktes Basis-Interface, von dem alle weiteren Nodes abgeleitet sind. Ein eigener Manager (wiederum in einer eigenen Klasse) kümmert sich um das Einfügen bestimmter Nodes in den Scene-Graph. Beispielcode dazu:

class ISceneGraphNode
{
   public:
   virtual void Render() = 0; // diese methode kümmert sich um
                          // das rendern des jeweiligen nodes

   // abstract base class
   virtual ~ISceneGraphNode() {};

   protected:
   // abstract base class
   ISceneGraphNode() {};
};

class CModellNode : public ISceneGraphNode
{
   public:
   CModellNode() {};
   ~CModellNode() {};

   virtual void Render() { RenderMe(); }
};


In eurem Manager gibt es z.B. eine Methode addModellNode(ISceneGraphNode* parent), die einen Node an einen anderen Node dranhängt. Jetzt braucht ihr den Baum nur noch ausgehend vom Root-Node rekursiv traversieren und die einzelnen Nodes rendern. Die einzelnen Transformationen der Nodes werden dabei vom Root-Node zu den jeweiligen Child-Nodes propagiert.

Rendering

Um das Rendering an sich zu bewerkstelligen, werden einfach je nach Node OpenGL-Befehle ausgeführt, die den entsprechenden Node rendern. Links und genauere Informationen zum Thema OpenGL findet ihr z.B. hier.

Natürlich können je nach Node unterschiedliche Shader/Texturen/Materialien benutzt werden - das ist der Sinn hinter einem Scene-Graph!

Tipp: Um State-Changes und Shader-/Texture-Changes zu vermeiden, kann man das ganze auch anders angehen, indem man den Scene-Graph traversiert, alle Objekte sammelt, sie je nach Shader/Textur sortiert, und die Objekte anschließend in dieser Reihenfolge rendert. Für eine korrekte Darstellung transparenter Materialien kommt man um eine eigene Sortierung ohnehin nicht herum.

Culling

Da das Rendern mehrerer Nodes mit vielen verschiedenen Shadern/Texturen schnell zu aufwendig werden kann, ist es äußerst wichtig, effizientes Culling zu implementieren. Die einfachste Form des Cullens ist das so genannte View-Frustum-Culling, bei dem einfach alle Objekte nicht gerendert werden, die sowieso nicht im sichtbaren Bereich der Kamera liegen.

Als weitere Culling-Methoden lassen sich z.B. Portale, BSPs oder PVS (Potentially Visible Sets) einsetzen. Im Internet lässt sich eine Fülle an Informationen dazu finden, da vor allem BSPs und PVS in der Quake-Reihe von id-Software zum Einsatz kommen.

Tipp: Implementiert zuerst einfaches View-Frustum-Culling und erweitert euer Culling-System erst nach und nach.

Input

Um Tastatur-/Mouse-Events abzufangen, gibt es grundsätzlich mehrere Möglichkeiten:

1. GLFW verwenden
2. SDL verwenden
3. Windows API Funktionen verwenden

Für Einsteiger können wir Methoden a) und b) empfehlen - wenn man auf Plattform-Unabhängigkeit Wert legt, scheidet c) schon aus. Über die jeweils ermittelten Inputs lassen sich z.B. die Positionen/Rotationen einzelner Nodes im Scene-Graph ändern. Hat man erst einmal die Implementierung eines Scene-Graphs fertiggestellt, sind den Möglichkeiten hier eigentlich keine Grenzen gesetzt. Mehr zum Thema Input (Tastatur und Maus) erfahrt ihr hier.

Advanced Section - Sound

Um Sounds/Musik abzuspielen, ist FMOD sicher die bequemste Library. Teilweise benötigt es nur 2-3 Zeilen an Code, um MP3s abzuspielen oder Sound-Effekte einzubauen. Wir können diese Library nur jedem nahe legen, der Sound in sein Spiel integrieren will. Eine Auswahl weiterer Libraries findet ihr auf dieser Seite.

OpenAL ist eine plattformübergreifende Open Source Audio Library für Sound, die ebenfalls zu empfehlen ist.

Advanced Section - Artificial Intelligence

Hierzu gibt es einige Ansätze, die auch je nach Spielgenre variieren. Ihr solltet dabei abwiegen, welche Art von AI ihr für euer Spiel benötigt und euch nicht allzu sehr in Details verstricken. Gebt euch lieber mit einfacheren Lösungen zufrieden, da hinter einer "intelligenten" AI wirklich sehr viel Arbeit steckt.

In fast allen Fällen (besonders im Rahmen dieser Übung) kommt man mit einer State-Machine aus, die im Prinzip folgendermaßen funktioniert:
Jeder Gegner/Monster/etc. verfügt über mehrere Zustände (States), in denen er sich befinden kann, z.B. RunAway, ShootAtPlayer, Idle, LookAround. Je mehr verschiedene States man einbauen will, umso komplizierter wird das Ganze. Jeder dieser States wird einfach durch bestimmte Events getriggert, die den Gegner in einen bestimmten State versetzen. Ist die Lebensenergie eines Gegners z.B. auf 5% gesunken, so wird er wahrscheinlich vor dem Spieler davonrennen, anstatt auf ihn zu schiessen - außer er hat irgendwo eine BFG9000 versteckt :)

Zum Navigieren der Gegner bieten sich (wieder je nach Genre) mehrere Möglichkeiten an: In isometrischen Spielen kommt man meist mit einer einfachen Pfad-Suche aus, in FPS muss man sich schon mehr Gedanken machen. Hier kann man die Bots z.B. anhand vorberechneter Pfad-Knoten navigieren lassen oder mittels einfachem Ray-Casting ermitteln, in welche Richtung sie sich nicht bewegen können und dadurch auf ihre Navigation schliessen, was allerdings ziemlich knifflig werden kann.

Tipp: Verwendet zu Beginn eine einfache State-Machine, die ihr später mehr und mehr erweitert. Man erwartet von euch sicher nicht, dass eure AI in der Lage ist, Verstärkung zu holen, etc.

Advanced Section - Collision Detection

Auch in diesem Bereich gilt es Abstriche zu machen, je nachdem, welches Spiel ihr entwickeln wollt. Normalerweise gibt es genügend Tricks, um Probleme bei der Collision Detection einfach gar nicht auftreten zu lassen, z.B. könnte man in einem Weltraumshooter zwischen den Raumschiffen nur Bounding-Sphere-Checks durchführen, und bei einer Kollision einfach ihre Schutzschilde (die wie eine durchsichtige Kugel aussehen) aktivieren. Dadurch spart man sich sehr viel Aufwand und Zeit, da Collision Detection zwischen konvexen Polyhedra sehr schwierig ist.

In fast allen Fällen lohnt es sich, auf hierarchische Bounding-Volumes zurückzugreifen. Für einen FPS wären das z.B. AABB-Trees, OBB-Trees, BSPs, Octtrees, etc. Solange man nicht physikalische Simulationen (dazu später mehr) implementieren will, reicht es meistens aus, eine Kollision nur zu erkennen und nicht den exakten Kollisionspunkt zu bestimmen, was deutlich schwieriger ist!

Falls ihr Collision Detection nicht selber implementieren wollt und stattdessen eine Library verwenden wollt, so können wir euch OPCODE empfehlen. Dabei solltet ihr jedoch beachten, ob ihr für euer Spiel wirklich exakte Collision Detection benötigt oder das Ganze vielleicht irgendwie "faken" könnt. Eine Auflistung weiterer Libraries findet ihr im Bereich "Zusatztools" dieser Seite.

Advanced Section - Physik

Ein relativ neues Thema, das aber immer mehr in Spielen zum Einsatz kommt und sehr viel zum Feeling beitragen kann (siehe Half-Life 2). Um physikalische Objekte zu simulieren, benötigt ihr zusätzlich zu fundierten Mathematik-Kenntnissen auch noch ein wenig physikalisches Hintergrundwissen. Wichtig ist hierbei, dass man sich ein klares Ziel setzt, was man in sein Spiel einbauen will - eine Simulation, die selbst Havok alt aussehen lässt, ist kein klares Ziel :)

Um euch einen grundlegenden Überblick zu verschaffen, könnt ihr euch die exzellenten Artikel von David Baraff durchlesen, besonders die Kapitel über "Rigid Body Dynamics".

Tipp: Falls ihr euch nicht allzu sehr mit Kollision und Physik auseinandersetzen wollt, kann die Verwendung einer Physik-Library sinnvoll sein. Gute Erfahrungen haben wir gemacht mit der NVidia PhysX Engine, die von der NVidia-Developer Seite bezogen werden kann. Wer eine lizenzrechtlich weniger eingeschränkte Physik-Engine braucht, könnte mit Bullet glücklich werden.