Inhaltsverzeichnis

1  Einleitung  5

2  Aufgabenstellung  6

2.1  Ausgangspunkt  6

2.2  Aufgabendefinition  7

2.3  Eingrenzung  8

3  Fachliches Umfeld  9

3.1  Theoretischer Hintergrund  9

3.1.1  Dreidimensionales Terrain in Computeranwendungen  9

3.1.2  Heightmaps  11

3.1.3  Plasma-Fraktale  12

3.1.4  Prozedurale Synthese  13

3.1.5  Skybox  13

3.1.6  Quaternions  14

3.1.7  Multitexturing  16

3.2  Technologischer Hintergrund  18

3.2.1  Apple iPhone 3GS  18

3.2.2  OpenGL ES 2.0  19

3.2.3  PowerVR SDK  20

3.3  Algorithmen zur prozeduralen Terrain-Synthese  21

3.3.1  Fuzzy-Landscaping  21

3.3.2  Fault-Line Algorithmus  22

3.3.3  Circles Algorithmus  23

3.3.4  Midpoint-Displacement  24

3.3.5  Particle-Deposition  25

3.3.6  Fractal-Brownian-Motion  26

3.4  Analyse der Algorithmen  27

3.4.1  Gewichtung  27

3.4.2  Auswahl  28

3.4.3  Ausblick  29

4  Implementierung des Spiels  30

4.1  Implementierung der Algorithmen  30

2

Inhaltsverzeichnis

4.1.1  Particle-Deposition Terrain  30

4.1.2  Midpoint-Displacement Terrain  33

4.1.3  Analyse Midpoint-Displacement und Particle-Deposition  37

4.1.4  Finale Auswahl  42

4.2  Implementierung des Spiels  42

4.2.1  Das Spielfundament - Die PVRShell  42

4.2.2  Die GameEngine Klasse  43

4.2.3  Skybox  44

4.2.4  Flugzeug Kamera mit Verzögerung  44

4.2.5  Terrain Multitexturing  47

4.3  Beschleunigungsansätze  50

4.3.1  Array of Structures  50

4.3.2  Vertex-Buffer-Objects  51

4.3.3  Beleuchtungsmodell  51

4.3.4  Das Terrain als Triangle-Strip  53

4.3.5  Bitoperationen  55

5  Ergebnisse und Bewertung  58

5.1  Darstellung des Erreichten  58

5.2  Mögliche Verbesserungen  59

5.3  Das Spiel  60

6  Zusammenfassung und Aussicht  61

7  Literaturverzeichnis  62

8  Abbildungsverzeichnis  64

3

1 Einleitung

Für viele Menschen sind Computerspiele eine beliebte Freizeitbeschäftigung geworden. Waren sie vor einigen Jahren hauptsächlich auf Spielkonsolen und Heimcomputern vertreten, steigt nun ihre Verbreitung auf Smartphones und Mobiltelefonen. Die Etablierung von Apple´s App Store oder dem Android Marketplace hat dem Trend weiteren Aufschwung gegeben. Kostenlos oder gegen Geld können über diese Portale Anwendungen auf dem eigenen Smartphone installiert werden.

Im Bezug auf Speicherplatz, Systemressourcen und Grafikperformance sind die mobilen Endgeräte dem Heimcomputern und Spielkonsolen unterlegen. Deutlich sichtbar wird dieser Umstand bei 3D-Computerspielen. Sie benötigen tendenziell mehr Speicherplatz und Systemressourcen als ihre 2D-Pendants. Dies liegt im erhöhten Rechenbedarf, welcher nötig ist um komplexe 3D-Szenen in Echtzeit darzustellen. Durch Spielinhalte, welche durch prozedurale Methoden generiert wurden, können Systemressourcen geschont werden. Denn die Spielinhalte stehen nicht von Anfang an fest, sondern werden erst zur Ausführung des Programms generiert. Der Speicherplatz für Programmdaten entfällt. Des Weiteren liefert die zufallsgesteuerte Synthese der prozeduralen Methoden eine große Anzahl an verschiedenartigen Ergebnissen. Bei jedem Programmstart werden nach festgelegten Ausgangsparametern neue Inhalte generiert. Das Ziel dieser Arbeit liegt in der Implementierung eines 3D-Flugsimulators, dessen Spielterrain nach prozeduralen Methoden generiert wird. Die zugrunde liegende Zielhardware ist das iPhone 3GS, welches mit PowerVR SGX Grafikprozessor Shaderoperationen unter OpenGL Es 2.0 unterstützt.

