Entwicklung eines interaktiven 3D

Entwicklung eines interaktiven
3D-Labyrinths
Studienarbeit
vorgelegt von
Verena Kolba
Institut Computervisualistik
Arbeitsgruppe Computergraphik
Betreuer und Prüfer: Dr.-Ing. Stefan Müller
- November 2004 -
Inhaltsverzeichnis
1 Einleitung
3
2 Das Konzept
2.1 Der Spielablauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Verwendete Software . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
4
3 Die
3.1
3.2
3.3
Umsetzung
Die Module . . . . . . . . . . . . . . . . . . . . .
Die zufällige Generierung des Labyrinths . . . . .
Realisierung des Labyrinths mit Coin3d . . . . .
3.3.1 Die Szene . . . . . . . . . . . . . . . . . .
3.3.2 Die Kamerasteuerung . . . . . . . . . . .
3.3.3 Die Kollisionserkennung und das Picking .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
8
12
12
17
19
4 Ergebnisse
23
5 Fazit und Ausblick
28
2
1 Einleitung
Motivation
Seitdem der Personal Computer Einzug in das Privatleben der Menschen gefunden
hat, erfreuen sich auch Computerspiele immer größerer Beliebtheit. Nachdem die
grafische Umsetzung zu Anfang eher weniger ansprechend war, macht es der rasante
Fortschritt im Bereich der 3D-Grafik Hardware mittlerweile möglich, zunehmend
realistischere Szenen und Spielabläufe darzustellen. Im Laufe meines Studiums habe
ich sehr viel über die Theorie der 3D-Grafik-Programmierung gelernt, hatte jedoch
wenig Gelegenheit, diese auch in der Praxis zu erproben.
Mit der Entscheidung, meine Studienarbeit im Bereich der Computergraphik zu
schreiben, bot sich mir die Gelegenheit, dieses Defizit zu kompensieren. Der besondere Reiz an der Implemetierung eines Spiels liegt für mich in der Möglichkeit,
interaktiv in das Geschehen auf dem Bildschirm einzugreifen. Außerdem wird eine
abwechslungsreiche Aufgabenstellung geboten, wie zum Beispiel die Texturierung
von Objekten oder Kollisionserkennung. Die Verwendung eines Szenegraphen stellt
eine zusätzliche Herausforderung dar.
Anspruch dieser Arbeit soll nicht sein, etwas noch nie da gewesenes zu erschaffen, sondern eher darin liegen anhand eines einfachen Spielekonzepts grundlegende
Ansätze der 3D-Programmierung umzusetzen.
Ziele
Ziel dieser Arbeit ist die Konzeption und Entwicklung eines 3D- Labyrinths, das in
verschiedenen Grössen zufällig generiert werden kann. Der Benutzer soll sich in dem
Räumen interaktiv bewegen können, wobei Kollisionen mit Wänden automatisch
vermieden werden. Ein Spielablauf soll zusätzlich berücksichtigt werden, wie zum
Beispiel durch Einsammeln von Gegenständen.
Diese Ausarbeitung beschäftigt sich im folgenden Kapitel (Kap.2) mit der Konzeption des Labyrinthspiels. Es wird erklärt, wie das fertige Spiel im Groben ablaufen
soll. Außerdem stelle ich zum besseren Verständnis die bei der Umsetzung zum Einsatz gekommenen Komponenten des Szenegraphen vor. Das 3. Kapitel beschäftigt
sich mit der Realisierung des Labyrinths. Die Definition der einzelnen Bausteine
(Module), aus denen das Labyrinth aufgebaut ist, wird erläutert sowie mein Ansatz
zur zufälligen Generierung.
Ein weiteres Unterkapitel beschreibt den Aufbau der Szene in 3D. Es wird außerdem erklärt, wie der Benutzer sich durch die Szene bewegen kann und wie die
Kamerasteuerung umgesetzt wird. Der letzte Teil dieses Kapitels befasst sich mit
der Implementierung der Kollisionserkennung.
Im Anschluß (Kap.4) wird das Resultat meiner Arbeit anhand von Screenshots
präsentiert. Ein abschliessendes Fazit fasst die gewonnenen Erfahrungen zusammen und weist auf Ausbau- und Verbesserungsmöglichkeiten hin.
3
2 Das Konzept
2.1 Der Spielablauf
Das Labyrinth soll in verschiedenen Grössen zufällig generiert werden können.
Es besteht aus verschiedenen Bauelementen (Modulen), deren Datenstruktur das
Grundgerüst für sowohl die zufällige Generierung als auch die Darstellung in 3D ist.
Der Spieler sieht die Szene aus der Sicht der Kamera. Seine Startposition befindet
sich vor dem Eingang des Labyrinths mit Blickrichtung ins Innere. Mit den PfeilTasten kann sich der Benutzer durch das Labyrinth bewegen. Da ein Labyrinth mit
durchlässigen Wänden keinen großen Sinn hat, muß eine Kollisionserkennung und
-behandlung programmiert werden.
An einigen Stellen im Labyrinth sind Münzen verteilt, von denen eine Mindestanzahl eingesammelt werden muss, bevor sich der Ausgang öffnet. Es können auch
einige Karten gefunden werden, die die aktuelle Position des Spielers im Labyrinth
anzeigen. Die Anzahl der vorkommenden Münzen und Karten ist abhängig von der
Grösse des Labyrinths. Hat man genügend Münzen gesammelt und den Ausgang
durchschritten, ist das Spiel erfolgreich beendet.
2.2 Verwendete Software
Zur Realisierung in 3D wurde das szenegraphbasierte Open Inventor Toolkit (SGI)
bzw. die Open-Source-Version Coin3D verwendet. Diese plattformunabhängige Software ist in C++ programmiert und benutzt die Graphikbibliothek OpenGL als
Rendering-Maschine. Die einzelnen Objekte (Knoten) in einer Szene werden in
einer Baumstruktur an den Wurzelknoten gehängt. Die Szene wird durch Traversierung dieses Baumes erstellt.
An dieser Stelle werden nur die wichtigsten Knoten, die zur Realisierung des Spiels
benötigt werden, kurz vorgestellt. Das Präfix “So” gibt an, dass es sich bei dem
jeweiligen Knoten um ein Scene Object handelt. Das bedeutet, dass das Objekt
die Darstellung der Szene direkt beeinflusst. Um einen detaillierteren Einblick in
die Architektur und Syntax des Szenegraphen zu erhalten, verweise ich auf das
Handbuch [1] The Inventor Mentor.
SoSeparator
Bei einem SoSeparator-Knoten handelt es sich um eine Unterklasse des SoGroupKnotens. Er wird verwendet, um die Kind-Knoten in der jeweiligen Gruppe zu isolieren. Sie haben dann keine Auswirkungen auf den Rest des Szenegraphen. Nach
der Traversierung seiner Kinder stellt ein SoSeparator-Knoten den vorherigen Traversierungsstand wieder her. Diese Art von Knoten wird zum Beispiel bei den
Modulen verwendet, um die einzelnen Wandelemente zu positionieren. Das daraus
4
resultierende Modul wird ebenfalls unter einen Separator gehängt und kann dann
im Weltkoordinaten-System an die richtige Stelle gesetzt werden.
Abbildung 1: Symbole für verwendete Knoten
SoSwitch/SoBlinker
Der SoSwitch-Knoten ist ebenfalls eine Unterklasse von SoGroup. Er wählt jedoch
nur einen seiner Kind-Knoten aus, um ihn zu traversieren. Die Kind-Knoten können
alle über ihren Index angesprochen werden. Er gibt an, an welcher Position (0...n)
im SoSwitch-Knoten sich das jeweilige Kind befindet. Über die Angabe des entsprechenden Index wird festgelegt, welcher Kinds-Knoten traversiert werden soll..
Ein SoSwitch-Knoten wird im Spiel verwendet, um zwischen zwei Kamerasichten
zu wechseln.
Ein SoBlinker-Knoten besucht seine Kinds-Knoten zyklisch. Mit Hilfe dieses Knotens wird zum Beispiel ein rot-blinkendes Warnschild dargestellt.
SoEventCallback
Ein EventCallback-Knoten wird verwendet, um das Verhalten des Programms zu
definieren, wenn ein bestimmtes Ereignis auftaucht. Der Callback besteht aus einer
selbtgeschriebenen Funktion die aufgerufen wird,wenn die HandleEventActionÊden
Knoten traversiert. Um zu bestimmen, welche Art von Ereignis von Interesse ist,
wird die addEventCallback()-Methode verwendet. Hat die Callback-Funktion ein
Ereignis abgehandelt, muss explizit setHandled() aufgerufen werden. Im Labyrinthspiel wird dieser Knoten benutzt, um die Kamera-Steuerung durch TastaturEingabe zu realisieren. Der Ereignistyp ist ein KeyPressEvent.
5
SoPerspectiveCamera
Der SoPerspectiveCamera-Knoten definiert eine perspektivische Kamera. Sie soll
das menschliche Auge emulieren. Die Position der Kamera stimmt mit dem Augpunkt überein. Durch den Kamera-Knoten kann außerdem die Near- und Far
Clipping-Plane angegeben werden. Im Programm wird z.B. bei jeder Bewegung
die Position oder die Orientierung der Kamera in diesem Knoten neu gesetzt.
SoFaceSet
Ein SoFaceSet-Knoten ist ein Shape-Knoten, der Flächen aus vorgegebenen Koordinaten, Normalen und Texturen erstellt und damit ein polygonales Objekt bildet.
Er wird verwendet, wenn komplexere Formen als zum Beispiel ein Quader oder eine
Kugel benötigt werden. Die Karten, die im Labyrinth gefunden werden können, sind
mit einem Faceset realisiert, da sie aus mehreren ”abgeknickten” Flächen bestehen.
SoElapsedTime
Bei diesem Knoten handelt es sich um eine Engine. Engines werden in Coin3d
hauptsächlich dazu verwendet, Teile der Szene zu animieren. Sie verfügen über eingebaute Funktionen. Die SoElapsedTime Engine entspricht einer Stoppuhr, die als
Ausgabe die verstrichene Zeit seit ihrem Start hat.
Verknüpft man die SoElapsedTime Engine mit einem Transform-Knoten, kann somit eine kontinuierliche Bewegung des zugehörigen Objekts erreicht werden. Auf
diese Weise wird im Spiel realisiert, dass sich die aufzusammelnden Gegenstände
um sich selbst drehen.
SoAlarmSensor
Ein Sensor-Knoten reagiert auf Änderungen der Szenegraph-Datenbank oder auf
spezifische Ereignisse in der Zeit. Tritt ein bestimmtes Ereignis auf, wird eine vom
Benutzer definierte Callback-Funktion aktiv. Ein SoAlarmSensor kann mit einem
Wecker verglichen werden, der erst nach einer bestimmten Zeit startet. Mit der
setTimeFromNow(time)-Methode kann bestimmt werden, welche Zeitspanne das
sein soll. Der Sensor ruft dann seine Callback-Funktion auf.
Ein SoAlarmSensor wird im Spiel dazu benutzt, den Switch zur mapCam auf 15 Sekunden zu beschränken. Bei Aufruf der Callback-Funktion wird wieder zur DefaultKamera zurückgewechselt.
SoRayPickAction
Diese Aktion findet Objekte entlang eines Strahls von der Kamera aus durch einen
Punkt auf der Nearclippingplane. Durch die Methode setRay() kann ein Strahl
in Weltkoordinaten definiert werden. Dazu wird ein Startpunkt und eine Richtung
angegeben. Außerdem ist es möglich den Raum, in dem das Picking erfolgen soll
6
durch die Angabe einer Near- bzw. Far Distance zu beschränken. Die RayPickAction kann an einen Graphen oder Subgraphen angehängt werden, der dann traversiert
wird und den Pfad zu den gefundenen Objekten zurückgibt.
Dieser Knoten wird im Labyrinth dazu verwendet, Kollisionen mit den Wänden
oder den zu findenden Gegenständen zu erkennen.
3 Die Umsetzung
3.1 Die Module
Abbildung 2: Definition der Module
Um ein Labyrinth zu erstellen, muß zuerst festgelegt werden, wie das Grundgerüst
aussehen soll. Statt einzelne Wände zu setzen, habe ich mich für die Verwendung
von vordefinierten Modulen entschieden.
Unter einem Modul versteht man ein Gangelement, das durch die Positionierung
der Wände ein Wegstück definiert. Die einzelnen Module müssen über mindestens
einen Eingang und einen Ausgang verfügen, können aber auch mehr haben. Sackgassen entstehen also erst bei der Generierung des Labyrinths durch die Kombination verschiedener Module. Die Kennziffer eines Moduls setzt sich aus der binären
Addition seiner Öffnungen zusammen. Jedes Modul kann über die Angabe einer
4-Bit-Sequenz definiert werden. Wenn eine Öffnung existiert, ist in der Binärdarstellung das entsprechende Bit auf 1 gesetzt. Geht man von einer Draufsicht von
oben auf die einzelnen Module aus, wird:
oben offen binär durch die 1(0001),
7
rechts offen durch die 2 (0010),
unten offen durch die 4 (0100) und
links offen durch die 8 (1000) dargestellt (siehe Abb.2).
Insgesamt ergeben sich 11 verschiedene Module, die durch Mehrfachverwendung
und unterschiedliche Kombinationen das Labyrinth ergeben. Ein zusätzlicher Modulblock hat keinerlei Ein- oder Ausgänge und wird als Füllelement verwendet. Er
wird binär durch die 0 (0000) dargestellt.
Eine erste Idee, wie die Module in 3D aussehen könnten, soll folgende Abbildung
veranschaulichen. Die 3D-Graphiken wurden entsprechend der gegebenen Moduldefinitionen erstellt und beispielhaft mit Texturen versehen. Die endgültige Größe
und Texturierung wird später festgelegt.
Abbildung 3: Beispiel-Module in 3D
3.2 Die zufällige Generierung des Labyrinths
Bevor das Spiel beginnen kann, muss über die Konsole zuerst eine Zahl zwischen
10 und 30 eingegeben werden, die die Grösse des Labyrinths angibt. In der 3DSzene soll das Labyrinth im Ursprung beginnen und sich entlang der x- und zAchsen ausbreiten. Die Grösse bestimmt die Anzahl von Modulen entlang dieser
Achsen. Der Einfachheit halber gehe ich davon aus, dass in jeder Richtung gleich
viele Module gesetzt werden. Es können also nur quadratische Labyrinthe erstellt
werden.
Im Voraus werden verschiedene Untermengen von Modulen gebildet, die bestimmte
Kriterien erfüllen. Die Menge
static int nachuntenweiter[7] = {3,5,7,9,11,13,15}; besteht zum Beispiel
aus allen Modulen, die oben eine Öffnung haben, mit denen man also ein nach
unten geöffnetes Modul fortsetzen kann. Jede Untermenge wird in Form eines ndimensionalen Arrays abgelegt, wobei n die Anzahl der verschiedenen Module mit
den entsprechenden Kriterien angibt. Die Module werden über ihre Kennziffern
angegeben.
Zur tatsächlichen Generierung des Labyrinths dient die Klasse Lab (siehe Abb.4).
8
Die Methode Lab(int *size) erzeugt ein Objekt vom Typ Lab in der übergebenen Grösse (2-dimensionales Array). Die Methode void genLab(void) füllt dieses
derart mit Modulen, dass ein sinnvolles Labyrinth entsteht. Sinnvoll bedeutet in
diesem Zusammenhang, dass das Labyrinth nur über einen Eingang und einen Ausgang verfügt und ansonsten nur aus erreichbaren Sackgassen besteht.
Die Generierung eines derartigen Labyrinths erwies sich als schwieriger, als gedacht.
Anfangs wurden die Felder ohne eine nähere Überprüfung ihrer Umgebung gefüllt,
was zur Folge hatte, dass der Ausgang oft nicht zu erreichen war und es viele Wege gab, die nicht betretbar waren. Also implementierte ich einen Umgebungs-Test,
der die Nachbarn des zu füllenden Feldes auf ihre Belegung überprüft. Auf dieses
‘Umfeld-Problem” wird im Folgenden noch näher eingegangen.
Abbildung 4: Die Klasse Lab
Die Klasse enthält die wichtigsten Methoden, die zur Generierung und Realisierung
des Labyrinths benötigt werden. Die SoSeparator-Definitionen werden zur Erstellung der Szene benutzt und im nächsten Kapitel näher erklärt. An dieser Stelle
werden nur die zur Generierung benötigten Methoden vorgestellt und ihre Funktion erklärt.
void genLab(void)
Nachdem das Labyrinth-Array in der übergebenen Grösse initialisiert wurde, wird
es zuerst mit Nullen gefüllt. Das erste Feld im Array an der Position lab[0][0]
entspricht dem Eingang des Labyrinths, das letzte Feld an der Position
lab[size-1][size-1] dem Ausgang. An diesen beiden Positionen soll immer ein
9
gerades Wegmodul in x-Richtung gesetzt werden. Es wird also jeweils eine 10 eingetragen.
( vgl. Abb.2 straightPathx = 10 = 1010 = 1000 + 0010 = links offen + rechts
offen).
private int Lab::possible(int act, int x, int y,int *weg))
Von der aktuellen Position aus wird geprüft, wohin der Gang der Modulbelegung
nach weitergehen kann. Dazu wird die Kennziffer des aktuellen Moduls act dieser
Methode übergeben. Die x-y-Ebene im 2-dimensionalen Array entspricht der x-zEbene im 3D-Raum. Das Modul wird nun darauf untersucht, in welche Richtungen
es Öffnungen besitzt und ob das nächste Feld in diese Richtung überhaupt frei ist
oder es sich schon um den Rand handelt.
Der Test wird mit Hilfe des logischen Bit-Operators & ausgeführt, der die Kennziffer des aktuellen Moduls mit den 4 möglichen Öffnungsrichtungen bitweise verundet und somit prüft, ob das entsprechende Öffnungs-Bit gesetzt ist (Beispiel: if
(act&OBEN && (y != 0)). Wenn beide Fälle nicht zutreffen, wird auf die LaufVariable possiblestep das Bit der möglichen Richtung aufaddiert. Die Funktion
liefert eine Zahl, die in der Binärrepräsentation an den Positionen eine 1 hat, an
denen der Gang fortgesetzt werden kann (11 = 1011 = oben, rechts und links offen).
private void Lab::take(int possiblestep ,int *x, int *y, int *weg)
Die Position für das nächste Modul wird zufällig gewählt oder bei nur einer Möglichkeit übernommen. Ist die Richtung gewählt, muß die Entscheidung getroffen werden, welches Modul bzw. welche Kennziffer an diese Position gesetzt wird. Dies
ist abhängig von der Belegung der umliegenden Felder (siehe Abb. 5). Bei den 3
Feldern, die untersucht werden müssen (in der Abbildung mit “x” gekennzeichnet),
wird überprüft ob sie noch auf Null initialisiert sind, also leer, oder schon eine Modulkennziffer gesetzt ist und das Feld somit schon Teil eines anderen Ganges ist.
Aus den zuvor definierten Untermengen von Modulen wird dann diejenige gewählt,
die die für die Umgebung entsprechenden Kriterien erfüllt. Per Zufall wird ein Modul daraus ermittelt, dessen Kennziffer in das aktuelle Feld eingetragen wird. Im
Beispiel wird von der aktuellen Position lab[2][0] die einzig mögliche richtung 4
(0100) genommen. Da ein Feld (rechts) bereits belegt ist, die anderen beiden jedoch frei, wird aus der Untermenge static int nachUntennoRechts[2]={13,15}
das Modul 13 gesetzt.
10
Abbildung 5: Das Umfeld-Problem
Dieser Ablauf wird iterativ für jede neue Position durchgeführt. Die Methode void
genLab(void) steuert über eine switch-Anweisung das Befüllen des Arrays. Wird
ein Weg gebaut, ist für dieses Vorgehen die Variable weg auf 1 gesetzt. Sollten bei
dem Umgebungstest alle drei Felder belegt sein, ist der aktuelle Weg zu Ende. Dann
wird weg auf 2 gesetzt und mit der switch-Anweisung ((siehe Abb.6 Die SwitchAnweisung) in die entsprechende Schleife gewechselt. Das Array wird von links
nach rechts durchlaufen und alle Module werden daraufhin überprüft, ob sie noch
eine frei Öffnung haben. Dieser Test wird wieder durch die Methode private int
Lab::possible() durchgeführt. Wenn ein solches Modul gefunden wird, springt
das Programm wieder in die Methode private void Lab::take() und baut von
der übergebenen Position des Moduls einen neuen Weg (weg=1) bis der Algorithmus in die nächste Sackgasse gerät. Am Ende eines Durchlaufs ist das Ergebnis
ein gefülltes 2-dimensionales Array, welches das Labyrinth in 2D präsentiert. Die
Module sind durch ihre Kennziffern eindeutig bestimmt.
Nach einigen Testdurchläufen, musste ich leider feststellen, dass immer noch Labyrinthe generiert wurden, deren Ausgang nicht erreicht werden konnte. Um sicher zu
gehen, dass ein erreichbarer Weg vom Eingang zum Ausgang erstellt wird, müssen
die Felder um das Ausgansmodul erweitert untersucht werden. Nach der Fertigstellung des Labyrinths wird vom Ausgang aus rückwärts getestet, ob die ”kritschen
Felder” (siehe Abb.5 grau unterlegt) eine Verbindung zwischen dem Ausgang und
dem restlichen Labyrinth bilden. Dazu werden die Modulkennziffern der Felder auf
Öffnungen zum übrigen Labyrinth hin untersucht. Wird keine Öffnung gefunden,
wird ein neues Labyrinth erstellt.
11
Abbildung 6: Die Switch-Anweisung
3.3 Realisierung des Labyrinths mit Coin3d
3.3.1 Die Szene
Es bietet sich an, Diagramme des verwendeten Szenegraphen zu verwenden, um den
Aufbau der Szene zu erläutern. Die Hierarchie-Anordnung und die verschiedenen
Zugehörigkeiten können so besser nachvollzogen werden.
Der ganzen Szene ist ein Root-Knoten vom Typ SoSeparator vorangestellt (siehe
Abb.7). Zuerst wird die Beleuchtung und ein SoSwitch-Knoten mit zwei Kameras angehängt. Der Switch-Knoten ist per Default auf camera gesetzt. Zur mapCam
wird nur gewechselt, wenn der Spieler eine Karte findet. Die dritte Kamera, die
angehängt wird, kommt erst bei der Kollisionserkennung zum Einsatz.
Damit das Labyrinth nicht im freien Raum schwebt, ist es von einer Skybox umgeben, die der Szene einen realistischen Charakter geben soll. Sie besteht aus mehreren
SoFaceset-Knoten, die jeweils eine Seite der Skybox definieren. Die Umsetzung in
Form einzelner Faceset-Knoten ist umständlicher als die Verwendung eines SoCubeKnotens. Da es mir jedoch nicht gelungen ist, die Seiten eines Cubes einzeln zu
texturieren, habe ich einzelne Facesets verwendet.
12
Abbildung 7: Der Szenegraph vom Root-Knoten aus
Die Module reihen sich vom Ursprung aus entlang der positiven x- und z- Achsen
auf. Sie sind von einer zusätzlich definierten Wand umgeben, da bei der Generierung des Labyrinths die Aussenwände nicht berücksichtigt werden. Um einen
ausreichenden Bewegungs-Spielraum innerhalb des Labyrinths zu garantieren, haben die Module jeweils eine Größe von 2*2*2 cm. Die Größe des Labyrinths in 3D
beläuft sich auf size*2 cm. Die Außenwände bestehen aus je einem texturierten
Quader, der dementsprechend die Breite size*2 hat.
Abbildung 8: Der Subgraph Laby
13
Die Module (siehe Abb.8) werden aus mehreren texturierten Quadern aufgebaut.
Da die Verwendung einzelner Facesets in diesem Fall zu aufwändig ist, werden kleine Fehler in der Textur auf den Schmalseiten der Wände akzeptiert.
In einer Schleife, die über das gesamte Lab-Array läuft, werden die Kennziffern der
einzelnen Module ausgelesen. Mit jedem Aufruf der Member-Funktion newModul =
lab->getMod(xcounter, ycounter) wird ein neues Modul in den Szenegraphen
gehängt. Die richtige Position in der Szene wird berechnet, indem für jedes Feld des
Arrays in x-Richtung die x-Koordinate des Moduls in Weltkoordinaten um 2. hochgezählt wird. Dementsprechend erhöht sich die z-Koordinate eines Moduls, wenn
im Array in y- Richtung weitergegangen wird (siehe Abb. 9 Schleife, um Module
zu setzen).
Die Funktion SoSeparator *Lab::getMod(int x, int y) sucht an der übergebenen Stelle im Array nach der Kennziffer des Moduls, generiert dieses und gibt es als
SoSeparator-Knoten zurück. Der Subgraph modules fasst alle Module zusammen.
Jedes Modul verfügt über einen Transform-Knoten, der die Position in der Szene
enthält und einem weiteren Separator-Knoten, der die Geometrie des jeweiligen
Modul beschreibt.
Abbildung 9: Schleife, um Module zu setzen
Wenn das Labyrinth erstellt ist, werden im nächsten Schritt die Münzen, die es
einzusammeln gilt, und einige Karten, die als Orientierungshilfe dienen sollen,
platziert. Dazu wird zuerst berechnet, wie viele Münzen bzw. Karten im Labyrinth verteilt werden sollen. Es wurde vorab festgelegt, dass ein Labyrinth jeweils
(size/2)+1 Münzen bzw. (size/2)-1 Karten enthält.
Die Member-Funktionen SoSeparator *Lab::getCoin(void) und
SoSeparator *Lab::makeMap(void) liefern jeweils ein Coin- bzw. ein KartenObjekt, das in den entsprechenden Subgraphen gehängt wird (siehe Abb.11a). Der
Aufbau der Subgraphen entspricht im Prinzip dem der der Module.
Im Fall der Münze handelt es sich bei dem Shape-Objekt um einen flachen, aufrecht
stehenden Zylinder, der sich kontinuierlich um sich selbst dreht. Diese Animation
wird erreicht, indem eine SoElapsedTime Engine mit dem Winkel der Rotation
verknüpft wird. Durch die Verwendung der Methode connectFrom() wird die Aus-
14
Abbildung 11: Die Subgraphen Coins und Maps
gabe der SoElapsedTime Engine in ein lesbares Winkelformat konvertiert und dem
SoRotationXYZ-Knoten übergeben.
Abbildung 10: zeitgesteuerte Rotation
Die Karte (siehe Abb.11 b) benutzt einen SoFaceset-Knoten um die Form darzustellen, wird aber auf die gleiche Weise animiert wie die Münzen. Zu Anfang wurde
die Karte mit einem Nurbs-Surface realisiert, was aber bei der späteren Implementierung des Pickings zu Problemen führte. Deshalb mußte auf diese realistischere
Umsetzung zu Gunsten der Funktionalität verzichtet werden.
Wo die Münzen und Karten im Labyrinth platziert werden, wird zufällig festgelegt ( rand()). Um die Sache etwas zu erschweren, soll in den ersten 3*3 Modulen
kein Gegenstand auftauchen. Dies wird in der Implementierung so umgesetzt, dass
der Zufallszahlen-Generator nur aus einer Menge von size+2-4 Modulpositionen
wählen kann (siehe Abb. 12 Position von Müenzen zufällig bestimmen). Da die Module eine Seitenlänge von 2 cm haben, werden 4 cm, also zwei Module, abgezogen.
Bei der tatsächlichen Angabe der Translation des Gegenstandes in Weltkoordina-
15
ten, werden die 4 cm wieder aufaddiert. Somit ist garantiert, dass die Felder direkt
um den Eingang nicht besetzt werden. Allerdings kann es vorkommen, dass sich auf
einer Position zwei Gegenstände befinden. Da dieser Umstand das Spiel allenfalls
vereinfacht, wurde auf eine zusätzliche Abfrage verzichtet.
Der Zufallszahlen-Generator muß nur für die x- und z-Koordinaten benutzt werden. Die y-Koordinate bleibt fest, damit sichergestellt werden kann, dass die Gegenstände in der Szene auf dergleichen Höhe wie die Kamera sind.
Abbildung 12: Position von Münzen zufällig bestimmen
Für den Fall, dass der Spieler beim Herumirren im Labyrinth versehentlich wieder
zum Eingang gelangt, und diesen fälschlicherweise für den Ausgang hält, ist dort
ein Schild(in) platziert, auf dem ein rotes Kreuz blinkt. Dies verdeutlicht, dass das
der falsche Weg ist.
Zur Realisierung des blinkenden Kreuzes wird ein SoBlinker-Knoten verwendet
(siehe Abb.14 Der Subgraph In). Es werden zwei verschiedene Texturen angehängt,
wobei es sich bei der ersten um ein schwarzes Kreuz auf Holz handelt (wood), bei der
zweiten um ein Rotes (woodred). Der Blinker-Knoten wechselt in der angegebenen
Geschwindigkeit zwischen den beiden Kind-Knoten hin und her.
Abbildung 13: Der SoBlinker-Knoten
16
Der Ausgang des Labyrinths ist zu Beginn mit einer Tür verschlossen, die als
SoSeparator-Knoten out an den Root-Knoten gehängt wird. Diese Tür verschwindet im Laufe des Spiels, wenn maxanzahlCoins = (size/2)+1 eingesammelt wurden. Das heißt also, dass ein Benutzer das Spiel nicht unbedingt erfolgreich beenden
kann, indem er auf dem schnellsten Weg zum Ausgang findet. Es kann mitunter
nötig sein, Umwege zu gehen, um die Mindestanzahl an Münzen zu erreichen.
Abbildung 14: Der Subgraph In
Die Geometrie der Szene ist somit vollständig aufgebaut. Im nächsten Schritt geht
es darum, die User-Interaktion zu implementieren und einen Spieleablauf einzubinden. Dem Spieler soll sich, bzw. die Kamera, durch die Szene bewegen können. Es
muß also entscheiden werden, wie die Steuerung realisiert wird.
3.3.2 Die Kamerasteuerung
Die Kamera wird, wie schon erwähnt, vor den Eingang mit Blickrichtung ins Innere
des Labyrinths positioniert. Da der Labyrinth-Eingang sich an der Position (0., 1.5,
1. ) im Weltkoordinatensystem befindet, wird die Kamera ein Stück zurückgesetzt
an die Position camera->position.setValue(-1.,1.5,1.), die Blickrichtung ist
entlang der positiven x-Achse.
Für die Kamera-Steuerung werden die Pfeiltasten verwendet. Wird der Up-Arrow
gedrückt, bewegt sich die Kamera nach vorn, beim Down-Arrow zurück. Dabei bleibt
die Blickrichtung nach vorn gerichtet. Mit den Right- und Left-Arrows rotiert die
Kamera in die entsprechende Richtung.
Um das Verhalten des Programms für eine solche Tastatur-Eingabe zu definieren,
wird ein SoEventCallback-Knoten benutzt.
17
Abbildung 15: Der Callback-Knoten
Die Parameter der Funktion definieren, auf welche Art von Ereignis der Callback
reagiert, die Callback-Funktion KeyPressCB selbst und den Knoten der dem Callback übergeben wird. In diesem Fall ist das die Kamera.
Tritt eine Tastatureingabe (KeyPressEvent) auf, wird die Callback-Funktion aufgerufen, die überprüft, ob es sich bei der Eingabe um eine der Pfeil-Tasten handelt.
Ist dies der Fall, wird die neue Position der Kamera berechnet. Für andere Tasten
ist kein Verhalten definiert und es geschieht garnichts.
Soll die Kamera vor oder zurück bewegt werden, wird der Translations-Vektor
transl berechnet, der sich aus der Multiplikation der Richtung mit der als SPEED
definierten Geschwindigkeit 0.2f ergibt. Die Kamera wird auf die neue Position
cam->position.setValue(cam->position.getValue() + transl) gesetzt und der
Eventcallback als setHandled() definiert.
Handelt es sich bei der Tastatur-Eingabe um die linke oder rechte Pfeiltaste, wird
die rotierte Blickrichtung bzw. Orintierung der Kamera ermittelt. Dem RotationsVektor rot wird die Rotationsachse und der Winkel übergeben. Die aktualisierte
Orientierung der Kamera ergibt sich aus der Multiplikation der als Radians-Winkel
gegebenen Orientierung der Kamera und dem als RotAngle definierten Winkel von
π
4 Grad ( 45
in Radians). Auch in diesen beiden Fällen wird der Event-Callback am
Ende auf setHandled() gesetzt.
18
Abbildung 16: Die Callback-Funktion
3.3.3 Die Kollisionserkennung und das Picking
Um zu verhindern, dass man in dem Labyrinth durch die Wände gehen kann, muss
eine Kollisionserkennung zwischen der Kamera und der Geometrie der Szene implementiert werden. Auch das Einsammeln der Münzen und Karten basiert auf
einer vorangegangenen Kollisionserkennung. Die Implementierung dieses Verfahrens hat mir am meisten Schwierigkeiten bereitet. Obwohl meine Probleme dabei
schlussendlich nur auf kleineren Mißverständnissen und Definitionen an der falschen
Stelle beruhten, hat die Kollisionserkennung mehr Zeit, als geplant in Anspruch genommen. Am Ende habe ich dadurch jedoch ein tieferes Verständnis für den Aufbau
eines Szenegraphen und seine Verwendung erlangt.
Da die Möglichkeit einer Kollision direkt vom Verhalten bzw. der Steuerung der
Kamera abhängig ist, muß die Kollisionserkennung und die nötige -behandlung im
KeyPressCallback ausgeführt werden.
19
In der Callback-Funktion wird die testCam mit den übergebenen Daten der Kamera
initialisiert. Für jede Steuerungs-Eingabe wird die nächste Position oder Orientierung zuerst daraufhin überprüft, ob sie noch kollisionsfrei erreicht werden kann.
Abbildung 17: Die Test-Kamera
Die Kollionserkennung wird mit Hilfe der SoRayPickAction *intersectionCheck
ausgeführt (siehe Abb.23). Die RayPickAction wird mit den Positionskoordinaten
und der Blickrichtung der Test-Kamera initialisiert und auf dem Root-Knoten ausgeführt. Das heißt, dass ein Strahl von der aktuellen Position aus in Blickrichtung
geschickt wird, der das erste Objekt entlang dieses Strahls findet. Gibt es ein solches Objekt, liefert die RayPickAction mit dem Aufruf
intersectionCheck->getPickedPoint() den Schnittpunkt zwischen Strahl und
Objekt. Ansonsten gibt die Funktion NULL zurück. Mit der Überprüfung dieses
Wertes wird bestimmt, wie sich das Programm weiter verhalten soll.
Da die Picking-Aktion nur an Objekten, die sich in unmittelbarer Nähe befinden
interessiert ist, wird sie auf den Bereich 0.1 cm bis 0.4 cm vor der Test-Kamera
beschränkt. Objekte, die sich weiter weg befinden, werden nicht untersucht. Mit
dieser Beschränkung wird zugleich ein Mindestabstand von 0.4 cm definiert, bis
auf den sich die Kamera den Wänden nähern kann, bevor eine Kollisionserkennung
nötig ist. Befindet sich die Test-Kamera mehr als 0.4 cm von den umliegenden Objekten entfernt, liefert die Abfrage intersectionCheck->getPickedPoint() den
Wert 0. In diesem Fall wird die Kameraposition oder- orientierung auf die Position
oder Orientierung der Test-Kamera gesetzt und der Callback wird verlassen.
Wird für den Bereich < 0.4 vor der Kamera ein kollidierendes Objekt gefunden,
muss ermittelt werden, ob es sich um ein Wandelement, eine Münze oder eine Karte
handelt. Es wird ein Schnittpunkt ungleich 0 vom Typ SoPickedPoint zurückgegeben. Da es sich bei dem Schnittpunkt um einen const-Wert handelt, muss für
jede Bewegung eine neue RayPickAction aufgerufen werden. Andernfalls kann die
Kamera nach der ersten Kollision nicht mehr bewegt werden, da schon ein Schnittpunkt != 0 gefunden wurde.
Den Aufruf interP->getDetail() liefert zusätzliche Information über das Objekt,
mit dem ein Schnittpunkt existiert. Die Information, die für die Objekterkennung
von Interesse ist, bezieht sich auf den Shape-Typ des Objekts. Da nur bestimmte
Objekte über eine SoDetail-Subklasse verfügen, muß darauf geachtet werden, dass
alle in der Szene verwendeten Objekte dieses Kriterium erfüllen. Aus diesem Grund
habe ich das zu Anfang benutzte Nurbs-Surface, mit dem die Karte realisiert wurde, verworfen und statt dessen einen Faceset-Knoten verwendet. Nurbs-Surfaces
20
verfügen über keine SoDetail-Information. Es ist natürlich ebenfalls zu bedenken,
dass Objekte, die ein unterschiedliches Verhalten des Programms erfordern, auch
verschiedene Erscheinungsformen haben sollten.
Bei den drei in der Szene verwendeten Shape-Objekten handelt es sich um einen Cube (Wände), der über die Subklasse SoCubeDetail verfügt, einen Zylinder (Münzen)
mit der SoCylinderDetail-Klasse und ein Faceset (Karten) mit dem entsprechenden SoFaceDetail-Knoten. Wird eine Kollision entdeckt, gibt es also drei verschiedene Möglichkeiten, wie das Programm darauf reagieren soll.
Abbildung 18: Die Kollisionerkennung und -behandlung
21
1. Handelt es sich bei dem geschnittenen Objekt um einen SoCube, also um
ein Wandelement, behält die Kamera ihre alte Position bzw. Orientierung
einfach bei. Der Callback wird verlassen, ohne dass irgendwelche Änderungen
vorgenommen werden. Es wird somit verhindert, dass die Kamera sich durch
eine Wand hindurch bewegen kann und die Wände erwecken so den Eindruck,
aus massivem Stein zu bestehen.
2. Liefert der Aufruf interP->getDetail() ein SoCylinderDetail, handelt es
sich um eine Münze. Diese wird dann aus dem Szenegraphen entfernt und
ein Zähler, der die Anzahl der bereits gefundenen Müzen angibt, wird um
1 hochgezählt (ccounter++). Ein SoPickedPoint-Knoten verfügt über die
Methode getPath(), die den Pfad zu dem geschnittenen Objekt zurück gibt.
Die Knoten in diesem Pfad können über ihren Index angesprochen werden.
Diese Funktion habe ich mir zu Nutze gemacht, um die entsprechende Münze
aus dem Szenegraphen zu löschen.
Da der Szenegraph während der Traversierung nicht verändert werden kann,
wird das Abhängen innerhalb des Pfades ausgeführt. Der letzte Knoten im
Pfad ist der SoCylinder-Knoten der entsprechenden Münze. Da hier aber
der komplette darüber liegende SoSeparator-Knoten setCoin gelöscht werden
soll, wird das Element mit dem Index 2 (vom Ende des Pfades aus gezählt),
welches dem SoSeparator-Knoten coins entspricht (vgl. Abb. 11a Die Subgraphen Coins und Maps) instanziiert und der entsprechende setCoin-Knoten
(Index 1) abgehängt.
Es muß an dieser Stelle noch überprüft werden, ob die Mindestanzahl an
Münzen schon gefunden wurde. Ist dies der Fall, wird die Tür, die den Ausgang verschließt ebenfalls aus dem Szenegraphen gelöscht. Wie viele Münzen
noch benötigt werden, wird über die Konsole ausgegeben.
3. Als dritte Möglichkeit kann ein SoFaceDetail zurück gegeben werden, was
bedeutet, dass der Spieler eine Karte gefunden hat. Auch hier wird über den
Pfad auf den entsprechenden setMap-Knoten zugegriffen und er wird aus dem
Szenegraphen gelöscht.
Der angehängte SoAlarmSensor wird dann eingeplant und das Labyrinth wird
füer 15 Sekunden aus Sicht der mapCam, also von oben, gezeigt. Um die Position des Spielers in der Szene zu markieren, wird für die Dauer dieser KameraEinstellung eine rote Kugel auf die aktuelle Position der Kamera gesetzt. Sind
die 15Ssekunden abgelaufen, ruft der AlarmSensor seine Callback-Funktion
auf, die den CameraSwitch wieder auf camera stellt. Die rote Kugel wird
wieder aus dem Graphen entfernt und das Spiel kann fortgesetzt werden.
Wenn der Spieler genügend Münzen gesammelt und den Ausgang durchschritten
hat, ist das Spiel beendet. Der camSwitch wechselt zu der Ansicht der mapCam und
der 2-dimensionaler Text “You Won” (SoText2-Knoten) wird angezeigt.
22
4 Ergebnisse
Abbildung 19: Die Anfangsposition der Kamera mit Blick ins Innere des Labyrinths
Abbildung 20: Die Tür vor dem Ausgang
23
Abbildung 21: Das Warnschild vor dem Eingang
Abbildung 22: Eine Münze
24
Abbildung 23: Eine Karte
Abbildung 24: Sicht von oben auf ein 20*20-Labyrinth
25
Abbildung 25: Sicht von oben auf ein 11*11-Labyrinth
Abbildung 26: Gewonnen
26
Abbildung 27: Panorama in +x/+z-Richtung
Abbildung 28: Panorama in -x/-z-Richtung
27
5 Fazit und Ausblick
Die Entwicklung dieses interaktiven 3D-Spiels war für mich eine gute Möglichkeit,
ein Gefühl dafür zu entwickeln, wie die Planung und Umsetzung eines derartigen
Projekt ablaufen sollte. Neben der Vertiefung meiner Kenntnisse der Programmiersprache C++ war für mich die Verwendung eines Szenegraphen eine interessante
Herausforderung.
Bei der Programmierung waren einige Bereiche einfacher als gedacht umzusetzen,
wogegen ich an anderen Stellen auf Probleme stieß, mit denen ich nicht gerechnet
hatte. Die Erstellung der Module in 3D benötigte überraschend wenig Zeit und
vermittelte mir einen guten Einstieg in die Verwendung eines Szenegraphen. Die
zufällige Generierung des Labyrinths hingegen erwies sich als schwieriger, als erwartet, da mehr Ausnahemefälle zu behandeln waren, als vorab angenommen. Die
größten Schwierigkeiten hatte ich jedoch, wie erwartet, mit der Implementierung der
Kollisionserkennung und -behandlung. Die richtige Anwendung der RayPickAction
und die Programmierung der Interaktion mit den zu sammelnden Gegenständen
erforderte viel Arbeit und Geduld.
Aus der Vielzahl von Funktion in Coin3D diejenige zu finden, die das aktuelle
Problem beseitigt, war ebenfalls sehr zeitaufwändig. Das Handbuch “The Open Inventor Mentor” war mir dabei zwar eine große Hilfe, im Nachhinein betrachet wäre
es mir jedoch lieber gewesen, mich in die verwendete Software vor dem tatsächlichen
Beginn der Studienarbeit einzuarbeiten und somit mehr Zeit für die Implementierung zu haben.
Mit zunehmender Komplexität des Programms fielen mir immer mehr Features ein,
mit denen ich das Spiel erweitern könnte. Auch wenn ich es nicht mehr geschafft
habe, alle zu implementieren, möchte ich an dieser Stelle noch einige erwähnen.
In der jetzigen Version befindet sich der Ein- und Ausgang immer an der gleiche
Stelle. Das heißt, man weiß immer in ungefähr in welche Richtung man sich bewegen muß. Um das Spiel zu erschweren, wäre es deshalb schön, wenn sowohl der
Eingang, als auch der Ausgang variabel gesetzt werden könnten.
Da ein Spiel ohne Ton immer etwas eintönig erscheint, wäre die Einbindung von
Sound eine interessante Erweiterung. Auch die Implementierung einer Zeitbegrenzung wäre denkbar. Die abgelaufene Zeit sollte dann stets im Blickfeld des Spielers
sein, was eventuell durch die Projektion von Text auf die Nearplane realisiert werden könnte. Mein Hauptanliegen wäre es jedoch, aus dem Spiel eine freistehende
Applikation zu machen, bei der die Ein- und Ausgabe nicht mehr über die Konsole
erfolgt.
Abschließend kann ich nur sagen, dass ich wirklich viel gelernt habe und mit dem
Ergebnis zufrieden bin.
28
Abbildungsverzeichnis
1
2
3
4
5
6
7
8
9
11
10
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Symbole für verwendete Knoten . . . . . . . . . . . . . . . . . . . . .
Definition der Module . . . . . . . . . . . . . . . . . . . . . . . . . .
Beispiel-Module in 3D . . . . . . . . . . . . . . . . . . . . . . . . . .
Die Klasse Lab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Das Umfeld-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . .
Die Switch-Anweisung . . . . . . . . . . . . . . . . . . . . . . . . . .
Der Szenegraph vom Root-Knoten aus . . . . . . . . . . . . . . . . .
Der Subgraph Laby . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Schleife, um Module zu setzen . . . . . . . . . . . . . . . . . . . . . .
Die Subgraphen Coins und Maps . . . . . . . . . . . . . . . . . . . .
zeitgesteuerte Rotation . . . . . . . . . . . . . . . . . . . . . . . . . .
Position von Münzen zufällig bestimmen . . . . . . . . . . . . . . . .
Der SoBlinker-Knoten . . . . . . . . . . . . . . . . . . . . . . . . . .
Der Subgraph In . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Der Callback-Knoten . . . . . . . . . . . . . . . . . . . . . . . . . . .
Die Callback-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . .
Die Test-Kamera . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Die Kollisionerkennung und -behandlung . . . . . . . . . . . . . . . .
Die Anfangsposition der Kamera mit Blick ins Innere des Labyrinths
Die Tür vor dem Ausgang . . . . . . . . . . . . . . . . . . . . . . . .
Das Warnschild vor dem Eingang . . . . . . . . . . . . . . . . . . . .
Eine Münze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Eine Karte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sicht von oben auf ein 20*20-Labyrinth . . . . . . . . . . . . . . . .
Sicht von oben auf ein 11*11-Labyrinth . . . . . . . . . . . . . . . .
Gewonnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Panorama in +x/+z-Richtung . . . . . . . . . . . . . . . . . . . . . .
Panorama in -x/-z-Richtung . . . . . . . . . . . . . . . . . . . . . . .
29
5
7
8
9
11
12
13
13
14
15
15
16
16
17
18
19
20
21
23
23
24
24
25
25
26
26
27
27
Literatur
[1] The Inventor Mentor: Programming Object-Oriented 3D Graphics with
Open Inventor, Release 2, [Wer94] Wernecke, J., Addision-Wesley, 1994
[2] Open InventorT M C++ Reference Manual: The Official Reference Document
for Open Inventor, Release 2. Open Inventor Architecture Group, AddisonWesley Publishing Company, July 1994
[3] www.coin3d.org
[4] www-eleves-isia.cma.fr/documentation/OpenInventorDoc/Coin/
30