Bachelorarbeit am Institut f¨
ur Informatik der Freien Universit¨at Berlin,
Arbeitsgruppe Software Engineering
Implementierung und Erweiterung eines
rhythmusbasierten Levelgenerators fu¨r
2D-Plattformer
Madlen Thaleiser
Matrikelnummer: 4478415
[email protected]
Betreuer: Prof. Dr. Marco Block-Berlitz
Berlin, 9. M¨arz 2015
Madlen Thaleiser
Zusammenfassung
Spiele in der heutigen Zeit sollen abwechslungsreiche, herausfordernde und
interessante Level besitzen. Die Erstellung solcher Level erfordert meist mehrere Entwickler. In dieser Arbeit wird der rhythmusbasierten Levelgenerator
f¨
ur 2D-Plattformer von Smith et al. vorgestellt und um Multiwege erweitert.
Bei der Erweiterung werden zun¨achst zwei Ans¨atze modelliert, wie Multiwege aussehen und in ein Level integriert werden k¨onnen. Anschließend werden
die von Smith et al. verwendeten prozeduralen Methoden um diese Ans¨atze
erg¨
anzt.
Das Konzept von Smith et al. und die Erweiterung um Multiwege sind in
einem 2D-Plattformerspiel Kitty’s Adventure“ umgesetzt und erprobt wor”
den.
b
Eidesstattliche Erkl¨
arung
Ich versichere hiermit an Eides Statt, dass diese Arbeit von niemand anderem als meiner Person verfasst worden ist. Alle verwendeten Hilfsmittel wie
Berichte, B¨
ucher, Internetseiten oder ¨ahnliches sind im Literaturverzeichnis
angegeben, Zitate aus fremden Arbeiten sind als solche kenntlich gemacht.
Die Arbeit wurde bisher in gleicher oder a¨hnlicher Form keiner anderen Pr¨
ufungskommission vorgelegt und auch nicht ver¨offentlicht.
Name:
Datum:
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Zielsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . .
1
1
1
1
2 Plattformer
¨
2.1 Kurzer geschichtlicher Uberblick
. . . . . . . . . . . . . .
2.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Bestandteile eines Plattformers . . . . . . . . . . . . . . .
2.3.1 Spielfigur . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Plattformen . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Hindernisse . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Sammelobjekte . . . . . . . . . . . . . . . . . . . .
2.3.5 Hilfsobjekte . . . . . . . . . . . . . . . . . . . . . .
2.3.6 Speicherpunkte . . . . . . . . . . . . . . . . . . . .
2.4 Unterscheidung 2D- zu 3D-Plattformer . . . . . . . . . . .
2.4.1
Super Mario Bros“ als Beispiel f¨
ur 2D-Plattformer
”
2.4.2
Mario 64“ als Beispiel f¨
ur 3D-Plattformer . . . . .
”
2.4.3 Fazit aus dem Vergleich . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
4
5
5
6
6
7
7
7
7
8
8
8
3 Prozedurale Generierung
3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Pseudozufallszahlengenerator . . . . . . . . . . . . . .
3.2.2 Generative Grammatiken . . . . . . . . . . . . . . . .
3.2.3 Bildfilter . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 R¨
aumliche Algorithmen . . . . . . . . . . . . . . . . .
3.2.5 Modellierung und Simulation von komplexen Systemen
3.2.6 K¨
unstliche Intelligenz . . . . . . . . . . . . . . . . . .
3.3 Anwendungsgebiete . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Spielbits . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Spielraum . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Spielsystem . . . . . . . . . . . . . . . . . . . . . . . .
3.3.4 Spielszenarien . . . . . . . . . . . . . . . . . . . . . . .
3.3.5 Spieldesign . . . . . . . . . . . . . . . . . . . . . . . .
3.3.6 Abgeleitete Inhalte . . . . . . . . . . . . . . . . . . . .
3.4 Online- und Offline-Generierung . . . . . . . . . . . . . . . .
3.5 Beispiele f¨
ur prozedurale Generierung in Spielen . . . . . . .
3.5.1 Civilization V . . . . . . . . . . . . . . . . . . . . . . .
3.5.2 Borderlands . . . . . . . . . . . . . . . . . . . . . . . .
3.5.3 Rogue . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
9
9
9
10
10
10
11
11
11
11
12
12
13
14
14
15
15
15
16
17
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Ans¨
atze im Bereich der Levelgenerierung
18
4.1 Erfahrungsgesteuerte Levelgenerierung . . . . . . . . . . . . . 18
4.2 Levelgenerierung mit genetischen Algorithmen . . . . . . . . . 18
4.3 Generierung auf Basis von Teill¨osungen . . . . . . . . . . . . 20
5 Rhythmusbasierte Levelgenerierung
5.1 Rhythmus als Ansatz . . . . . . . . . . . . . . . . . . . . . .
5.2 Der Levelgenerator Launchpad“ von Smith et al. . . . . . .
”
5.2.1 Rhythmus und Rhythmusgruppe . . . . . . . . . . .
5.2.2 Struktur des Generators . . . . . . . . . . . . . . . .
5.2.3 Generierung von Rhythmusgruppen . . . . . . . . .
¨
5.2.4 Uberpr¨
ufung durch Kriterien . . . . . . . . . . . . .
5.2.5 Nachbereitung . . . . . . . . . . . . . . . . . . . . .
5.2.6 Verwendete Methoden der prozeduralen Generierung
5.3 Implementierung des Levelgenerators . . . . . . . . . . . . .
5.3.1 Allgemeine Anmerkungen . . . . . . . . . . . . . . .
5.3.2 Programmaufbau . . . . . . . . . . . . . . . . . . . .
5.3.3 Rhythmus und Rhythmusgruppe . . . . . . . . . . .
5.3.4 Kriterien und Nachbereitung . . . . . . . . . . . . .
5.3.5 Methoden der prozeduralen Generierung . . . . . . .
5.3.6 Bewertung der Implementierung . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
22
22
22
23
23
25
25
26
26
26
26
28
30
31
32
6 Erweiterung um Multiwege
6.1 Begriffskl¨
arung . . . . . . . . . . . . . . . . . . . .
6.2 M¨
oglichkeiten der Erweiterung . . . . . . . . . . .
6.3 Modellierung der Multiwege . . . . . . . . . . . . .
6.3.1 Simpler Multiweg . . . . . . . . . . . . . . .
6.3.2 Komplexer Multiweg . . . . . . . . . . . . .
6.4 Implementierung der Multiwege . . . . . . . . . . .
6.4.1 Implementierung des simplen Multiweges .
6.4.2 Implementierung des komplexen Multiweges
6.5 Bewertung . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
34
34
35
35
35
36
36
36
37
38
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Zusammenfassung und
7.1 Zusammenfassung .
7.2 Fazit . . . . . . . . .
7.3 Ausblick . . . . . . .
Ausblick
39
. . . . . . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . . . 40
8 Quellenverzeichnis
8.1 Literatur . . . . . .
8.2 Online-Ressourcen
8.3 Spiele . . . . . . .
8.4 Sonstige Quellen .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
42
43
44
45
A Inhalt der DVD
46
A.1 Bachelorarbeit . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.2 Projekt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1 Einleitung
1
Madlen Thaleiser
Einleitung
1.1
Motivation
An ein Videospiel werden heutzutage hohe Anforderungen gestellt. Neben
einer interessanten Spielmechanik sowie einer spannenden Geschichte soll das
Spiel auch interessante und herausfordernde Level bieten. Die Gestaltung
solcher Level erfordert oftmals mehrere Mitarbeiter eines Entwicklerteams.
Mit der prozeduralen Generierung von Spielinhalten, d. h. der Erzeugung von
Inhalten mittels einer algorithmischen Methode, k¨onnen einzelne Aspekte
der Levelgestaltung ausgelagert werden, so dass Energie und Ressourcen
eingespart oder auch auf andere Bereiche umverteilt werden k¨onnen.
Somit w¨
are es m¨
oglich u.a. Level und R¨atsel automatisch zu generieren,
welche trotz der automatischen Generierung spielbar und l¨osbar sind.
1.2
Zielsetzung
Mit dem Plattformerspiel Kitty’s Adventure“, als Ergebnis dieser Arbeit,
”
soll gezeigt werden, auf welche Weise die rhythmusbasierte Levelgenerierung
der Arbeit von Smith et al. [9, 4] implementiert und um Multiwege erweitert
werden kann.
Die Spielfigur Kitty durchl¨
auft die generierten Level und ist auf der Suche
nach ihrem Zuhause. Jedoch vergisst Kitty jedes mal, wie das Level aussah.
Dies spiegelt die prozedurale Levelgenerierung von unterschiedlichen Leveln
mit Multiwegen wieder.
Die verwendeten Methoden der prozeduralen Generierung aus Abschnitt 3.2
werden erweitert und damit wird demonstriert, wie ein bestehendes Modell
eines Levelgenerators um neue Aspekte erg¨anzt werden kann. Durch diese Erweiterung soll die Grundlage geschaffen werden, neue Konzepte bzw.
Ans¨
atze, durch die Modifizierung der Methoden, in ein bestehendes Modell
einzuf¨
ugen.
F¨
ur die Arbeit und deren Ergebnis, das Plattformerspiel Kitty’s Adven”
ture“, ergeben sich somit zwei Zielvorgaben:
1. Die erzeugten Level sollen spielbar sein.
2. Die Generierung der Level soll in einer m¨oglichst geringen Zeit erfolgen.
1.3
Aufbau der Arbeit
Im nachfolgendem Kapitel 2 wird das Genre der Plattformerspiele dargestellt, dabei wird zun¨
achst die Begrifflichkeit des Plattformers gekl¨art. Des
Weiteren wird erl¨
autert, wieso die Implementierung und deren Erweiterung
sich auf den zweidimensionalen Raum beschr¨anken.
1
1.3
Aufbau der Arbeit
Madlen Thaleiser
Die prozedurale Generierung, deren Methoden und Anwendungsgebiete werden im Kapitel 3 betrachtet. Dabei werden f¨
ur einzelne Anwendungen Beispiele genannt sowie Beispiele prozeduraler Generierung in bestehenden Spielen vorgestellt. Spezielle Ans¨atze f¨
ur die Generierung von Leveln werden im
Kapitel 4 beleuchtet.
In Kapitel 5 wird zun¨
achst der Levelgenerator von Smith et al. [9, 4] erkl¨art. Anschließend wird die Implementierung selbst dargestellt. Dabei wird
auf die einzelnen Phasen der Generierung bzw. auf einzelne Bestandteile des
Generators eingegangen und welche Unterschiede sich bei der Implementierung von Kitty’s Adventure“ im Vergleich zum Konzept von Smith et al.
”
ergeben haben.
Nachdem die Implementierung des Generators im Kapitel 5 erfolgte, wird er
im Kapitel 6 um Multiwege erweitert. In diesem Kapitel wird zun¨achst der
Begriff des Multiweges erkl¨
art und danach werden die damit verbundenen
M¨
oglichkeiten beschrieben. Aus den M¨oglichkeiten werden die Multiwege
modelliert, die danach im Plattformerspiel Kitty’s Adventure“ implemen”
tiert und erprobt werden.
Abschließend wird im Kapitel 7 ein Fazit gezogen sowie ein Ausblick gegeben.
2
2 Plattformer
2
Madlen Thaleiser
Plattformer
Ob nun der Engel Vi D¨
amonen in Wings of Vi“ [30] bek¨ampft, der als Katze
”
kost¨
umierte Mario in Super Mario 3D World“ [31] den Feen zur Hilfe eilt
”
oder Sonic sich durch Zeit und Raum in Sonic CD“ [32] bewegt - alle diese
”
Spiele haben eins gemeinsam: es sind Plattformer.
Seit 2011 sind solche Spiele wieder sehr gefragt, da sie zwar ein einfaches
Spielprinzip haben, dennoch sehr herausfordernd sein k¨onnen. So ist es nicht
verwunderlich, dass neben neuen 3D-Spielen der großen Marken auch viele Neuauflagen alter Klassiker zu finden sind oder an den klassischen Stil
angelehnte Spiele im Bereich der Indiegames entwickelt werden.
Im Folgenden wird gekl¨
art, wie sich die Plattformer entwickelt haben, wie
sie definiert werden und welche Bestandteile solche Spiele im wesentlichen
aufweisen. Des Weiteren werden anhand von Super Mario Bros“ [40] und
”
Mario 64“ [37] Unterschiede von 2D- zu 3D-Plattformern erl¨autert.
”
2.1
¨
Kurzer geschichtlicher Uberblick
1980 ver¨
offentlichte Universal Space Panic“ [44] und begr¨
undete damit das
”
Spielgenre des Plattformers. Dabei konnte sich die Spielfigur nur nach links
und nach rechts bewegen, sowie die Leitern hochklettern, welche die einzelnen Ebenen verbanden. Gegnern galt es entweder auszuweichen oder sie
mittels Schaufeln in ein Loch zu locken und zu erschlagen. Ziel des Spiels
war es, auf die oberste Ebene zu gelangen.
Ein Jahr sp¨
ater, 1981, brachte Nintendo das Arcade-Spiel Donkey Kong“
”
[42] heraus. Das Ziel war ¨
ahnlich zu Space Panic“. Es galt die oberste Etage
”
zu erreichen und Pauline vor dem Affen Donkey Kong zu retten. Die Spielfigur des Jumpman“, heute besser bekannt als Mario, konnte nun nicht mehr
”
nur laufen und klettern, sondern auch springen. Wegen der Erweiterung der
Bewegungsm¨
oglichkeiten ums Springen wird dieses Spiel oftmals als der eigentliche Urvater des Plattformers bezeichnet.
Im Verlauf der folgenden Jahre wurden verschiedene Spiele ver¨offentlicht,
die das neue Genre um interessante Aspekte erweiterten.
Mit Pitfall!“ [41] aus dem Jahr 1982 kam das Sidescrolling hinzu. Die Spiel”
figur wurde seitlich betrachtet und wurde von der linken Seite des Spielbereiches zur rechten gesteuert. Am Ende angekommen wurden nun nicht mehr
die Grafiken der einzelnen Spielbereiche neu geladen, sondern es wurde der
Spielbereichausschnitt in den n¨achsten Spielbereich gerollt“.
”
Ein anderer Aspekt, der hinzukam, war die Ver¨anderung im Spielverhalten.
So kam 1985 mit Super Mario Bros“ die Gr¨oßenver¨anderung hinzu, sobald
”
ein Pilz oder eine Feuerblume aufsammelte wurde. Damit einher ging auch,
dass die Spielfigur nun neue F¨ahigkeiten aufwies. Nach Konsum eines Pilzes
3
2.2
Definition
Madlen Thaleiser
wuchs Mario und konnte Bl¨ocke zerst¨oren. Nahm Mario die Feuerblumme
auf, wuchs er ebenfalls und konnte zudem noch Feuerb¨alle schießen.
Bei dem 1990 herausgebrachten Sonic the Hedgehog“ [38] wurde der Spielfi”
gur das Verhalten hinzugef¨
ugt, eingesammelte Ringe fallen zu lassen, sobald
sie von einem Feind getroffen wurde.
Die klassische zweidimensionale Ebene wurde schließlich 1996 mit Mario 64“
”
[37] in den dreidimensionalen Raum geholt. Nun war es innerhalb eines
großen Spielbereiches m¨
oglich, M¨
unzen und Sterne zu sammeln.
Aufgrund u. a. dieser Meilensteine innerhalb des Plattformer-Genres erfreuen sich Plattformerspiele einer großen Beliebtheit. Dabei ist es egal, ob es
sich um eine Neuauflage eines Klassikers, einen neuen Teil der Spielreihe oder
gar ein ganz neues Spiel in Anlehnung an die klassischen Plattformerspiele
handelt.
2.2
Definition
In der Literatur lassen sich untschiedliche Definitionen zum Begriff des Plattformers finden. So hat Wolf folgendes zur Begrifflichkeit des Plattfomers
festgehalten:
Games in which the primary objective requires movement through
”
a series of levels, by way of running, climbing, jumping, and other
means of locomotion.“ [13, S. 270]
¨
Ahnlich
charakterisiert auch Koster das Genre:
Platform games: any of a broad class of games where you att”
empt to traverse a landscape collecting objects or touching every
space on the map.“ [15, S. 249]
Beide Definitionen beschreiben den Begriff auf unterschiedliche Weise. So
geht Wolf auf die unterschiedlichen Bewegungsm¨oglichkeiten ein, die zum
Durchqueren eines Levels verwendet werden. Koster hingegen beschreibt die
Zielsetzung des Spieles, welche sich nicht nur auf das Einsammeln von Gegenst¨
anden bezieht, sondern auch auf die Erkundung des Levels.
In beiden Definitionen fehlt jeweils der andere betrachtete Aspekt. Bei beiden Definitionen fehlen jedoch noch weitere Gesichtspunkte, die einen Plattformer ausmachen.
So stehen nur eine begrenzte Anzahl an Versuchen in Form von Leben zur
Verf¨
ugung, um Level zu absolvieren. Diese Leben werden jedoch reduziert,
wenn die Spielfigur versehentlich einen Gegner ber¨
uhrt oder durch eine L¨
ucke
hindurchf¨
allt. Jedoch kann durch das Einsammeln von Sammelobjekten die
Anzahl der Versuche erh¨
oht werden.
4
2.3
Bestandteile eines Plattformers
Madlen Thaleiser
Des Weiteren fehlt die Abgrenzung, wann das Spiel beendet ist. Das Spiel
ist entweder beendet, wenn keine Versuche mehr vorhanden sind oder, wenn
alle Level erfolgreich durchquert worden sind.
Deshalb komme ich zu dieser Definition:
Ein Plattformer ist ein Spiel, bei dem die Spielfigur mittels Laufen und Springen Level durchquert und dabei mit Spr¨
ungen Hindernissen wie zum Beispiel L¨
ucken oder Feinde u
¨berwindet.
Hierf¨
ur stehen eine begrenzte Anzahl an Versuchen zur Verf¨
ugung, die durch das Sammeln von bestimmten Objekten erh¨
oht
werden k¨
onnen. Durch das versehentliche Ber¨
uhren von Feinden
oder das Fallen durch eine L¨
ucken verringert sich die die Anzahl
der Versuche.
Das Spiel ist beendet, wenn keine Versuche mehr zur Verf¨
ugung
stehen oder alle Level erfolgreich durchquert wurden.
Wird die obige Definition mit Spielen wie zum Beispiel Super Mario Bros“
”
verglichen, l¨
asst sich im Allgemeinen sagen, dass der obige Versuch einer
Definition dem Begriff des Plattformers1 in seinen wesentlichen Merkmalen
gut beschreibt.
Jedoch ist es unerheblich, welche Definition zugrunde gelegt wird, die Gemeinsamkeiten aller sind, dass es dem Spieler m¨oglich sein soll, das Levelgebiet mittels der Bewegungsm¨oglichkeiten des Laufens und Springens zu
durchqueren und dabei Hindernissen auszuweichen bzw. diese zu eliminieren.
2.3
Bestandteile eines Plattformers
Um einen Plattformer zu gestalten, der die aufgef¨
uhrten Merkmale aufweist,
m¨
ussen verschiedene Spielelemente ber¨
ucksichtigt werden. Bei der Analyse
von verschiedenen Spielen kristallisiert sich eine Gruppe von Spielelementen
heraus, die f¨
ur die Gestaltung eines Spieles und das Leveldesign wichtig sind.
Die folgende Auflistung ist an Smith et al. [12] angelehnt:
2.3.1
Spielfigur
Die Spielfigur ist die Repr¨
asentation des Spielers innerhalb des Spieles. Sie
weist die wichtigen Bewegungsmerkmale des Laufens und Springens auf.
Beim Laufen kommt es in verschiedenen Plattformern noch zu einer Beschleunigung der Figur bei l¨angerem Halten der Bewegungstaste oder beim
1
Plattformer werden auch auf Grund der Bewegungsm¨
oglichkeiten des Springens und
des Laufens als Jump’n’Run bezeichnet.
5
2.3
Bestandteile eines Plattformers
Madlen Thaleiser
zus¨
atzlichen Dr¨
ucken einer vorher definierten zweiten Taste. Dies erm¨oglicht dem Spieler zum Beispiel u
¨ber eine Reihe von Plattformen mit kleinen
L¨
ucken zu laufen ohne herunterzufallen.
In anderen Spielen kann es beim Springen noch zu Variationen kommen.
Dabei k¨
onnte die Sprungweite durch das l¨angere Dr¨
ucken erh¨oht werden.
Eine andere M¨
oglichkeit w¨
are, durch mehrfaches Dr¨
ucken der Sprungtaste
(ggf. in Kombination mit anderen Tasten) verschiedene Spr¨
unge, zum Beispiel einen Doppelsprung, zu kreieren. Daher spielen die Eigenschaften der
Spielfigur eine erhebliche Rolle beim Design von Leveln.
Neben den Grundeigenschaften des Laufens und Springens besitzt die Spielfigur zumeist noch verschiedene Stadien, die sie annehmen kann und in denen
sie neue Eigenschaften erh¨
alt. Ob und in welchem Stadium sich die Figur
befindet, h¨
angt davon ab, ob sie Power-ups2 gesammelt hat und welche das
waren.
So besitzt Mario in Super Mario Bros“ drei Stadien: kleiner Mario, großer
”
Mario und Feuermario.
2.3.2
Plattformen
Der Begriff Plattform definiert nicht nur das Genre, sondern ist ein wesentliches Spielelement und umfasst alle Oberfl¨achen, auf denen sich die Spielfigur
sicher bewegen kann.
Jede Plattform hat zudem physikalische Eigenschaften: einen Reibungskoeffizienten, eine Gr¨
oße und einen Steilheitsgrad. Diese Werte k¨onnen vom
Leveldesigner beliebig gesetzt werden, so dass die Gestaltung eines Weges
mit unterschiedlich gewichteten Plattformen bereits interessant f¨
ur den Spieler sein kann.
2.3.3
Hindernisse
Als Hindernis werden alle Elemente innerhalb des Spieles bezeichnet, die
den Bewegungsablauf st¨
oren bzw. beeintr¨achtigen und ggf. der Spielfigur
schaden.
Daher ist es nicht verwunderlich, dass s¨amtliche Gegnertypen unter diesen
Begriff fallen. Es gibt Gegner, die get¨otet werden m¨
ussen(z. B. Gumbas3 ),
solche, denen man ausweichen muss (z. B. Muncher4 ) und schließlich solche,
bei denen der richtige Zeitpunkt zum Durchqueren abgewartet werden muss
(z. B. Thwomp5 ).
2
Ein Power-up bezeichnet ein Objekt, das die Spielfigur durch einfache Ber¨
uhrung
aufnehmen kann und das die Figur mit besonderen F¨
ahigkeiten ausstattet.
3
Gumbas sind kleine braune Wesen, die der Spielfigur bei Kontakt schaden und durch
einen einfachen Sprung auf den Kopf get¨
otet werden k¨
onnen.
4
Muncher sind kleine schwarze Pflanzen, die der Spielfigur bei Kontakt schaden und
nicht zerst¨
orbar sind.
5
Thwomps sind herabfallende Steine, die der Spielfigur bei Kontakt schaden.
6
2.4
Unterscheidung 2D- zu 3D-Plattformer
Madlen Thaleiser
Neben Gegnern z¨
ahlen auch L¨
ucken und sich bewegende Plattformen dazu.
Um diese verschiedenen Hindernisse zu absolvieren, muss der Spieler auf
diese reagieren, in dem er ihnen entweder ausweicht oder, sofern m¨oglich, sie
aus dem Spiel nimmt (z. B. durch Sprung auf den Kopf des Gegners).
2.3.4
Sammelobjekte
Fast alle Plattformer besitzen ein Belohnungssystem, welches meist aus dem
Sammeln von Sammelobjekten besteht. Dabei k¨onnen dies M¨
unzen, Sterne,
Ringe, Power-ups oder andere Elemente sein, die dem Spieler einen kleinen
Vorteil zum Beispiel in Form von einem Extraleben bringen.
Diese Objekte nehmen innerhalb des Spieles die Funktion als Belohnung ein
oder weisen dem Spieler auf den Weg bzw. einen alternativen Weg hin.
2.3.5
Hilfsobjekte
Hilfsobjekte helfen dem Spieler ein Level zu absolvieren. Dabei wird zwischen
Bewegungshilfen und Levelhilfen unterschieden.
Bewegungshilfen sind Objekte, die dem Spieler neue M¨oglichkeiten in der
Bewegung durch das Level geben. Dazu geh¨oren Leitern, Seile, Sprungfedern
und bewegliche Trampoline.
Levelhilfen hingegen k¨
onnen Schalter oder a¨hnliche Objekte sein, die das Level modifizieren und zum Bew¨altigen optional gebraucht werden. Sie k¨onnen
auch dazu verwendet werden Plattformern eine R¨atselkomponente zu geben.
Dies k¨
onnte zum Beispiel das Dr¨
ucken von Schaltern in einer bestimmten
Reihenfolge sein.
2.3.6
Speicherpunkte
Speicherpunkte markieren Punkte innerhalb des Level, die den aktuellen
Levelfortschritt speichern und als Wiederbelebungspunkte (engl.: Respawnpoints) dienen, falls der Spieler ein Leben verliert.
Somit muss der Spieler beim Verlust eines Lebens nicht nochmal das gesamte Level bis zur Passage spielen, bei der er umgekommen ist, sondern
kann direkt bei der Ungl¨
ucksstelle starten und nochmals versuchen sie zu
bew¨
altigen.
2.4
Unterscheidung 2D- zu 3D-Plattformer
Im folgendem werden zwei Spiele aus der Mario-Reihe betrachtet, um die
jeweiligen Merkmale des zwei- bzw. dreidimensionalen Raumes herauszuarbeiten. Dabei wird Wert auf die Punkte Weg/Spielwelt, Kamera, Ziele und
Sprungr¨
atsel6 gelegt.
6
Sprungr¨
atsel stellen das Absolvieren einer Sprungpassage in einer bestimmten Reihenfolge da.
7
2.4
Unterscheidung 2D- zu 3D-Plattformer
Madlen Thaleiser
2.4.1
Super Mario Bros“ als Beispiel fu
¨ r 2D-Plattformer
”
In einer zweidimensionalen Spielwelt ist es Marios Aufgabe, die Level mittels
Laufen und Springen zu durchqueren. Der Weg dabei ist im wesentlichen vorgegeben und mit verschiedenen Hindernissen versehen. Diese Passagen gilt
es mit gut gesetzten Spr¨
ungen zu absolvieren, um ans Ende des Levels zu
gelangen. Hierbei werden die Aktionen mittels Sidescrolling in einer Seitenansicht verfolgt, weshalb das L¨osen von Sprungr¨atseln recht einfach ist.
2.4.2
Mario 64“ als Beispiel fu
¨ r 3D-Plattformer
”
Mit Ver¨
offentlichung von Mario 64“ [37] wird die Spielwelt in den dreidi”
mensionalen Raum geholt. Mario wird in einer offenen Spielwelt gesteuert
und folgt nicht mehr nur einen linearen Weg, der zum Ende vom Level f¨
uhrt.
Stattdessen sollen nun verschiedenste Ziele erf¨
ullt werden. Dadurch werden
Level gr¨
oßer. Das Absch¨
atzen von Spr¨
ungen macht das L¨osen von Sprungr¨
atseln schwieriger, da nun auch eine freie Kamera vorhanden ist, die das
Spielgeschehen zeigt und richtig positioniert werden muss.
Spiel
Super Mario Bros
Mario 64
Weg/Spielwelt
feste Spielwelt,
lineare Wege
offene Spielwelt,
komplexe Wege
Kamera
Ziele
fixe Seitenansicht
Absolvierung des Levels
freie Kamera
Absolvierung des Levels,
mehrere objektbezogene
Ziele
Spr¨
unge
gut absch¨atzbar,
einfache Passagen
schlecht absch¨atzbar,
komplexe Passagen
Tabelle 1: Zusammenfassung Unterschied 2D- zu 3D-Plattformern
2.4.3
Fazit aus dem Vergleich
Aufgrund der großen Unterschiede in den betrachteten Punkten (vgl. Tabelle 1) muss eine Beschr¨
ankung auf eine der beiden Dimensionen f¨
ur das
Leveldesign erfolgen. Es gibt aber auch Spiele, wie Donald Duck Quack At”
tack“ [36], die beide Dimensionen verwenden, in dem sie zweidimensionale
und dreidimensionale Level abwechselnd aneinanderreihen.
Jedoch wird sich diese Arbeit auf das Genre des 2D-Plattformers beschr¨anken.
8
3 Prozedurale Generierung
3
Madlen Thaleiser
Prozedurale Generierung
3.1
Definition
Prozedurale Generierung von Inhalten und besonders von Spielinhalten ist
noch ein sehr junges Forschungsgebiet, das dennoch bereits sehr umfangreich
ist. Es existiert schon eine Vielzahl an wissenschaftlichen Arbeiten, die sich
mit einzelnen Aspekten auseinandersetzen.
Dahlskog und Togelius beschreiben prozedurale Generierung von Spielinhalten wie folgt:
Procedural content generation in digital games refers to the
”
automated or semi-automated creation of game content using
algorithms.“ [3, Section 1: Introduction]
Eine andere Definition findet sich bei Hendrikx et al.:
In contrast to manual content production, Procedural Content
”
Generation for Games (PCG-G) is the application of computers to generate game content, distinguish interesting instances
among the ones generated, and select entertaining instances on
behalf of the players.“ [2, Section 1: Introduction]
Da die prozedurale Generierung sich auf viele Gebiete (zum Beispiel die
Erzeugung von Texturen oder das Erzeugen von Verhalten einer nicht spielbaren Spielfigur) erstreckt, kann eine einheitliche Definition nicht bestimmt
werden. Jedoch herrscht Einigkeit u
¨ber einen wesentlichen Aspekt:
Durch eindeutig definierte Algorithmen sollen Inhalte automatisch am Computer erstellt werden und den Einsatz manueller Arbeit, die sonst diese Inhalte produzieren w¨
urde, verringern bzw. ersetzen.
In den folgenden Abschnitten werden zun¨achst die g¨angigen Methoden beschrieben und anschließend die Anwendungsgebiete der prozeduralen Generierung von Spieleinhalten erl¨autert.
3.2
Methoden
Auch wenn verschiedene Anwendung im Bereich der prozeduralen Generierung sich aufgrund der Anforderungen voneinander unterscheiden, kommen
jedoch mehrere Konzepte und Techniken wiederholt zum Einsatz. In den folgenden Abschnitten werden diese gem¨aß der Klassifizierung von Hendrikx
et al. [2] beschrieben.
3.2.1
Pseudozufallszahlengenerator
In der Natur scheint vieles zuf¨allig zu sein, wie zum Beispiel die Gestalt von
Wolken oder Blumen. Solche Zuf¨alle sollen mit Pseudozufallszahlgeneratoren
nachgebildet werden.
9
3.2
Methoden
Madlen Thaleiser
Durch deterministische Algorithmen werden Reihen von zuf¨alligen Zahlen
erzeugt. Diese Zahlenreihen sind jedoch reproduzierbar, sofern die Eingabe
gleich ist.
3.2.2
Generative Grammatiken
Generative Grammatiken bezeichnen einen bestimmtes Regelsystem, das alle
S¨
atze einer Sprache zusammen mit ihren Strukturen erzeugt. Dies geht auf
die Sprachstudien Noam Chomskys in den 1960er Jahren zur¨
uck.
Auf Grund dieses Regelsystems ist es m¨oglich, eine unbegrenzte Anzahl an
grammatikalisch richtigen S¨
atzen zu bilden. In der prozeduralen Inhaltsgenerierung wurde dies u
¨bernommen. Anstelle von W¨orter stehen nun einzelne Elemente, die zum Beispiel B¨aume erzeugen. Ein bekannte Grammatik,
die zu den generativen Grammatiken geh¨ort, stellt das Lindenmayer-System
da[18, 17]. Bei diesem System werden Einzelteile eines Objektes sukzessiv
durch Produktionsregeln ersetzt.
3.2.3
Bildfilter
Mittels eines Bildfilters sollen wesentliche Merkmale von Bildern verst¨arkt
bzw. herausgearbeitet werden. Dies wird vorwiegend in der prozeduralen
Erzeugung von Texturen verwendet. Durch bin¨are Morphologie oder Konvolutionsfilter werden die gew¨
unschten Ergebnisse erzeugt.
Bei der bin¨
aren Morphologie werden Bilder in zwei Pixelwerten weiß und
schwarz dargestellt. Die dadurch entstandenen Schwarz-Weiß-Bilder werden
als Mengen interpretiert, wodurch die Anwendung von Mengenoperationen
wie zum Beispiel Vereinigung und Schnitt m¨oglich ist. So k¨onnen durch eine
¨
Abfolge von Mengenoperationen Offnungen
im Bild verst¨arkt oder geschloßen werden.
Die Konvolutionsfilter berechnen jedes Pixel eines Bildes mittels einer Kernelfunktion. Dabei k¨
onnen durch verschiedene Kernelfunktionen verschiedene Ergebnisse erzielt werden. Mit dem Sobel-Operator als Kernelfunktion
zum Beispiel k¨
onnen Kanten erkannt werden.
3.2.4
R¨
aumliche Algorithmen
R¨
aumliche Algorithmen manipulieren einen gegebenen Raum, um Inhalte
zu generieren. Dabei werden mit Struktur als Eingabeparameter dementsprechende Ausgaben erzeugt. Besonders das Aufteilen des Raumes in ein
Kachelraster mit anschließender Unterteilung in Schichten findet innerhalb
vom 2D-Bereich Anwendung, um die Illusion von 3D-Karten zu erzeugen.
Eine andere r¨
aumliche Methode ist die Rasterteilaufteilung, bei der Objekte
in immer feiner werdene Raster aufgeteilt werden, wenn zum Beispiel hineingezoomt wird. Dadurch werden immer mehr Details erzeugt. So werden
10
3.3
Anwendungsgebiete
Madlen Thaleiser
in einem generierten Gel¨
ande nur Bereiche in der N¨ahe des Spieler detailliert
dargestellt, wohingegen das restliche Gebiet grob gerendert bleibt.
3.2.5
Modellierung und Simulation von komplexen Systemen
Mit dieser Methode sollen nat¨
urliche Ph¨anom¨ene erzeugt werden, da dies
mit mathematisch Methoden in einigen F¨allen nicht m¨oglich ist. Eine Technik ist dabei das Modell des zellul¨aren Automaten. Hierbei wird ein Netz aus
Zellen gebildet, die jeweils einen anderen Zustand annehmen k¨onnen. Zudem
werden Regeln festgelegt, nach der sich die Zellen verhalten sollen. In welchem Zustand die Zelle sich befindet, wird dadurch beeinflusst, in welcher
Nachbarschaft sich die Zelle befindet, welchen aktuellen Zustand die Zelle
hat und welche Regeln zu befolgen sind.
Die agentenbasierte Simulation ist eine weitere Methode zur Modellierung
und Simulation von komplexen Systemen. Dabei wird eine komplexe Situation mittels Individuen, den Agenten, simuliert. Die Agenten sind dabei
einfach gehalten in ihrem Verhalten, jedoch durch Interaktion miteinander
entstehen komplexe Abl¨
aufe. Durch Hinzuf¨
ugen von einfachen Regeln ist
eine Simulation von Spielgeschehen m¨oglich.
3.2.6
Ku
¨ nstliche Intelligenz
K¨
unstliche Intelligenz ist ein großes Forschungsgebiet innerhalb der Informatik. Ziel ist es dabei nat¨
urliche Intelligenz nachzubilden.
Mittels genetischer Algorithmen werden Optimierungsprobleme gel¨ost, indem die biologische Evolution nachgeahmt wird. Ein anderer Ansatz zum
L¨osen von Optimierungsproblemen sind neuronale Netzwerke. Nach einer
Lernphase k¨
onnen diese Netzwerke gerade verlangte Inhalte generieren und
gegebenenfalls die Generierung von zuk¨
unftigen Inhalten beeinflussen.
Das Constraint-Satisfaction-Problem stellt die Aufgabe, einen Zustand zu
finden, in dem alle vorgebenen Bedingungen erf¨
ullt wurden. Diese Aufgabe wird durch automatische Planung gel¨ost. Es werden Inhalte nur dann
erzeugt, wenn die Bedingungen zu einem geplanten Grad erf¨
ullt wurden.
3.3
Anwendungsgebiete
Im Folgenden werden die verschiedenen Anwendungsgebiete beschrieben,
in denen die prozedurale Generierung von Spieleinhalten bereits eingesetzt
wird. Dabei wird die Unterteilung von Hendrikx et al. [2] u
¨bernommen und
f¨
ur jedes Teilgebiet ein Beispiel angef¨
uhrt.
3.3.1
Spielbits
Spielbits sind die kleinsten Elemente eines Spieles, die den Spieler nicht
direkt beeinflussen. Dazu z¨
ahlen Texturen, Sounds, Vegetation, Geb¨aude,
11
3.3
Anwendungsgebiete
Madlen Thaleiser
einfaches Verhalten sowie nat¨
urliche Partikelsysteme (Feuer, Wasser, Steine
und Wolken).
Texturen k¨
onnen zum Beispiel mittels Pseudozufallszahlengeneratoren erzeugt werden. Diese werden in Rauschfunktionen wie Perlin-Noise7 verwendet, um Muster zum Beispiel f¨
ur Holz zu erzeugen.
Eine anderes Beispiel f¨
ur die prozedurale Generierung von Spielebits ist die
Erzeugung von Vegetation. Verwendete Methoden sind dabei die generativen
Grammatiken, r¨
aumliche Algorithmen sowie die Modellierung und Simulation von komplexen Systemen. Ein bekanntes und oft verwendetes Beispiel
ist die kommerzielle Software SpeedTree [47]. In Spielen wie zum Beispiel
The Witcher 3: Wild Hunt“ [29] oder auch in Filmen wie Avatar“ [45] wird
”
”
SpeedTree verwendet (siehe Abbildung 1).
(a) Szene aus Witcher 3: Wild Hunt“
”
(b) Szene aus Avatar“
”
Abbildung 1: Anwendungsbeispiele f¨
ur SpeedTree
(Quelle: SpeedTree.22slides.com [26, 25])
3.3.2
Spielraum
Als Spielraum wird der Raum bezeichnet, in dem das Spiel stattfindet. Zu
dieser Kategorie geh¨
oren Karten f¨
ur drinnen und draußen sowie Wasserelemente einer Karte (zum Beispiel Fl¨
usse).
Clyde [22] hat mittels Modellierung und Simulation von komplexen Systemen die Erzeugung von richtigen Wasserfluss sowie Wassererosion gezeigt.
3.3.3
Spielsystem
Ein Spielsystem kann als Interaktion von Spielraum und Spielbits verstanden werden. So wird zum Beispiel die Beziehung zwischen Vegetation und
Außenkarten definiert und generiert. Mit generativen Grammatiken, Pseudozufallsnummergeneratoren sowie Modellierung und Simulation von kom¨
plexen Systemen k¨
onnen Okosysteme,
Straßennetzwerke, Stadtgebiete und
Einheitsverhalten erzeugt werden.
7
Perlin-Noise wurde 1982 von Ken Perlin entwickelt und ist eine fraktale Rauschfunktion auf Basis von pseudozuf¨
alligen Gradientwerten [24]
12
3.3
Anwendungsgebiete
Madlen Thaleiser
Mateas und Stern [16] haben mit Facade“ eine Fallstudie f¨
ur Einheitsver”
halten gestaltet. Innerhalb der Anwendung reagieren zwei Charaktere auf
das Verhalten des Spielers und so wird innerhalb eines Aktes ein Drama
erz¨
ahlt.
3.3.4
Spielszenarien
Die Ordnung bzw. der Weg, wie ein Spiel und dessen Events ablaufen sollen,
wird als Spielszenario bezeichnet. Darunter fallen R¨atsel, Storyboards8 , Storys und Level. Diese werden mit Pseudozufallsgeneratoren und generativen
Grammatiken erzeugt.
Eine Grundlage f¨
ur die Erzeugung von Geschichten stellt die Arbeit von
Propp [19] dar. Er analysierte hunderte von russischen Volksm¨archen und
stellte fest, dass diese eine feste Handlungsstruktur haben und sich in Erz¨
ahleinheiten einteilen lassen. The Fairy Tale Generator“ [23] der Brown
”
University kann so nach Auswahl der Erz¨ahleinheiten eine Geschichte generieren. Ein Beispiel f¨
ur eine mittels des Generators erzeugte Geschichte in
Abbildung 2 zusehen.
Ans¨
atze f¨
ur die prozeduralen Levelgenerierung werden im Abschnitt 4 n¨aher
behandelt.
Abbildung 2: Fairy Tale Generator“ der Brown University
”
(Quelle: eigene Darstellung)
8
Storyboard ist die Abfolge einer Geschichte (engl. Story) in Einzelbildern und wird
meist im Bereich des Films zur Erl¨
auterung eines Drehbuches verwendet.
13
3.3
Anwendungsgebiete
3.3.5
Madlen Thaleiser
Spieldesign
Unter Spieldesign werden Inhalte verstanden, wie etwa Regeln und Ziele
¨
eines Spieles, die Dramaturgie, Asthetik
sowie das graphische Thema eines
Spieles. Diese Elemente k¨
onnen als Systemdesign oder als Weltdesign unter
anderem mittels Pseudozufallsgeneratoren erzeugt werden.
Hartsook et al. [6] diskutiert ein System, das unter Verwendung einer von
Menschen oder Computer generierten Geschichte eine Spielwelt erzeugt, so
dass ein 2D-Rollencomputerspiel entsteht.
3.3.6
Abgeleitete Inhalte
Unter abgeleiteten Inhalten werden Inhalte verstanden, die w¨ahrend des
Spielens erzeugt und eingebunden werden. Dazu z¨ahlen News, Broadcasts
und Bestenlisten.
Chan et al. [11] entwickelten ein System, das automatisch die Spielerinteraktion mit der Welt in Form eines Comics zusammenfasst. Dabei werden
Screenshots und ein Spielerlog verwendet. Der Spieler kann aber auch die
Generation beeinflussen und selbst mittels eines Interfaces seine Spielmomente in einem Comic festhalten (siehe Abbildung 3).
Abbildung 3: Beispiel einer generierten Comicseite
(Quelle: Chan et al. [11])
14
3.4
Online- und Offline-Generierung
3.4
Madlen Thaleiser
Online- und Offline-Generierung
Eine wichtige Unterscheidung beim Einsatz der Generierungsmethoden ist,
ob Inhalte w¨
ahrend des Spieles oder w¨ahrend der Entwicklung des Spieles
eingesetzt werden sollen.
• Bei der Online-Generierung werden Inhalte, wie zum Beispiel Level,
zur Laufzeit erzeugt oder angepasst. Dadurch variieren die erzeugten
Inhalte meist, weshalb die Motivation steigt, das Spiel erneut zu spielen. Nicht alle Methoden aus Abschnitt 3.2 eignen sich f¨
ur die OnlineGenerierung, da manche zu komplex sind, in einer angemessen Zeit
Inhalte zur Laufzeit zu erzeugen.
• Sofern der Inhalt nach der Erzeugung nochmals kontrolliert oder modifiziert werden soll, wird die Offline-Generierung daf¨
ur verwendet.
Die erzeugten Inhalte werden vor dem Einsatz innerhalb eines Spieles
gepr¨
uft, ob sie spieltauglich sind und eingesetzt werden k¨onnen. Somit
k¨
onnen die Inhalte ggf. nochmals generiert oder angepasst werden. Alle
Methoden aus Abschnitt 3.2 eignen sich f¨
ur die Offline-Generierung.
3.5
3.5.1
Beispiele fu
¨ r prozedurale Generierung in Spielen
Civilization V
Im Strategiespiel Civilization V“ [33] ist es das Ziel, seine Zivilisation durch
”
Jahrhunderte zu f¨
uhren und eines der verschiedenen Siegziele zu erreichen.
Dabei kann das Spielgeschehen auf vorgefertigten Karten stattfinden. Jedoch hat der Spieler auch die M¨oglichkeit, Karten anhand von Parametern
generieren zu lassen.
Die Parameter Temperatur und Regen beeinflussen dabei zum Beispiel das
Erscheinungsbild der Karte. Wird die Temperatur mit heiß“ belegt, so er”
scheinen mehr Dschungelgebiete auf der Karte. Sollte dazu noch der Regenwert mit nass“ belegt sein, wird die Dschungeldichte zus¨atzlich erh¨oht. So
”
kann z. B. eine vorwiegend gr¨
une Karte erzeugt werden. Einen Einblick in
den Generierungsprozess gew¨ahrt der Grafikprogrammierer Kloetzli Jr. in
einem Entwicklerblog [20].
In diesem wird der Einsatz der prozeduralen Generierung bei der Gestaltung
einer Karte erl¨
autert. Dabei werden auf einer Karte Berge zuf¨allig erstellt.
Danach werden auf der Karte in Abh¨angigkeit zur Lage die Ressourcen
verteilt und die Karte in Hexagonfelder eingeteilt. Zudem werden K¨
usten
anhand vorgefertigter K¨
ustenelemente erzeugt, die anschließend durch Splinekurven9 ein nat¨
urliches Aussehen erhalten.
9
Splinekurven sind nummerische Funktionen, die st¨
uckweise durch Polynome definiert
werden.
15
3.5
Beispiele f¨
ur prozedurale Generierung in Spielen
(a) Optionen
Madlen Thaleiser
(b) Karte
Abbildung 4: Kartengenerierung in Civilization V“
”
(Quelle: eigene Darstellung)
3.5.2
Borderlands
Eine andere Anwendung von prozeduraler Generierung von Spielinhalten findet sich im Spiel Borderlands“ [34]. Innerhalb des Ego-Shooters mit Rollen”
spielelementen werden die Waffen sowie andere Ausr¨
ustungsgest¨ande mittels
Generatoren erstellt.
Aus einer Menge m¨
oglicher Bestandteile werden Einzelteile zuf¨allig ausgew¨
ahlt, die zusammen eine Waffe oder einen anderen Gegenstand bilden.
Durch die zuf¨
allige Auswahl unterscheiden sich die erzeugten Gegenst¨ande in ihrem Aussehen und in ihren Attributen, da die Bestandteile diese
Attribute beeinflussen.
Abbildung 5: zufallsgenerierte Waffe aus Borderlands“
”
(Quelle: eigene Darstellung)
16
3.5
Beispiele f¨
ur prozedurale Generierung in Spielen
3.5.3
Madlen Thaleiser
Rogue
Das Computerspiel Rogue“ [43] von 1980 ist eines der ersten Fantasy”
Rollenspiele, in dem der Spieler als Abenteuer einen Kerker erkunden muss.
Dieser Kerker wird prozedural generiert, indem R¨aume an zuf¨alligen Positionen mit unterschiedlicher Gr¨oße erstellt werden und mit ebenfalls zuf¨allig
generierten Korridoren verbunden werden.
Die Gegner und Sch¨
atze werden abschließend hinzugef¨
ugt.
Abbildung 6: generierter Kerker in ASCII des Spieles Rogue“
”
(Quelle: killscreen.daily.com [27])
17
4 Ans¨
atze im Bereich der Levelgenerierung
4
Madlen Thaleiser
Ans¨
atze im Bereich der Levelgenerierung
Die Generierung von Leveln, besonders f¨
ur 2D-Plattformer, ist ein beliebtes Thema in der prozeduralen Generierung von Spielinhalten. Bei der Generierung kommen verschiedene Techniken und Ans¨atze zum Einsatz, die
unterschiedliche Anforderungen stellen.
4.1
Erfahrungsgesteuerte Levelgenerierung
Die erfahrungsgesteuerte Levelgenerierung will Level auf Grundlage von
Spielerdaten generieren. Dabei werden oftmals neuronale Netze verwendet.
Polymorph“ von Jennings-Teats et al. [8] ist ein 2D-Plattformer, welcher ein
”
Level generiert und es dem Spielverhalten des Spielers w¨ahrend des Spielens
anpasst.
Hinter diesem dynamischen Anpassen steht ein mehrschichtiges Perzeptron10 .
Dieses lernt zun¨
achst offline, welche Levelelemente wie schwer sind. Dazu
werden im Vorfeld Daten gesammelt, indem rund 200 Spieler kleine Levelabschnitte spielen und die vorkommenden Levelelemente in ihrer Schwierigkeit
einstufen. Anhand dieser Daten stuft das neuronale Netz alle generierten
Levelelemente ein.
W¨
ahrend des Spielens stuft Polymorph“ das Spielverhalten ein und f¨
ur den
”
n¨
achsten Levelabschnitt werden anhand der Einstufung entsprechende Spielelemente gew¨
ahlt.
Ein anderer Ansatz im Bezug auf erfahrungsgesteuerte Levelgenerierung ist,
nicht das Level dem Spielverhalten anzupassen, sondern ein Level zu erzeugen, dass interessant und herausfordernd, jedoch wenig frustrierend ist.
Pedersen et al. [10] wollen dies ebenfalls mit einem neuronalen Netz erreichen, jedoch verwenden sie nur ein einzelnes Perzeptron. Pedersen et al.
haben zun¨
achst ebenfalls Daten gesammelt, die aber nun Informationen u
¨ber
die verwendeten L¨
ucken, vorkommenden Spielelemente und die Spielerlebnisse der Spieler beinhalten. Anhand dieser Daten werden drei Hauptmerkmale (Spaß, Frustration und Herausforderung) in Abh¨angigkeit zueinander
berechnet, wobei eine bestimmte Verteilung angestrebt wird. Bei dieser Verteilung sollen die Merkmale Spaß und Herausforderung hohe Werte annehmen und das Merkmal Frustration soll einen geringen Wert aufweisen.
Mit diesen Informationen wird bisher das Perzeptron trainiert. Als n¨achsten
Schritt wollen Pedersen et al. einen Generator auf Basis des Perzeptrons
entwickeln, der Level mit bestm¨oglichen Werten generiert.
4.2
Levelgenerierung mit genetischen Algorithmen
Genetische Algorithmen k¨
onnen auch f¨
ur die Generierung von Leveln eingesetzt werden. Ferreira et al. [1] nutzen dazu vier Populationen f¨
ur vier
10
Ein Perzeptron ist einfaches Netz aus k¨
unstlichen Neuronen.
18
4.2
Levelgenerierung mit genetischen Algorithmen
Madlen Thaleiser
Spielelemente (Boden, Bl¨
ocke, Feinde und M¨
unzen).
Als Eingabe f¨
ur die einzelnen Populationen wird jeweils ein Vektor mit einer
Kodierung der wichtigen Eigenschaften der jeweiligen Population verwendet.
Bei der Bodenpopulation wird beispielsweise ein Integervektor benutzt, der
u. a. die H¨
ohe der Bodenelemente speichert. Zudem hat jede dieser Population eine eigene Fitnessfunktion, die die Chancen und Brauchbarkeit f¨
ur die
Evolution bewertet.
W¨
ahrend der Evolutionsphase werden in den einzelnen Populationen mittels
Selektionen, Rekombination und Mutation neue Individuen erzeugt, die anschließend von der Fitnessfunktion bewertet werden. Dieser Prozess wiederholt sich u
¨ber mehrere Generationen. Nachdem die Evolution abgeschlossen
ist, werden die jeweils besten Elemente der vier Populationen f¨
ur die Levelgenerierung verwendet.
Mourato et al. [5] verwendeten ebenfalls einen genetischen Algorithmus. Bei
ihrer Arbeit ließen sie sich von dem Plattformer Prince of Persia“ [39] in”
spirieren. Zun¨
achst unterteilten sie die Spielszene in ein Raster, wobei sie
verschiedene Rastergr¨
oßen untersuchten.
Nachdem die Spielszene in ein Raster aufgeteilt wurde, wurde den einzelnen Zellen einer von drei m¨oglichen Zust¨anden (Boden, Wand oder leer)
zugeordnet. Anschließend wurde die Fitnessfunktion mittels verschiedener
Heuristiken berechnet. So wurden die Zellen zum Beispiel auf ihre Bedeutung im Bezug zur Lage und Zustand eingestuft.
Die folgende Evolution bezieht sich auf die Ergebnisse der Fitnessfunktion
und versucht mittels Mutation sowie Crossover neue Variationen zu schaffen,
damit sich der Wert der Fitnessfunktion verbessert.
Ist die Evolution beendet und ein guter Wert f¨
ur die Fitnessfunktion gefunden, durchl¨
auft das generierte Level einen Nachbereitungsprozess. In diesem
werden Fallen, Feinde und ¨
astethische Objekte hinzugef¨
ugt.
Abbildung 7: Generietes Level mit Raster
(Quelle: Mourato et al. [5])
19
4.3
4.3
Generierung auf Basis von Teill¨osungen
Madlen Thaleiser
Generierung auf Basis von Teill¨
osungen
Mit einer Bibliothek aus Teill¨osungen zur Generierung von Leveln befassen
sich Mawhorter und Mates [7]. Die Idee f¨
ur diesen Ansatz ist, dass Level
generiert werden sollen, ohne die Mechaniken des Spieles zu kennen.
Zun¨
achst wird eine Bibliothek aus typischen Levelst¨
ucken mit potentiellen
Ankerpositionen angelegt. Diese Ankerpositionen sind Punkte, die der Spieler beim Durchlaufen des Levels besetzen k¨onnte.
Nachdem eine Bibliothek angelegt ist, wird nun ein Startst¨
uck gew¨ahlt. Anhand der dazugeh¨
origen Ankerpositionen wird ein Rahmen bestimmt, anhand dessen die St¨
ucke der Bibliothek gefiltert werden. Aus dem Ergebnis
der Filterung wird mittels einer Auswahlfunktion das n¨achste Levelst¨
uck
bestimmt. Dieses wird nun ins Level gem¨aß der Ankerpositionen des vorhergehenden St¨
uckes integriert und ein neuer Rahmen anhand der Ankerpositionen des ausgew¨
ahlten St¨
uckes wird bestimmt, um den Ablauf zu wiederholen. Dies geschieht so lange, bis das Level die gew¨
unschte L¨ange oder Anzahl
an St¨
ucken erreicht hat. Das fertig generierte Level durchl¨auft im Anschluss
die Nachbearbeitung, in der Feinde, M¨
unzen u. a. positioniert werden, die
das Level komplettieren. Der Prozess wird in Abbildung 8 dargestellt.
Abbildung 8: Teill¨
osungen: Im oberen linken Abschnitt ist existierender Inhalt mit einem Anker dargestellt. Der obere rechte Abschnitt zeigt ein passendes Levelst¨
uck, basierend auf der vorhergehenden Filterung. Innerhalb
des unteren linken Bildes wird das passende Levelst¨
uck hinzugef¨
ugt und
der Anker als verwendet markiert. Das untere rechte Bild zeigt das ganze
Levelst¨
uck nach der Nachbearbeitung.
(Quelle: Mawhorter und Mates [7])
In Spelunky“ [35] wird prozedurale Levelgenerierung basierend auf Teill¨o”
sungen [21] angewendet. Als erstes wird das Level in ein Raster aus 16 R¨aumen aufgeteilt und anschließend wird ein Weg vom Levelanfang im obersten
Bereich zum Levelausgang im untersten Bereich erzeugt.
20
4.3
Generierung auf Basis von Teill¨osungen
Madlen Thaleiser
Nun wird jeder Raum aus einer Menge von Raumentw¨
urfen ausgew¨ahlt.
Welche Menge f¨
ur die Auswahl verwendet wird, ist abh¨anig davon, welche
Lage der Raum auf den Weg vom Eingang zum Ausgang hat. Um etwas Abwechslung in die R¨
aume zu bringen, werden nun einzelne zuf¨allig generierte
Bl¨
ocke hinzugef¨
ugt.
Abschließend werden Fallen, Sch¨atze, diverse Kreaturen u. a. hinzugef¨
ugt.
21
5 Rhythmusbasierte Levelgenerierung
5
Madlen Thaleiser
Rhythmusbasierte Levelgenerierung
5.1
Rhythmus als Ansatz
Compton und Mateas [14] ließen sich von den rhythmischen Strukturen afrikanischer Musik inspirieren. Sie sahen den Rhythmus und das damit verbundene Timing als einen zentralen Aspekt beim Design von Plattformerspielen.
Ein Rhythmus wird dabei als Abfolge von Bewegungsman¨over, z. B. laufen
und springen, verstanden.
Die bisherigen Levelgeneratoren, wie in Rogue“ [43], erzeugten Level durch
”
das zuf¨
allige Platzieren von Komponenten. Wurden die verwendeten Ans¨atze aus diesen Generatoren auf die Generierung von Plattformern u
¨bertragen, entstanden oft nichtspielbare Level. Durch den Rhythmusansatz als
Gestaltungsaspekt k¨
onnen einzelne Levelabschnitte, welche in der Arbeit von
Compton und Mateas als Muster beschrieben werden, so gestalten werden,
dass nach der Generierung ein spielbares Level entsteht.
Im Modell von Compton und Mateas wird zun¨achst eine Zellenstruktur erzeugt, welche den Verlauf des Levels bestimmt. Eine einzelne Zelle besteht
dabei aus mehreren Mustern, die verschiedene Komponentenreihenfolgen
aufweisen kann. Diese Reihenfolge wird anhand eines Rhythmus bestimmt
und erzeugt.
5.2
5.2.1
Der Levelgenerator Launchpad“ von Smith et al.
”
Rhythmus und Rhythmusgruppe
Smith et al. [9, 4]11 haben den Rhythmusansatz von Compton und Mateas als
Gestaltungsmittel f¨
ur Plattformerspiele u
¨bernommen. Der Rhythmus wird
als Grundlage f¨
ur die Erzeugung von Leveln genommen und ist nicht nur
ein Gestaltungsmittel f¨
ur eine bestehende Levelstruktur wie bei Compton
und Mateas. Sie haben den Rhythmusansatz verwendet, um einen Levelgenerator namens Launchpad“ f¨
ur 2D-Plattformer zu entwickeln. Statt einer
”
Zellenstruktur, die das Level beschreibt, wird der Rhythmus direkt zum Beschreiben des Levels verwendet.
Der Rhythmus wird dabei, wie in Abschnitt 5.1 beschrieben, als Reihe von
Aktionen verstanden, die notwendig sind, um ein Level zu absolvieren. Bei
Smith et al. beschr¨
anken sich die Aktionen auf die Bewegungsman¨over Laufen und Springen.
Durch die Beschreibung des Levels mittels eines Rhythmus ist das Level als
Aneinanderreihung von Rhythmusgruppen zu verstehen. Dabei beschreibt
der Begriff Rhythmusgruppe einen Satz von Levelkomponenten, welcher
einen herausfordernden Bereich zusammenfasst und auf Grundlage des Rhythmus gestaltet ist.
11
Die folgenden Ausf¨
uhrungen in den Kapitel 5 und 6 beziehen sich auf Smith et al. [9, 4]
22
5.2
Der Levelgenerator Launchpad“ von Smith et al.
”
5.2.2
Madlen Thaleiser
Struktur des Generators
Der Generator besteht aus mehreren Abschnitten, welche in Abbildung 9
dargestellt sind. Zun¨
achst werden in zwei Stufen die Rhythmusgruppen generiert. In der ersten Stufe wird der Rhythmus erstellt, der eine Reihe von
Bewegungsaktionen des Spielers darstellt. Anschließend wird der Rhythmus
in der zweiten Stufe mittels der Grammatik in mehrere Rhythmusgruppen
umgewandelt.
Nach der Generierung von Rhythmusgruppen werden diese aneinandergereiht und bilden Kandidatenlevel. Diese Kandidatenlevel werden nun auf
bestimmte Kriterien getestet. Es wird das Kandidatenlevel als Basislevel
ausgew¨
ahlt, das am besten den Kriterien gerecht wird. Im letzten Schritt
werden dem Level noch Sammelgegenst¨ande wie zum Beispiel M¨
unzen hinzugef¨
ugt.
Abbildung 9: Aufbau des Generators Launchpad“
”
(Quelle: Smith et al. [4])
5.2.3
Generierung von Rhythmusgruppen
Innerhalb des ersten Teiles des Generators wird ein Rhythmus erzeugt. Dieser wird durch drei Eigenschaften bestimmt:
23
5.2
Der Levelgenerator Launchpad“ von Smith et al.
”
Madlen Thaleiser
• L¨
ange (engl.: length) des Rhythmus: kann 5, 10, 15 oder 20 Sekunden
betragen.
• Typ (engl.: type) des Rhythmus: bestimmt, in welcher Abfolge Spr¨
unge vorkommen sollen:
– swing (zwei Spr¨
unge folgen direkt nacheinander)
– regular (Spr¨
unge treten in regelm¨aßigen Abst¨anden auf)
– random (zuf¨
allige Aneinanderreihung von Spr¨
ungen)
• Dichte (engl.: density) des Rhythmus: bestimmt, in welcher H¨aufigkeit
Spr¨
unge innerhalb des Rhythmus vorkommen und kann low (geringe
Anzahl an Spr¨
ungen), medium (moderate Anzahl an Spr¨
ungen) oder
high (hohe Anzahl an Spr¨
ungen) annehmen.
Nachdem die Eigenschaften festgelegt wurden, wird der Rhythmus erzeugt.
Die einzelnen Takte des Rhythmus stellen Bewegungsman¨over dar, wobei
zwei zur Auswahl stehen: laufen und springen. Jeder einzelne Takt und seine dazugeh¨
orige Aktion werden mittels der Grammatik (vgl. Abbildung 10)
in eine Komponente u
¨bersetzt. Der gesamte Rhythmus als Reihe von Komponenten stellt nun die Rhythmusgruppe dar. Es werden nun im Folgendem
Rhythmusgruppen aneinandergereiht, um ein Kandidatenlevel zu bilden.
Abbildung 10: Grammatik f¨
ur Komponentenerstellung
(Quelle: Smith et al. [4])
24
5.2
Der Levelgenerator Launchpad“ von Smith et al.
”
5.2.4
Madlen Thaleiser
¨
Uberpr
u
¨ fung durch Kriterien
Die entstandenen Kandidatenlevel m¨
ussen nun gegen zwei Kriterien getestet
werden. Dabei ist es dem Spielentwickler u
¨berlassen, welche Wertigkeit die
Kriterien haben.
1. Liniendistanzkriterium: kontrolliert das Kandidatenlevel dahingehend, wie weit die einzelnen Komponenten von einer vorgegebenen
Linie entfernt sind. Damit sollen Level erzeugt werden, die keine extremen Variation der Komponenten auf der y-Achse aufweisen. Die
Linie, welche Grundlage ist, wird vom Spielentwickler gew¨ahlt und
Beginn sowie Ziel des Levels sollten auf dieser Linie liegen. Es wird
dabei nach dem Level gesucht, welches den geringsten Abstand zwischen allen Endpunkten der Plattformen und der Linie besitzt.
2. Kombinierungskriterium: u
uft, wie h¨aufig Komponenten in¨berpr¨
nerhalb des Levels vorkommen. Dabei kann der Spielentwickler festlegen, welche H¨
aufigkeit die einzelnen Komponenten haben sollen. Um
zu ermitteln, inwiefern die auftretenden Komponenten dem gerecht
werden, wird die Chi-Quadrat-Anpassungsg¨
ute verwendet. Hierbei wird
die Differenz zwischen der beobachteten (O) und der erwarteten (E)
H¨
aufigkeit gebildet und anschließend quadriert. Das Quadrat wird
durch die erwartete H¨
aufigkeit geteilt. Alle Ergebnisse werden schließlich aufsummiert:
x2 =
X (O − E)2
E
(1)
Es wird das Level ausgew¨ahlt, das den kleinsten Testwert hat.
Das Kandidatenlevel, welches die besten Ergebnisse in beiden Kriterien aufweist, wird als Basislevel ausgew¨ahlt.
5.2.5
Nachbereitung
Innerhalb des Nachbereitungsprozesses wird das ausgew¨ahlte Basislevel mit
Sammelobjekten, z. B. M¨
unzen, versehen. Diese werden anhand von zwei
Regeln platziert:
1. Eine Gruppe soll entlang einer langen Plattform angeordnet werden,
wenn keine andere Aktion als Laufen mit dieser verbunden ist.
2. Sammelobjekte sollen als Belohnung f¨
ur einen risikoreichen Sprung
u
ucke positioniert werden. Anhand der H¨ohe soll der Spieler
¨ber eine L¨
die Spr¨
ungeh¨
ohe bestimmen k¨onnen.
Hat das Basislevel die Nachbereitung durchlaufen, ist es fertig generiert und
kann gespielt werden.
25
5.3
Implementierung des Levelgenerators
5.2.6
Madlen Thaleiser
Verwendete Methoden der prozeduralen Generierung
Smith et al. verwendeten zwei Methoden aus Abschnitt 3.2:
1. die generative Grammatik (vgl. Abschnitt 3.2.2)
2. das Constraint-Satisfaction-Problem (vgl. Abschnitt 3.2.6)
Die Grammatik, welche in Abbildung 10 zu sehen ist, erzeugt f¨
ur einen gew¨
ahlten Rhythmus eine Rhythmusgruppe. Dabei ist jeder Takt vergleichbar
mit einer Satzkomponente, die hierbei als eine der beiden Aktionen, laufen und springen, interpretiert wird. Die erzeugte Rhythmusgruppe stellt im
u
ur die Gram¨bertragendem Sinne einen richtigen grammatikalischen Satz f¨
matik von Smith et al. dar.
Die beiden Kriterien sind f¨
ur das L¨osen des Constraint-Satisfaction-Problems
zust¨
andig. Dadurch wird ein Kandidatenlevel als Basislevel erst erzeugt,
wenn das Kandidatenlevel diesen Kriterien am besten gerecht wird.
5.3
Implementierung des Levelgenerators
Es wird im Folgendem die Implementierung des Levelgenerators in Form
des Plattformerspieles Kitty’s Adventure“ betrachtet. Dabei wird auf die
”
im Abschnitt 5.2 beschriebenen einzelnen Phasen der Levelgenerierung eingegangen.
5.3.1
Allgemeine Anmerkungen
Die Umsetzung des Generators von Smith et al. wurde mittels der Unity 3D
Engine [46] in der Programmiersprache C# realisiert.
Aufgrund der einfachen Bedingung des Unity 3D Editors, der umfangreichen
Funktionalit¨
at und des bestehenden Vorwissen eignete sich die Spielengine
f¨
ur die Realisierung und die sp¨atere Erweiterung des Generators.
Unity 3D ist zwar vorwiegend eine 3D-Engine, jedoch ist es m¨oglich mit
der orthografischen Kamera auch 2D-Spiele zu entwickeln. Das integrierte
2D-Toolset kommt in dieser Arbeit nur in einzelnen F¨allen zur Anwendung
(zum Beispiel bei der Gestaltung der Spielfigur Kitty).
5.3.2
Programmaufbau
Abbildung 11 zeigt die grundlegenden Klassen, die im Folgendem kurz erl¨autert werden:
• GameManger: ist das zentrale Verwaltungselement des Spieles. Die
Anzahl der Leben sowie die Anzahl der gesammelten M¨
unzen werden
von ihm verwaltet.
26
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
• GeneratorMenu: erlaubt es dem Spieler, Werte f¨
ur die Parameter
(type, length und density) des Rhythmus festzulegen. Im Anschluss
werden die gew¨
ahlten Werte an die Klasse GeneratorManager weitergeleitet.
• GeneratorManager: ist f¨
ur die Erstellung des Levels zust¨andig. Dabei werden die Parameterwerte aus dem GeneratorMenu verwendet,
um mit Hilfe der Klassen Critics und Rhythm eine Aneinanderreihung
von Rhythmusgruppen zu erzeugen.
• Rhythm: erh¨
alt bei der Instanziierung durch den GeneratorManager
die Werte f¨
ur die Rhythmuseigenschaften und generiert daraus einen
Rhythmus. Dieser wird an den GeneratorManager durch den Aufruf
einer Objektmethode der Rhythm-Klasse zur¨
uck gegeben, damit im
weiteren Verlauf Rhythmusgruppen gebildet werden k¨onnen.
• Critics: bekommt als Parameter w¨ahrend der Instanziierung vom GeneratorManager den generierten Rhythmus und erzeugt ein Integerarray, welches das komplette Level in kodierter Form darstellt. Bei der
Erzeugung wird das potentielle Levelarray auf das Liniendistanz- und
das Kombinierungskriterium gepr¨
uft, welche im Abschnitt 5.2.4 beschrieben wurden. Durch den Aufruf einer Objektmethode der CriticsKlasse erh¨
alt der GeneratorMangager das erzeugte Levelarray.
• Enemy, Stomper, etc.: sind Verhaltensklassen einzelner Bestandteile des GeneratorManagers und werden aufgerufen, wenn entsprechende
Levelkomponenten generiert werden.
• PlayerController: definiert das Verhalten der Spielerfigur Kitty und
die physikalischen Eigenschaften wie Sprungh¨ohe oder Laufgeschwindigkeit. Zudem werden s¨amtliche Interaktionsm¨oglichkeiten mit der
Spielwelt behandelt.
• PlayerCamera: bestimmt das Verhalten der Kamera. Diese verfolgt
die Spielfigur und zeigt den aktuellen orthografischen Spielauschnitt
aus der Spielwelt.
27
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
Abbildung 11: Die zentralen Klassen des Levelgenerators
(Quelle: eigene Darstellung)
5.3.3
Rhythmus und Rhythmusgruppe
Bei der Realisierung des Rhythmus und damit verbunden der Rhythmusgruppe wurde sich bei der Eigenschaft Typ auf die beiden Typen swing und
regular beschr¨
ankt. Dies soll bei der sp¨ateren Implementierung von Multiwegen das Erkennen des Rhythmustyps vereinfachen und somit die Ausf¨
uhrung
der richtigen Bewegungsman¨
over ohne Versuch und Irrtum erm¨oglichen.
Die Eigenschaften des Rhythmus werden im Generatormen¨
u (siehe Abbildung 12) festgelegt und anschließend mithilfe der PlayerPrefs 12 gespeichert,
so dass der GeneratorMangager darauf zugreifen kann.
12
PlayerPrefs ist eine von Unity bereitgestellte Funktion, die es erm¨
oglicht, Daten zwischen einzelnen Szenen und einzelnen Spielsitzungen zu speichern.
28
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
Abbildung 12: Generatormen¨
u in Kitty’s Adventure“
”
(Quelle: eigene Darstellung)
Anhand der ausgelesenen Werte wird im GeneratorManager eine Instanz
der Klasse Rhythm, rhythm“, erstellt. Innerhalb dieser Instanz wird der
”
Rhythmus gem¨
aß des Typen entweder mit der Funktion GenerateSwing()
oder mit der GenerateRegular() erzeugt.
Es wird nun im GeneratorManagers eine Instanz levelWithCritics der Klasse Critics erzeugt, wobei dem Konstruktor der Klasse Critics die vorher
erzeugte Rhythm-Instanz als Parameter u
¨bergeben wird und so eine Instanzvariable initialisiert. Durch den Aufruf levelWithCritics.CreateLevel()
wird eine Aneinanderreihung von Rhythmusgruppen mittels der RhythmInstanzvariable erzeugt.
Dabei werden die einzelnen Komponenten nummerisch kodiert (vgl. Tabel¨
le 2 und 3). Uber
den Aufruf der Objektmethode GetLevelList() wird die
fertig erzeugte Integerliste zur¨
uckgeben.
Nun wird innerhalb des GeneratorManagers in der Methode CreateLevel()
die Liste durchlaufen. Jeder Eintrag wird an die Methode AssignTile() u
¨bergeben, welche die Eintr¨
age dekodiert und ihnen die richtige Auswahlmethode zuordnet. Dabei stehen die Methoden ChooseMove(), ChooseWaiting(),
ChooseJump() und ChooseJumpCombi() zur Verf¨
ugung, welche den Integerwerten der entsprechenden Create-Methode zuordnen.
29
5.3
Implementierung des Levelgenerators
Name
flatplatform
steep slope up
steep slope down
gradual slope up
gradual slope down
waiting
Madlen Thaleiser
Nummerncode
0
1
2
3
4
5
Tabelle 2: Kodierung der Kategorie Moving“
”
Name
flat gap
gap
no gap
jump up
jump down short
jump down medium
jump down long
spring
fall
enemy kill
enemy avoid
Nummerncode
200
mit L¨
ucke
100 bis 105
ohne L¨
ucke
110 bis 115
202
203
Tabelle 3: Kodierung der Kategorie Jumping“
”
5.3.4
Kriterien und Nachbereitung
Die Kriterien aus Abschnitt 5.2.4 werden in einer abgewandelten Form innerhalb der Klasse Critics verwendet.
Das Kombinierungskriterium wird mittels Gleichverteilung der Komponenten als spezialisierte Form der Anpassungsg¨
ute (vgl. Abschnitt 5.2.4, Formel 1) realisiert.
Hierf¨
ur werden innerhalb des Konstruktors von Critics die Listen moveTile und jumpTile initialisiert, welche u. a. die nummerische Kodierung der
Komponenten enthalten.
Sobald die Methode CreateLevel() aufgerufen wird, wird der Rhythmus wiederholt durchlaufen und den einzelnen Takten eine Komponente zugeordnet.
Die Anzahl der Rhythmuswiederholungen und die damit verbundene Gesamtl¨
ange des Levels wird mittels der Hilfsmethode GetIteration()bestimmt.
In dieser wird der L¨
angenparameter des Rhythmus einer konstanten Anzahl
an Wiederholungen zugeordnet.
Bei der Komponentenzuordnung wird aus der entsprechenden Liste (entweder moveTile oder jumpTile) eine Komponente ausgew¨ahlt und der Level30
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
liste hinzugef¨
ugt. Das ausgew¨ahlte Element wird anschließend aus der Liste
entfernt. Dieser Vorgang wiederholt sich solange, bis aus einer leeren Listen
gew¨
ahlt werden soll. Sobald dieser Fall eintritt, wird die Liste neu initialisiert. Die Komponentenzuordnung ist abgeschlossen, wenn alle Elemente
aus der Levelliste einer Komponente, entweder aus der Liste moveTile oder
aus der Liste jumpTile, zugeordnet sind.
Mit dieser Vorgehensweise wird sichergestellt, dass alle zur Verf¨
ugung stehenden Komponenten weitestgehend gleich oft innerhalb des Levels vorkommen.
Das Liniendistanzkriterium ist realisiert, indem die Distanzen der einzelnen
Komponenten zur Nulllinie verwendet werden.
Die Nullliniendistanz beschreibt die Distanz zwischen der yKoordinate des letzten Teilelementes einer Komponente und der
x-Achse (Nulllinie).
Innerhalb des Konstruktors von Critics werden die beiden Listen moveTile
und jumpTile nicht nur mit den nummerischen Kodierungen der einzelnen
Komponenten erzeugt, sondern auch mit der Nullliniendistanz dieser.
Bei der Komponentenzuordnung wird die Nullliniendistanz der gerade ausgew¨
ahlten Komponente auf die Variable currentDistance addiert und mit
zwei Bedingungen verglichen. Die currentDistance soll zum Einem kleiner
als die Rhythmusl¨
ange und zum Anderem gr¨oßer bzw. gleich einem Minimum
sein, welches sich aus der Differenz der Rhythmusl¨ange und einer festgelegten Konstante berechnet. Die genannten zwei Bedingungen sind festgelegt
worden, damit eine gr¨
oßere Variation in den H¨ohen der Komponenten vorkommt. Bei der Pr¨
ufung auf die Bedingungen wird versucht, eine m¨oglichst
kleine Gesamtdistanz zu ermitteln. Da dies nicht zwangsl¨aufig bei der ersten
Zusammenstellung von Komponenten erfolgt, wird der Zusammenstellungsprozess tausendmal durchlaufen. Nach allen Durchl¨aufen ist so entweder ein
Level mit geringer Distanz und gleichverteilten Komponenten oder zumindest ein Level mit gleichverteilten Komponenten gefunden worden.
Die Nachbereitung findet im GeneratorManager statt. Dort werden innerhalb der Create-Methoden nicht nur die einzelnen Levelkomponenten generiert, sondern entsprechend dieser auch Belohnungen.
Beispielsweise wird in der Methode CreateSpring() u
¨ber dem station¨aren
Trampolin eine Reihe von M¨
unzen erzeugt, die als Wegweiser fungieren.
Dagegen stellen M¨
unzen in der Methode CreateFall() auch eine Belohnung
f¨
ur den risikoreichen Sprung ins Ungewisse da.
5.3.5
Methoden der prozeduralen Generierung
Die Methoden aus Abschnitt 3.2, welche bei Smith et al. und bei der Implementierung Anwendung finden, waren die generative Grammatik und das
31
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
Constraint-Satisfaction-Problem.
In der Klasse GeneratorManager wurden die einzelnen Bestandteile der
Grammatik (siehe Abbildung 10) von Smith et al. in Form von CreateMethoden umgesetzt. Bei der Zuordnung der einzelnen Takte zu den richtigen Komponenten wurde die Methode AssignTile() als Dekodierungsmethode vor den eigentlichen Auswahlmethoden eingesetzt.
Die Auswahlmethoden ChooseMove(), ChooseWaiting(), ChooseJump() und
ChooseJumpCombi() haben dementsprechend die richtige Create-Methode
aufgerufen.
Der Aspekt des Constraint-Satisfaction-Problem aus Abschnitt 3.2.6 wurde durch die Umsetzung der beiden Kriterien innerhalb der Critics-Klasse
realisiert. Dort wird versucht ein Level anhand des Kombinierungs- und Liniendistanzkriteriums auszuw¨ahlen, welches eine Gleichverteilung innerhalb
der Komponentenvorkommen sowie eine m¨oglichst geringe Nullliniendistanz
(siehe Abschnitt 5.3.4) hat. Jedoch wird das Kombinierungskriterium schwerer gewichtet als das Liniendistanzkriterium, weshalb auch Level generiert
werden k¨
onnen, die nur eine Gleichverteilung der Komponentenvorkommen
aufweisen.
5.3.6
Bewertung der Implementierung
Die Implementierung des rhythmusbasierten Levelgenerators von Smith et
al. in Form des Plattformers Kitty’s Adventure“ folgt nicht komplett den
”
Vorgaben, wie sie in Abbildung 9 dargestellt sind.
Als erste Abweichung ist die Beschr¨ankung auf zwei Rhythmustypen zu nennen. Diese gr¨
undet sich, wie in Abschnitt 5.3.3 beschrieben, auf die sp¨atere
Erweiterung um Multiwege. Da beim Rhythmustyp random keine Regelm¨aßigkeit in der Abfolge der Bewegungsman¨over vorliegt, ist es f¨
ur den Spieler
einfacher, die beiden anderen Rhythmustypen swing oder regular zu erkennen und diese beim Durchqueren eines zweiten Weges erneut anzuwenden.
Eine weitere Abweichung betrifft den Realizer. Dieser sollte anhand der physikalischen M¨
oglichkeiten der Spielfigur beim Sprung Spr¨
unge definieren, die
kurz, normal oder weit sein k¨onnen. Dies wurde bei der Umsetzung vorerst
nicht ber¨
ucksichtigt, sondern der Spielfigur Kitty wurde eine angemessene
Sprungkraft zugeordnet, die f¨
ur die Bew¨altigung der einzelnen Sprungelemente ausreichend ist.
Die einzelnen Komponenten der Grammatik von Smith et al. wurden bis
auf die beweglichen Plattformen innerhalb von Kitty’s Adventure“ umge”
setzt. Bei der Umsetzung der beweglichen Plattformen existiert ein Problem,
welches bisher nicht gel¨
ost werden konnte. Die Spielfigur kann zwar auf die
Plattformen springen und mit ihnen fahren, jedoch f¨allt die Spielfigur nach
dem Verlassen einer beweglichen Plattformen durch station¨are Plattformen
durch. Daher wurde die Umsetzung dieser Komponenten vorerst nicht realisiert.
32
5.3
Implementierung des Levelgenerators
Madlen Thaleiser
Weiterhin wurden in Kitty’s Adventure“ weitere Modifizierungen im Be”
zug zum Aufbau von Smith et al. vorgenommen. Innerhalb des Aufbaues
von Smith et al. waren die Generierung der Rhythmusgruppe und die anschließende Pr¨
ufung durch die Kriterien zwei separate Schritte. Bei Kitty’s
”
Adventure“ hingegen werden die Rhythmusgruppen w¨ahrend der Generierung auf die Kriterien gepr¨
uft, so dass es nun nur noch ein Schritt ist. Des
Weiteren wurden die beiden Kriterien angepasst. Das Liniendistanzkriterium orientiert sich nur noch an der Nullliniendistanz und das Kombinierungskriterium verwendet eine Gleichverteilung als spezialisierte Form der
Anpassungsg¨
ute aus Abschnitt 5.2.4.
Auch der Prozess der Nachbereitung wurde in Kitty’s Adventure“ ange”
¨
passt. Ahnlich
wie bei der Umsetzung der Kriterien wird die Nachbereitung
w¨ahrend des Prozesses der Komponentenzuordnung durchgef¨
uhrt.
All diese Abweichungen zum Konzept von Smith et al. waren innerhalb des
Rahmens, welche sie den Spielentwicklern zur Verf¨
ugung gestellt haben.
In Abbildung 13 sind einzelne Spielszenen aus Kitty’s Adventure“ darge”
stellt, die Ausschnitte aus erzeugten Leveln auf Basis des implementierten
Levelgenerators von Smith et al. zeigen.
(a) Zwei Sprungkomponenten
(b) Zwei Gegner
(c) Stachelgegner
(d) Levelende
Abbildung 13: Spielszenen aus Kitty’s Adventure“
”
(Quelle: eigene Darstellung)
33
6 Erweiterung um Multiwege
6
Madlen Thaleiser
Erweiterung um Multiwege
6.1
Begriffskl¨
arung
In der Arbeit von Dahlskog und Togelius [3] wurden einzelne Designmuster
von Super Mario Bros“ analysiert, um sp¨ater anhand des Spielerk¨onnens
”
geeignete Muster f¨
ur die Levelgenerierung auszuw¨ahlen.
Dabei haben sie auch Muster beschrieben, die Multiwege enthielten. Es werden drei Arten von Multiwegen unterschieden (vgl. Abbildung 14):
• Zweifacher Weg - Es existiert eine h¨angende Plattform, die die
M¨
oglickeit eines anderen Weges aufzeigt.
• Dreifacher Weg - Zwei in unterschiedliche H¨ohe h¨angende Plattformen erlauben es, zwischen drei verschiedenen Wegen zu w¨ahlen.
• Risiko und Belohnung - Dies ist ein Multiweg mit einem Weg, der
eine risikoreiche Situation, z. B. ein Feind, aufweist. Nach Bew¨altigung
des Weges wartet eine Belohnung f¨
ur das Risiko.
(a) Zweifacher Weg
(b) Dreifacher Weg
(c) Risiko und Belohnung
Abbildung 14: Multiwege gem¨aß Dahlskog und Togelius
(Quelle: www.mariouniverse.com [28])
Somit kann im Allgemeinen der Begriff Multiweg wie folgt definiert werden:
Multiwege sind alternative Wege innerhalb des Levels, welche das
Absolvieren eines Levelst¨
uckes auf jeweils eine andere Art und
Weise erm¨
oglichen.
Aufbauend auf dieser Definition werden im Folgenden die M¨oglichkeiten vorgestellt, die eine Erweiterung des Levelgenerators Launchpad“ von Smith
”
et al. um Multiwege darstellen.
34
6.2
M¨
oglichkeiten der Erweiterung
6.2
Madlen Thaleiser
M¨
oglichkeiten der Erweiterung
Der Levelgenerator Launchpad“ aus Abschnitt 5.2 l¨asst einige M¨oglichkei”
ten zu, einen Multiweg zu integrieren und diesen in Kitty’s Adventure“ zu
”
realisieren.
Als erster Ansatz w¨
are das Einf¨
ugen von einzelnen Bl¨ocken bzw. Blockgruppen zu nennen. Hierbei muss gekl¨art werden, an welchen Stellen die Bl¨ocke
auftreten, ob die Bl¨
ocke immer auftreten und ob es sich um verschieden hohe
Bl¨
ocke handeln soll. Die Kombinationen aus den Antworten erlauben eine
Vielzahl an M¨
oglichkeiten zur Erstellung von Multiwegen.
Ein zweiter Ansatz ist, einen Multiweg als parallel verlaufendes Levelst¨
uck
zu verstehen. Dabei kann der Zugang zum Multiweg zum Beispiel u
¨ber eine
L¨
ucke f¨
uhren, die die Spielfigur herabspringt. Eine andere Option w¨are es,
ein spezielles Sprungbrett oder ein anderes Element zu integrieren, das die
Spielfigur hinauf zum Levelst¨
uck bewegt.
Des Weiteren w¨
are noch zu kl¨aren, wie dieses Levelst¨
uck auszusehen hat.
Das Aussehen k¨
onnte folgende verschiedene Formen annehmen:
• Wiederholung der Komponenten des Hauptweges
• Aneinanderreihung von Rhythmusgruppen basierend auf einen eigenem Rhythmus
• eine ¨
ahnliche Kombination von Komponenten, welche die gleichen Nullliniendistanzen wie die Komponenten des Hauptweges haben
Auch hier bietet die Beantwortung der Fragen eine Reihe von Kombinationsm¨
oglichkeiten.
6.3
Modellierung der Multiwege
Um Multiwege ins Spiel zu implementieren, bedarf es einer Grundlage. Aus
dem ersten Ansatz f¨
ur Multiwege werden die simplen und aus dem zweiten
Ansatz die komplexen Multiwege definiert.
6.3.1
Simpler Multiweg
Der simple Multiweg soll eine Anordnung von einzelnen oder mehreren Bl¨ocken auf gleicher H¨
ohe sein. Dabei soll das Auftreten zun¨achst zuf¨allig sein
und nur bei l¨
angeren Strecken vorkommen.
Dazu wird die Grammatik von Smith et al. (siehe Abbildung 10) um das
Nichtterminalsymbol SndPath“ erweitert, das sich in die Terminale no block“,
”
”
one block“, two blocks“, three blocks“, four blocks“ und five blocks“ auf”
”
”
”
”
schl¨
usselt. Die erweiterte Grammatik wird in Abbildung 15 dargestellt.
35
6.4
Implementierung der Multiwege
Madlen Thaleiser
Abbildung 15: Erweiterte Grammatik
(Quelle: eigene Darstellung)
6.3.2
Komplexer Multiweg
Als komplexen Multiweg wird ein Weg bezeichnet, der ein St¨
uck lang parallel
zum Hauptweg verl¨
auft. Der Weg verl¨auft unterhalb des Hauptweges und als
Zugang k¨
onnen z. B. Sprungkomponenten verwendet werden.
Um sp¨
ater die Umsetzung von komplexen Multiwegen zu erm¨oglichen, wird
das Wegkriterium definiert:
Das Wegkriterium erlaubt die Erzeugung eines Multiweges nur
dann, wenn zwischen dem Zugang und dem Ausgang zum Multiweg sich mehrere Komponenten auf den Hauptweg befinden.
Ist ein Multiweg auf Grundlage dieses Kriteriums gefunden, wird die Komponetenreihenfolge dieses Weges mittels der Komponenten des Hauptweges
erzeugt. Dabei soll jede einzelne Komponente des Multiweges aus einer Menge mit gleicher Nullliniendistanz (vgl. Abschnitt 5.3.4) gew¨ahlt werden. Diese Menge wird durch die Nullliniendistanz der entsprechenden Komponente
des Hauptweges erzeugt.
6.4
6.4.1
Implementierung der Multiwege
Implementierung des simplen Multiweges
Der Levelgenerator des Plattformerspiels Kitty’s Adventure“ wird um den
”
simplen Multiweg erweitert, indem die Switch-Anweisungen der Choose36
6.4
Implementierung der Multiwege
Madlen Thaleiser
Methoden im GeneratorManager bei entsprechenden Fallunterscheidungen
um eine Abfrage erweitert werden. Dabei wird das vorhergehende Komponentenst¨
uck betrachtet. Ist es eine flache Plattform gewesen, wird zuf¨allig
eine Anzahl an Bl¨
ocken erzeugt und diese der Methode CreateSimplePath()
u
¨bergeben. Diese Methode erzeugt die entsprechende Anzahl an Bl¨ocken.
Des Weiteren werden bei einer Kombination aus steilem Abhang und steilem
Aufgang f¨
unf Bl¨
ocke generiert, die dem Spieler die Option geben, das Tal“
”
zu u
berspringen.
¨
In Abbildung 16 sind drei Beispiele f¨
ur die Generierung von simplen Multiwegen in Kitty’s Adventure“ gezeigt.
”
(a)
(b)
(c)
Abbildung 16: simple Multiwege
(Quelle: eigene Darstellung)
6.4.2
Implementierung des komplexen Multiweges
Bei der Implementierung des komplexen Multiweges in Kitty’s Adventure“
”
wurde die Critics-Klasse um die Methode FindSecWays() erweitert. In dieser
Methode wird das Wegkriterium verwendet, wobei zun¨achst zwei Sprungtakte gepr¨
uft werden, ob sie mindestens f¨
unf, aber maximal zehn Komponenten
auseinanderliegen. Ist dies der Fall, werden beide als Tupel in die Liste possWays hinzugef¨
ugt.
Sind alle m¨
oglichen Spr¨
unge durchlaufen worden, wird die Liste possWays
auf die Anzahl der Elemente gepr¨
uft. Bei der sp¨ateren Generierung eines
Levels sollen vorerst an maximal drei Stellen komplexe Multiwege vorhanden
sein. Sollte die Liste mehr als drei Elemente aufweisen, werden die ersten
drei Elemente an einer ungeraden Position ausgew¨ahlt.
Die Auswahl der Elemente an ungerader Position erfolgt, da es vorkommen
kann, dass zwei aufeinander folgende Elemente in der Liste einen einzelnen
Sprungtakt zum Einem als Endposition und zum Anderem als Startposition
eines Multiweges verwenden k¨onnen. Dies erschwert die folgende Generie¨
rung der Multiwege, da Uberschneidungen
der Start- bzw. Endkomponente
den Zugang bzw. den Ausgang zum Weg behindern.
¨
Uber
die Methode GetSecWayList() kann innerhalb des GeneratorManagers
auf die Liste mit den Start- und Endkomponenten der komplexen Multiwege
37
6.5
Bewertung
Madlen Thaleiser
zugegriffen werden. Dies wiederum geschieht in der Methode CreateComplexPath(). In dieser Methode wird anhand der Elemente aus der secWayList
ein Teilst¨
uck des Hauptweges erzeugt. Das Teilst¨
uck wird nun durchlaufen
und f¨
ur jede Komponente des St¨
uckes wird eine Menge an Komponenten erzeugt, die die gleiche Nullliniendistanz besitzen. Aus dieser Menge wird nun
eine Komponente gew¨
ahlt, die dem komplexen Multiweg angeh¨ort. In der
Abbildung 17 sind Teile von komplexen Multiwegen in Kitty’s Adventure“
”
dargestellt.
(a) Zugang
(b) Multiweg
(c) Ausgang
Abbildung 17: Bestandteile eines generierten komplexen Weges
(Quelle: eigene Darstellung)
6.5
Bewertung
Die Implementierung beider Konzepte f¨
ur Multiwege innerhalb von Kitty’s
”
Adventure“ funktioniert und wurde mehrfach erprobt. Die Kombination beider Ans¨
atze kann jedoch dazu f¨
uhren, dass beim parallel verlaufenden Weg
Bl¨
ocke erstellt werden, die die Spielerfigur Kitty beim Springen behindern
k¨
onnen.
Eine anderer negativer Effekt ist, dass es zum Ende des komplexen Multiweges passieren kann, dass der Ausgang des Weges zu niedrig positioniert ist.
Dadurch kann die Spielfigur nur zur¨
uck auf den Hauptweg gelangen, indem
sie stirbt und am Anfang des Levels wiederbelebt wird.
Des Weiteren erzeugt die Ausgangskomponente Bl¨ocke innerhalb von M¨
unzen, was zur Folge hat, dass die M¨
unzen nicht eingesammelt werden k¨onnen.
Jedoch ist die Erweiterung des Generators um Multiwege gelungen. Sie setzt
bei den beiden Methoden der prozeduralen Generierung (generative Grammatik und Constraint-Satisfaction-Problem, vgl. Abschnitt 3.2) an und erg¨anzt diese um den Aspekt des Multiweges.
38
7 Zusammenfassung und Ausblick
7
7.1
Madlen Thaleiser
Zusammenfassung und Ausblick
Zusammenfassung
Im Rahmen dieser Arbeit wurde die Implementierung des rhythmusbasierten
Levelgenerators f¨
ur 2D-Plattformer Launchpad“ von Smith et al. [9, 12]
”
vorgestellt, welcher auf der Grundlage des Rhythmusansatzes von Compton
und Mateas [14] basierte. Des Weiteren wurde der Generator um Multiwege
erweitert.
Dabei wurden die Multiwege in die einzelnen prozeduralen Methoden der generativen Grammatik und des Constraint-Satisfaction-Problems integriert.
Die bestehende Grammatik wurde um das Nichtterminalsymbol SndPath
erweitert, so dass Blockgruppen auf gleicher H¨ohe generiert werden, sofern
l¨angere Levelpassagen ohne weitere Bewegungsman¨over als Laufen auftreten.
Dies wird als simpler Multiweg bezeichnet.
Die Erweiterung der Bedingungen des Constraint-Satisfaction-Problems um
ein zus¨
atzliches Kriterium, dem Wegkriterium aus Abschnitt 6.3.2, erlaubt
die Generierung von komplexen Multiwegen. Diese Wege verlaufen jeweils
parallel zum Hauptweg und haben Komponenten, die eine gleiche Nullliniendistanz (vgl. Abschnitt 5.3.4) aufweisen wie die entsprechenden Komponenten des Hauptweges. Dadurch weist der Multiweg Variation in seiner
Komponentenzusammenstellung zu den Komponenten des Hauptweges auf.
Die Implementierung und die Erweiterung des Generators wurde praktisch
im Plattformerspiel Kitty’s Adventure“ umgesetzt und erprobt.
”
7.2
Fazit
Die Implementierung des rhythmusbasierten Levelgenerators f¨
ur 2D-Plattformer Launchpad“ von Smith et al. und die Erweiterung um Multiwege
”
werden in dem Ergebnis dieser Arbeit in Form des Plattformerspieles Kit”
ty’s Adventure“ dargestellt. Die Ziele aus Abschnitt 1.2 sind somit erf¨
ullt.
So werden spielbare Level in einer angemessen Zeit generiert.
Jedoch kann es bei der Generierung von komplexen Multiwegen, wie sie in
Abschnitt 6.3 modelliert werden, dazu kommen, dass die Spielfigur Kitty am
Ende des Multiweges nicht wieder zum Hauptweg gelangen kann. Dadurch
ist in manchen F¨
allen der komplexe Multiweg nicht spielbar, d. h. der Weg
integriert sich nicht optimal in das generierte Level.
Bisher ist keine L¨
osung f¨
ur diesen Umstand gefunden worden. Eine Verringerung der m¨
oglichen Komponenten, die durch das Wegkriterium f¨
ur die
Generierung eines Multiweges ausgesucht werden, hat zwar das Auftreten
vermindert, jedoch nicht verhindert.
Ein weiterer Aspekt, der noch nicht in Kitty’s Adventure“ umgesetzt wird,
”
betrifft die Sprungeigenschaften der Spielfigur Kitty. In Abschnitt 2.3.1 wird
beschrieben, dass die Spielfigur zum Beispiel durch l¨angeres Dr¨
ucken der
Sprungtaste weiter springen kann. Diese Eigenschaft wird auch innerhalb des
39
7.3
Ausblick
Madlen Thaleiser
Konzeptes von Smith et al. verwendet. Bei der Spielfigur Kitty jedoch wird
nur eine angemessene Sprungh¨ohe festgelegt, aber die M¨oglichkeit, weiter
springen zu k¨
onnen, fehlt.
Die Erweiterung um Multiwege im Allgemeinen jedoch ist gelungen. Durch
die Erweiterung der beiden verwendeten Methoden der prozeduralen Generierung, die generative Grammatik und das Coinstraint-Satisfaction-Problem
(vgl. Abschnitt 3.2), ist gezeigt worden, dass das bestehende Modell von
Smith et al. [9, 12] um neue Aspekte erg¨anzt werden kann.
Aus den genannten Punkten lassen sich M¨oglichkeiten f¨
ur die Weiterentwicklung von Kitty’s Adventure“ ableiten. Zudem kann auch das Konzept
”
des Levelgenerators von Smith et al. und die Erweiterung um Multiwegen
auf Basis dieser Erkenntnisse weiterentwickelt werden.
7.3
Ausblick
Die prozedurale Generierung wird k¨
unftig bei der Erstellung von Inhalten,
z. B. in Spielen, weiter an Bedeutung gewinnen.
Der Einsatz der Software SpeedTree“ [47] in Spiel- und Filmproduktionen
”
ist eine Erleichterung f¨
ur die Produktion dieser Werke. In Zukunft wird die
Online-Generierung (siehe Abschnitt 3.4 von Inhalten neue M¨oglichkeiten
und Chancen f¨
ur die Entwicklung von Spielen bieten.
Auch der Ansatz des rhythmusbasierten Levelgenerators, der die Grundlage
f¨
ur diese Arbeit und f¨
ur die Erweiterung um Multiwege ist, bietet weitere
Optionen f¨
ur die k¨
unftige Levelgenerierung.
So k¨
onnten Multiwege innerhalb des Levels sowohl oberhalb als auch unterhalb eines Hauptweges verlaufen. Eine Realisierung f¨
ur einen Multiweg, der
unterhalb des Hauptweges verl¨auft, ist in dieser Arbeit gegeben und kann
als Ansatz f¨
ur die Umsetzung eines oberhalb verlaufenden Multiweges dienen. Dabei muss die Distanz zwischen dem Hauptweg und dem Multiweg
so gestaltet werden, dass die beiden Wege sich nicht gegenseitig behindern.
Daher ist eine Distanz zu w¨
ahlen, die die beiden Wege weit genug von einander trennt. Hierbei kann es vorkommen, dass der Zugang zu einem oberhalb
verlaufenden Multiweg nicht durch einen einfachen Sprung m¨oglich ist. Um
den Zugang zu gew¨
ahren, m¨
ussten neue Spielelemente wie zum Beispiel eine
Ranke integriert werden.
Weitere Erweiterungsm¨
oglichkeiten von Multiwegen bietet der vorgestellte
Ansatz des simplen Multiweges. Statt einer Reihe von Bl¨ocken mit gleicher
H¨ohe zu generieren, k¨
onnten auch verschieden hohe Bl¨ocke generiert werden.
Dazu m¨
usste die Grammatik noch um weitere Symbole erweitert werden.
Des Weiteren sollte eine Evaluation erfolgen, die den umgesetzten Ansatz
und dessen Erweiterung bewertet. M¨ogliche Kriterien f¨
ur die Bewertung w¨aren, wie herausfordernd die Level empfunden wurden, ob starke Frustration
herrscht, an welchen Stellen diese Frustration auftrat und wie das Spielerlebnis insgesamt war. Dies m¨
usste in Abh¨angigkeit zum Level erfolgen.
40
7.3
Ausblick
Madlen Thaleiser
Daher sollte der Generator noch um eine Speicher- und Ladefunktion erweitert werden. Damit k¨
onnen generierte Level gespeichert werden und bei der
Evaluation kann auf genaue Komponentenkombinationen des gespeicherten
Levels eingegangen werden
Zudem sollte bei der Evaluation auch eine Kontrollgruppe aus manuell erstellten Level betrachtet werden, damit ein Bezugspunkt f¨
ur die Qualit¨at
der automatisch generierten Level gegeben ist. Dabei w¨are beispielsweise
noch zu kl¨
aren, ob die manuell erstellten Level Rhythmen als Grundlage
f¨
ur die Aneinanderreihung der Levelkomponenten haben sollen oder ob die
Aneinanderreihung beliebig sein kann.
41
8 Quellenverzeichnis
8
8.1
Madlen Thaleiser
Quellenverzeichnis
Literatur
[1] Lucas Ferreira, Leonardo Pereira, and Claudio Toledo. A multipopulation genetic algorithm for procedural generation of levels for
platform games. In Proceedings of the 2014 Conference Companion
on Genetic and Evolutionary Computation Companion, GECCO Comp
’14, pages 45–46, New York, NY, USA, 2014. ACM.
[2] Mark Hendrikx, Sebastiaan Meijer, Joeri Van Der Velden, and Alexandru Iosup. Procedural content generation for games: A survey. ACM
Trans. Multimedia Comput. Commun. Appl., 9(1):1:1–1:22, February
2013.
[3] Steve Dahlskog and Julian Togelius. Patterns and procedural content
generation: Revisiting mario in world 1 level 1. In Proceedings of the
First Workshop on Design Patterns in Games, DPG ’12, pages 1:1–1:8,
New York, NY, USA, 2012. ACM.
[4] Gillian Smith, Jim Whitehead, Michael Mateas, and Mike Treanor.
Launchpad: A Rhythm-Based level generator for 2D platformers. IEEE
Transactions on Computational Intelligence and AI in Games, 3(1):1–
16, March 2011.
[5] Fausto Mourato, Manuel Pr´ospero dos Santos, and Fernando Birra.
Automatic level generation for platform videogames using genetic algorithms. In Proceedings of the 8th International Conference on Advances
in Computer Entertainment Technology, ACE ’11, pages 8:1–8:8, New
York, NY, USA, 2011. ACM.
[6] Ken Hartsook, Alexander Zook, Sauvik Das, and Mark O. Riedl. Toward supporting stories with procedurally generated game worlds. In
Sung-Bae Cho, Simon M. Lucas, and Philip Hingston, editors, CIG,
pages 297–304. IEEE, 2011.
[7] Peter A. Mawhorter and Michael Mateas. Procedural level generation
using occupancy-regulated extension. In Georgios N. Yannakakis and
Julian Togelius, editors, CIG, pages 351–358. IEEE, 2010.
[8] Martin Jennings-Teats, Gillian Smith, and Noah Wardrip-Fruin. Polymorph: A model for dynamic level generation. In G. Michael Youngblood and Vadim Bulitko, editors, AIIDE. The AAAI Press, 2010.
[9] Gillian Smith, Mike Treanor, Jim Whitehead, and Michael Mateas.
Rhythm-based level generation for 2d platformers. In Proceedings of the
4th International Conference on Foundations of Digital Games, FDG
’09, pages 175–182, New York, NY, USA, 2009. ACM.
42
8.2
Online-Ressourcen
Madlen Thaleiser
[10] Chris Pedersen, Julian Togelius, and Georgios N. Yannakakis. Modeling
player experience in super mario bros. In Pier Luca Lanzi, editor, CIG,
pages 132–139. IEEE, 2009.
[11] Chan, Chia-Jung and Thawonmas, Ruck and Chen, Kuan-Ta. Automatic Storytelling in Comics: A Case Study on World of Warcraft. In
CHI ’09 Extended Abstracts on Human Factors in Computing Systems,
CHI EA ’09, pages 3589–3594, New York, NY, USA, 2009. ACM.
[12] Gillian Smith, Mee Cha, and Jim Whitehead. A framework for analysis
of 2d platformer levels. In Proceedings of the 2008 ACM SIGGRAPH
Symposium on Video Games, Sandbox ’08, pages 75–80, New York, NY,
USA, 2008. ACM.
[13] editor. Mark J. P. Wolf. The video game explosion: A history from pong
to playstation and beyond, 2007.
[14] Kate Compton and Michael Mateas. Procedural level design for platform games. In John E. Laird and Jonathan Schaeffer, editors, AIIDE,
pages 109–111. The AAAI Press, 2006.
[15] Ralph Koster. A Theory of Fun for Game Design, 2005.
[16] Michael Mateas and Andrew Stern. Procedural authorship: A casestudy of the interactive drama facade. In Digital Arts and Culture
(DAC), 2005.
[17] Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The algorithmic
beauty of plants, 1996.
[18] P. Prusinkiewicz and James Hanan. Lindenmayer systems, fractals and
plants, 1989.
[19] Vladimir Iakovlevich Propp. Morphology of the folktale, 1968.
8.2
Online-Ressourcen
[20] John Kloetzli, Jr. Procedural Terrain Generation in Sid Meiers
Civilitazion V.
http://www.firaxis.com/?/blog/single/
procedural-terrain-generation-in-sid-meiers-civilization-v,
2013.
[21] Derek Yu. The Full Spelunky on Spelunky.
http://makegames.tumblr.com/post/4061040007/
the-full-spelunky-on-spelunky, 2011.
43
8.3
Spiele
Madlen Thaleiser
[22] David Clyde. Adding Realistic Rivers to Random Terrain.
http://archive.gamedev.net/archive/reference/articles/
article2065.html, 2004.
[23] Brown University. proppian fairy tale generator.
https://web.archive.org/web/20110716054518/http://www.
brown.edu/Courses/FR0133/Fairytale_Generator/gen.html, 2001.
[24] Ken Perlin. Making Noise, 1999. http://www.noisemachine.com/
talk1/index.html.
[25] www.speedtree.22slides.com.
http://speedtree.22slides.com/games/72157649979891788.
[26] www.speedtree.22slides.com.
http://speedtree.22slides.com/cinema-animation#3377_image_
223299.
[27] killscreendaily.com.
http://killscreendaily.com/articles/
brief-history-roguelike/.
[28] http://www.mariouniverse.com/maps/nes/smb,
Welt 1-1 aus Super Mario Bros“.
”
http://www.mariouniverse.com/images/maps/nes/smb/1-1.png.
8.3
Spiele
[29] CD Projekt RED. The Witcher 3: Wild Hunt, 2015.
[30] Grynsoft. Wings of Vi, 2014.
[31] Nintendo EAD. Super Mario 3D World, 2013.
[32] Blit Software. Sonic CD, 2012.
[33] Firaxis Games. Civilization V, 2010.
[34] Gearbox Software. Borderlands, 2009.
[35] Derek Yu, Andy Hul, Bitworks. Spelunky, 2008.
[36] Ubisoft Montreal und Ubisoft Milan. Donald Duck - Quack Attack,
2000.
[37] Nintendo EAD. Mario 64, 1996.
[38] Sega. Sonic the Hedgehog (Genesis), 1991.
[39] Brøderbund. Prince of Persia, 1990.
44
8.4
Sonstige Quellen
Madlen Thaleiser
[40] Nintendo EAD. Super Mario Bros, 1985.
[41] Activision. Pitfall!, 1982.
[42] Nintendo EAD. Donkey Kong, 1981.
[43] University of California, Berkeley. Rogue, 1980.
[44] Universal. Space Panic, 1980.
8.4
Sonstige Quellen
[45] James Cameron. Avatar, 2009.
[46] Unity Technologies. Unity 3D Engine, 2005.
Version 4.6.3 (Feb. 19, 2015).
[47] Interactive Data Visualization, Inc,. Speedtree, 2002.
Version 6.3. for Games (Mar 20, 2013) and Version 7.0 for other Applications (Nov 13, 2013).
45
A Inhalt der DVD
A
A.1
Madlen Thaleiser
Inhalt der DVD
Bachelorarbeit
Pfad: /
BachelorarbeitThaleiser2015.pdf ...............
A.2
Bachelorarbeit
Projekt
Pfad: /Projekt/
/Standalone und Web .................................
ausf¨
uhrbare Dateien f¨
ur Windows
und Mac OS X
/Kitty’s Adventure ......................................
Unity-Projektordner mit allen verwendeten
Assets und den Quellcode-Dateien
46

Kurztest Kombinatorik Serie 1 Aufgaben 1. Auf wie viele - gxy.ch

Diskrete Mathematik für Informatiker

GK Flyer - BounceTAP

Aufgabenblatt 7

Infoblatt als PDF-Download

SUCCESS-STORY - schlaepfer.com

Gehörbildung

Was ist eigentlich Ninjutsu - Ninjutsu-Mosbach

SUMMER ADVENTURE CAMP 2015

Wie Sie sehen, haben wir Sie seit geraumer Zeit im - Cyberpath.de

2 Neubau-Objekte mit 3 bzw. 4 Wohneinheiten - Kreissparkasse