Das folgende Kapitel liefert einen genaueren Bezug zum Thema und geht detaillierter auf die Problemstellung ein. Anschließend wird im dritten Kapitel das fachliche Umfeld abgesteckt. Dabei wird der theoretische Hintergrund aufgearbeitet und ein Blick auf die technologische Ebene dieser Arbeit geworfen. Darauf aufbauend, befasst sich der letzte Abschnitt mit der Vorstellung und kritischen Bewertung verschiedener Algorithmen zur Terrain-Generierung. Mit der Implementierung des prozeduralen Terrains und der Umsetzung des Spiels befasst sich Kapitel vier. Auch Ansätze zur Beschleunigung der Anwendung werden an dieser Stelle diskutiert. Kapitel fünf beleuchtet die Ergebnisse dieser Thesis und befasst sich mit möglichen Verbesserungen. Abschließend wird in Kapitel sechs ein zusammenfassender Rückblick auf diese Arbeit geworfen.

4

2 Aufgabenstellung

2.1 Ausgangspunkt

Der gegenwärtige Stand der Technik im Heimcomputerbereich glänzt bei der Darstellung von 3D-Spielen mit atemberaubenden Effekten und brillanter Grafik. Seit den letzten Jahren steigt auch im Bereich der Smartphones die Verbreitung von Spielen. Die OpenGL Unterstützung dieser Geräte ermöglichte es, Anwendungen zu programmieren, welche bis vor kurzem nur auf Heimcomputern oder Spielkonsolen darstellbar waren. Auf der anderen Seite werden Smartphones durch limitierende Faktoren eingeschränkt. Die Gesamtheit der Systemressourcen ist beschränkt und eine Aufrüstung ist meist nicht möglich. Die Rechenkapazitäten der Smartphones steigen zwar stetig, sind aber im Vergleich zur PC Hardware gering. Ein weiterer Nachteil liegt in der begrenzten Einsatzdauer. Die Kapazität des Akkus gibt den maximalen Zeitraum der Benutzung vor und rechenintensive Anwendungen können die Zeit zwischen zwei Aufladungen erheblich reduzieren.

Eine Möglichkeit die begrenzten Systemressourcen von Smartphones zu schonen, liegt in der Verwendung von prozeduralen Methoden. Sie ermöglichen die Erzeugung von Programminhalten verschiedenster Art. Prozedurale Methoden benötigen keinen Speicherplatz auf dem System, da die Inhalte erst zur Laufzeit des Programms generiert werden. Die Synthese basiert auf festen Ausgangsparametern, erfolgt aber zufallsgesteuert. Der Zufallsfaktor bewirkt, dass die Ergebnisse nie gleich sind. Mit Blick auf die Systemressourcen liegt der Vorteil prozeduraler Methoden in den theoretisch unbegrenzt möglichen Variationen, die erzeugt werden können. Eine vorherige Erstellung der Inhalte durch den Entwickler entfällt, genauso wie deren Speicherung auf dem Gerät.

In Computerspielen wurden prozedurale Methoden schon früh angewendet ¹ . Das prozedurale Leveldesign einer bekannten Action-Rollenspiel Serie ² begeisterte um die Jahr-

tausendwende viele Computerspieler. Die zufällig generierten Spiel-Levels sahen immer unterschiedlich aus und das sorgte für hohen Langzeit-Spielspaß. In einem aktuellen Ego-Shooter ³ werden ebenfalls prozedurale Methoden verwendet. In dem Spiel ist es möglich

mit über einer halben Million prozedural erstellter Waffen zu spielen, welche allesamt verschiedene Eigenschaften besitzen. Wären diese Spieldaten vorausberechnet worden,

¹ Elite (1984) und The Sentinel (1986)

² Diablo (1990) und Diablo II (2000), Blizzard North

³ Borderlands (2009), Gearbox Software

5

wäre die dafür benötigte Speichermenge enorm hoch gewesen. Die zur deutschen Demoszene gehörende Gruppe Farbrausch zeigt, dass es auch möglich ist ein komplettes 3D-Spiel mit der Größe von nur 96 Kilobyte zu entwickeln. In ihrem Spiel ⁴ wird von Models über Texturen, bis hin zur Spielmusik, alles prozedural

zur Laufzeit erstellt. Damit gewann Farbrausch 2006 den Deutschen Entwicklerpreis für das innovativste Spiel des Jahres [Farbrausch, 2006].

2.2 Aufgabendefinition

Für die Entwicklung des Spiels ist die Auseinandersetzung mit verschiedenen Problemstellungen unabdingbar. Ein Kernbereich dieser Arbeit ist die Auseinandersetzung mit dem Thema der prozeduralen Terrain-Generierung und der dafür zur Verfügung stehenden Algorithmen. Da diese das Terrain nach unterschiedlichen Vorgehensweisen generieren, variieren die optischen Resultate sehr stark. Aus diesem Grunde müssen die Algorithmen auf ihre Verwendbarkeit hin geprüft werden. Folglich muss ein Bewertungssystem geschaffen werden, dass es ermöglicht die Eigenschaften der Algorithmen durch Kriterien zu gewichten. Der Algorithmus, welcher sich unter den Kriterien als der Tauglichste herauskristallisiert, wird anschließend programmiertechnisch umgesetzt und zur Darstellung des Spielterrains verwendet werden. Der Titel Isle of Skye ist eine Anlehnung an die gleichnamige Insel im Nordwesten Schottlands und dementsprechend soll auch das Spielterrain die Form einer Insel aufweisen.

Der zweite Kernbereich dieser Arbeit umfasst die Realisierung des Flugsimulators. Dazu gehört die Entwicklung einer Spiel-Engine, welche in der Lage ist alle wesentlichen Spielabläufe zu koordinieren. Darunter fallen unter Anderem das Behandeln von Events, das Aktualisieren der Spiellogik sowie das Rendern der 3D-Szene.

In der Simulation soll der Spieler das Flugzeug aus der Perspektive einer Third-Person 5

Kamera bewegen. Die Steuerung des Flugzeugs soll durch den eingebauten Beschleu-nigungssensor des iPhones ermöglicht werden. Auf diese Weise wird durch drehen und neigen des iPhones eine Steuerung des Flugzeugs ohne Berührung des Touchscreens möglich. Um die Geschwindigkeit des Flugzeugs zu animieren soll ein Partikelsystem implementiert werden, welches je nach Geschwindigkeit unterschiedlich stark ausgeprägt ist.

Zur Unterstreichung der Spielatmosphäre wird eine Skybox die Spielwelt umschließen. Zudem wird das Terrain mit Hilfe von Multitexturing entsprechend seinen Höhenwerten texturiert. Verschiedenen Geländestufen und die Vegetationsgrenze lassen sich auf diese Weise visualisieren.

Die zugrunde liegende Zielumgebung ist das iPhone 3GS welches mit PowerVR SGX

⁴ .kkrieger (2004), .theprodukkt

⁵ Eine Perspektive bei der die Kamera typischerweise hinter oder über dem Charakter schwebt.

6

Grafikprozessor Shaderoperationen unter OpenGL Es 2.0 unterstützt. Diese werden ausgenutzt um im Spiel ein realistisches Beleuchtungsmodell zu simulieren. Da die Umsetzung dieser Arbeit auf einem Smartphone mit begrenzten Systemressourcen basiert, sind Methoden zur Beschleunigung der Terrain-Synthese und Rendergeschwindigkeit sinnvoll. Mögliche Beschleunigungsansätze werden in dieser Arbeit behandelt und im Spiel umgesetzt.

2.3 Eingrenzung

Die Reihe der im nachfolgenden Kapitel vorgestellten Algorithmen erhebt keinen Anspruch auf Vollständigkeit. Vielmehr wird eine Auswahl von sechs bekannten und etablierten Verfahren dargestellt und untersucht. Die vollständige Implementierung jedes Algorithmus würde den Rahmen dieser Arbeit sprengen. Aus diesem Grunde werden in Abstimmung mit einem Bewertungssystem nur die tauglichsten Algorithmen umgesetzt. Prozedurale Synthese ermöglicht auch die Generierung von anderen Spielinhalten, wie Texturen oder Musik [vgl. Abschnitt 3.1.4]. Jede dieser Syntheseformen ist ein komplexes Thema für sich. Aus diesem Grunde liegt der Fokus dieser Arbeit ausschließlich auf der prozeduralen Synthese von Terrain.

Die theoretische Basis der im Folgenden diskutierten Konzepte werden durch das Spiel Isle of Skye belegt. Es weist die Kernelemente eines Flugsimulators auf, besitzt in jedem Fall aber einen prototypischen Charakter und wird in dieser Form keinesfalls mit einem kommerziellen Spiel vergleichbar sein.

7

3 Fachliches Umfeld

3.1 Theoretischer Hintergrund

Im folgenden Abschnitt werden eine Anzahl ausgewählter und im 3D-Bereich gebräuchlicher Techniken vorgestellt. Ihre theoretischen Hintergründe werden erläutert und Verfahrensweisen zur Umsetzung aufgezeigt. Auf diesem theoretischen Fundament baut die spätere Implementierung des Spiels Isle of Skye auf.

3.1.1 Dreidimensionales Terrain in Computeranwendungen

Gegenwärtige Computerspiele sind in der Lage durchweg realistisch anmutende Landschaften in einem hohem Detailgrad darzustellen. Schroffe Berggipfel oder sanfte Hügelketten, sowie die natürlich wirkende Darstellung von Ebenen und tiefen Tälern, bestimmen den aktuellen Stand der 3D-Technik (Abbildung 3.1).

Abbildung 3.1: Screenshot aus dem Spiel Stalker - Call of Pripyat (2009).

8

Definiert werden diese Außenareale meist durch Polygonnetze. Diese werden auch Dreiecksnetz oder Mesh genannt. Ein Polygonnetz wird durch eine endliche Anzahl an Punkt-koordinaten im 3D-Raum bestimmt (Abbildung 3.2). Diese Punktkoordinaten werden Vertex ¹ genannt. Neben den Punktkoordinaten werden zusätzlich auch noch Informa-

tionen über den Normalen-Vektor des Vertex und dessen Koordinaten auf der Textur gespeichert.

Abbildung 3.2: Das Polygonnetz eines dreidimensional gerenderten Terrains.

Mit Hilfe von Texturkoordinaten kann über die formgebende Grundstruktur des Polygonnetzes eine Rastergrafikdatei gelegt werden. Die Oberflächendetails eines Terrainpolygons erhöhen sich beispielsweise stark durch die Verwendung von Sand-, Gras- oder Felstexturen. Das Terrain wirkt auf diese Weise natürlicher, da es mehr an seine realen Vorbilder erinnert.

Im Zusammenspiel mit einer Lichtquelle dienen die Vertex Normalen der Ermittlung des Lichteinfalls auf das texturierte Dreiecksnetz. Durch verschiedene Beleuchtungsmodelle wird auf diese Weise die realistische Beleuchtung einer Oberfläche ermöglicht. Bekannte Beleuchtungsmodelle sind das Phong- und das Blinn-Modell welche in Abschnitt 4.3.3 behandelt werden.

¹ pl. Vertices

9

3.1.2 Heightmaps

Das zur Darstellung von Terrain notwendige Dreiecksnetz muss nicht zwingend mit Hilfe eines 3D-Modelling-Programms ² erstellt werden. Dreidimensionales Terrain kann auch mit Hilfe von Heightmaps generiert werden. Heightmaps ³ sind Rastergrafik-Dateien, de-

ren enthaltene Farbinformationen es ermöglicht, die Oberfläche eines Objektes zu definieren (Abbildung 3.3).

Die Heightmap stellt dabei das Relief der Geländetopographie auf dem gewünschten Dreiecksnetz dar (Abbildung 3.4).

Abbildung 3.4: Die dreidimensional gerenderte Heightmap aus aus Abbildung 3.3.

² Maya, Blender oder 3D Studio Max

³ Heightmaps sind auch als Höhenfelder oder Höhenkarten bekannt.

10

Die verschieden Abstufungen des Farbwertes pro Bildsegment bestimmen den Höhenwert am korrespondierenden Vertex. Folglich legen die Farbwerte der Abtastpunkte die Höhe des Geländes fest. Die Abstufung der Abtastwerte erfolgt in Graustufen. Dunkle Farbwerten definieren tiefe Punkte und helle Farbwerte hohe Punkte.

3.1.3 Plasma-Fraktale

Plasma-Fraktale sind geometrische Figuren, welche einen hohen Grad an Selbstähnlichkeit aufweisen. Selbstähnlichkeit bedeutet, dass diese Figuren aus kleineren Kopien von sich selbst bestehen. Diese kleineren Figuren sind wiederum sich selbst ähnlich (Abbildung 3.5).

Landschaften und Geländeformationen auf der Erde sind ebenfalls selbstähnlich. Hält man einen zerklüfteten Stein in der Hand und betrachtet ihn, entdeckt man genau dieselben Unebenheiten wie an einer Bergkette, die sich am Horizont entlang zieht. Die selben Strukturen und Muster, welche der Betrachter im Großen findet, finden sich auch im Kleinen wieder.

Die Eigenschaft der Selbstähnlichkeit ermöglicht es, natürlich wirkendes, dreidimensionales Gelände aus Plasma-Fraktalen zu generieren. Unabhängig von der Skalierung im Anwendungsprogramm sieht dieses Gelände, aufgrund seiner fraktalen Struktur, immer wie wirkliches Terrain aus [Martz, 1996, vgl.].

11

Eine treffende nichtmathematische Beschreibung von Plasma-Fraktalen formuliert Jesse Laeuchli in einem Artikel über Fraktal-Programmierung:

„A good non-mathematical definition of a fractal is something regular that has randomness added in a controlled way. Things modeled with fractals are not completely random, but they are not entirely orderly either.“ [DeLoura, 2001, S. 239]

3.1.4 Prozedurale Synthese

Mit Hilfe von Methoden der prozeduralen Synthese können komplexe Programminhalte erschaffen werden. Beispielsweise ist die Generierung von Heightmaps, Texturen oder Musik möglich. Die Inhalte werden dabei nicht vorher vom Entwickler festgelegt, sondern erst zur Laufzeit der Anwendung berechnet. Die Synthese basiert auf festen Ausgangsparametern und folgt zufallsgesteuerten Algorithmen. Aufgrund des Zufallsfaktors in der Synthese kann nach einem einzigen Algorithmus eine nahezu unendliche Variation an Inhalten generiert werden.

3.1.5 Skybox

Um dem Anwender eine unterhaltsame und angenehme Spielerfahrung zu bieten, benötigen interaktive Computerspiele eine konsistente und glaubwürdige Spielwelt. Ein Raumschiff-Shooter im Weltraum ist nicht vorstellbar ohne den Weltraum selbst, als Hintergrund des Spielgeschehens. Auch die Atmosphäre eines Abenteuerspiels in den Bergen lebt von der Schönheit der Hintergrundbilder. Der Spieler sieht am Horizont vereinzelt Wolken und massive Bergrücken um sich herum. In der Ferne könnte sich sogar ein kleines Dorf erahnen lassen. Folglich unterstreichen Hintergrundbilder die Ästhetik der Spielerfahrung und lassen dabei den Spieler tiefer in die Welt eintauchen. Werden derartig detaillierte Umgebungen mit Hilfe von 3D-Modellen erzeugt, verbraucht der Computer zur Ablage der Modelldaten wertvollen Speicherplatz. Zudem verschwenden Prozessor und Grafikchip in jedem Renderdurchgang einen Teil ihrer Rechenleisung für die Transformations- und Beleuchtungsberechnung der Modelle. Das ist ungünstig in Anbetracht der limitierten Systemressourcen des iPhones [vgl. Abschnitt 2.1]. Durch Verzicht auf aufwändige Modelle und deren Beleuchtung, spart die Verwendung einer Skybox dem Computer wertvolle Rechenoperationen. Das Prinzip ist dabei sehr simpel. Die entfernten Landschaften werden auf sechs Texturen gezeichnet, von denen jeweils eine auf jede Innenseite des Würfels gelegt wird. Die Kamera des Betrachters wird in der Mitte des Würfels platziert und kann frei um alle Achsen rotieren. Bewegt sich die Kamera, wird der Würfel analog zur Kamera mitbewegt (Abbildung 3.6). Auf

12

diese Weise ist es niemals möglich die Skybox zu verlassen, denn die Kamera bleibt stets in der Mitte. Die Illusion weiter Ferne ergibt sich für den Spieler durch die Projektion der Bilder auf die Innenflächen des Würfels [DeLoura, 2001, vgl. S. 416]. Durch die Verwendung von Bilddateien sind die Helligkeitswerte der Skybox-Texturen schon vorberechnet und auf ihre Nachbartexturen abgestimmt. Beim zeichnen der Skybox sollte die Beleuchtung der 3D-Szene abgeschaltet werden, denn es ist nicht wünschenswert, das Beleuchtungsmodell auch auf die entfernte Szenerie der Skybox zu übertragen.

3.1.6 Quaternions

Die Orientierungsmöglichkeiten eines Bodenfahrzeugs unterscheiden sich von denen eines Luftfahrzeugs. Soll für eine Anwendung beispielsweise die Steuerung eines Luftkissen-

13