Prozedural generierte Universen in der Nussschale


Von künstlicher Intelligenz erstellte Inhalte in Spielen sind kein neues Phänomen, haben aber durch Games wie Minecraft oder No Man’s Sky ein Revival erlebt. Für Entwickler stellt Procedural Content Generation (PCG) eine besondere Herausforderung dar, beginnend beim Design (Welche Algorithmen können herangezogen werden?) über die Testphase (Wie kann garantiert werden, dass prozedural generierte Level lösbar sind?) bis zur Evaluation (Wie lässt sich messen, ob automatisch erstellte Level gut sind?). Dieser blogpost liefert einen Leitfaden und eine Einführung in PCG und zeigt auch: Ohne menschliche Kreativität geht oft die Würze verloren.

Planeten, Tiere, Musik: Alles ist generierbar!

Es galt als eines der meisterwarteten Spiele dieses Jahres und wurde für viele zu einer bitteren Enttäuschung: No Man’s Sky wartete mit einem schier unendlichen Universum mit 18 Trillionen (1.8*10^19) verschiedenen Planeten auf, die völlig computergeneriert sein sollten, vom Terrain über die Pflanzen bis zu den Tieren. Auch wenn die Entwickler letztendlich etwas zu viel versprachen und so den Zorn der Spielergemeinschaft auf sich zogen, ist das Konzept gut durchdacht und das Ergebnis beeindruckend, wenn auch kein Alleinstellungsmerkmal. Bereits Infiniminer und daraus folgend Minecraft setzten auf PCG um (quasi-)unendliche Welten voller Blöcke zu generieren. Etwas früher hatte ein Indie-Entwicklerstudio mit Dwarf Fortress ein kostenloses ASCII-basiertes Spiel veröffentlicht, bei dem der Spieler eine Gruppe an Zwergen in einer zufällig generierten Welt anleiten musste. Auch die Forschung hat sich dem Thema PCG bereits früh angenommen, die Universität Texas etwa experimentierte mit Neuroevolution um im Spiel NERO eine Armee an Roboter zu trainieren, die gegen Feinde kämpft und mit der Zeit immer komplexere Manöver lernt.
Wie diese Beispiele zeigen, ist der Einsatz von PCG in Spielen sehr vielschichtig, grundsätzlich lassen sich vier “Pfade” unterscheiden, die man verfolgen kann:

  1. Prozedural generierte Spielwelten. Das kann ein dreidimensionaler dungeon sein, ein 2D platformer auf Basis einer tilemap oder sogar Geschicklichkeits- bzw. Geduldsspiele. Je nach Abstraktionsgrad kann die Generierung nur einzelne Elemente innerhalb der Welt umfassen (zB. Terrain, Pflanzen, Gebäude, Fahrzeuge, Waffen) oder ganze Planeten und Sonnensysteme.
  2. Prozedural generierte Missionen und Ziele. In solch einem Szenario werden nicht nur die Spielwelten künstlich erzeugt, sondern auch die Missionen und Ziele, die im Spiel erreicht werden müssen.
  3. Prozedural generierte NPC (Non-player character). Dieser Fall überschneidet sich thematisch mit künstlicher Intelligenz für Computergegner und ist einer der am häufigsten anzutreffenden Anwendungsfälle in Spielen.
  4. Prozedural generierte spielbegleitende Materialien (zB. Musik im Spiel).

Die Gründe für den Einsatz von PCG sind vielfältig. Offensichtlich ist, dass prozedurale Generierung die Möglichkeit bietet, mit vergleichsweise geringem Einsatz von Ressourcen und Entwicklern sehr umfangreiche Spiele zu erschaffen – das Entwicklerteam hinter No Man’s Sky etwa umfasste nur 16 Personen. Ein weiterer Grund ist, dass PCG basierte Spiele längeren Spielspaß versprechen, weil “Walkthrough”- oder “Let’s play”-Videos und “Lösungsguides” nie den vollen Umfang eines solchen Spiels zeigen können – immerhin sieht dieses dank prozeduraler Generierung für jeden Anwender anders aus. Nicht unterschätzen sollte man als Entwicklerstudio auch die publicitiy, die man mit einem gut gemachten PCG Spiel generieren kann: Künstliche Intelligenz oder Machine Learning gelten als die aktuellen Top-Themen in der IT. Entwickelt man Spiele, die auf Techniken aus diesen Bereichen aufbauen, kann man damit enormes mediales Echo erzeugen. Doch, bevor die DVD gepresst oder der “Download”-Button gedrückt werden kann, stehen zunächst viele Stunden an Arbeit an und die entscheidende Frage lautet: Wie startet man am besten?

Im Anfang war der Graph

Wer den Nintendo 64-Klassiker “Zelda: Ocarina of Time” gespielt hat, wird sich vielleicht noch mit Schaudern an den Wassertempel erinnern. Es war sehr einfach in dem Gewirr an Gängen, Rätsel und Gegner die Orientierung zu verlieren und oft half nur entweder ein Freund oder ein Lösungsbuch (Internet war damals rar). Die Tempel in der Zelda-Reihe sind nach einem grundsätzlich sehr einfachen Schema aufgebaut: Es ist eine Aneinanderreihung von Gängen und Räumen, in denen Gegner besiegt und Rätsel gelöst werden müssen um danach Schlüssel, neue Waffen oder Objekte zu erhalten, die in anderen Räumen eingesetzt werden können. So kämpft man sich Schritt für Schritt bis zu einem Zwischen- oder Endboss durch und steigert nach erfolgreichem Abschluss der Mission seine Lebens- oder Erfahrungspunkte bis man in den nächsten Tempel vordringt und sich das Prozedere wiederholte. J. Dormans hat sich in diesem interessanten paper näher mit der Struktur solcher Level aus der Adventure-Sparte beschäftigt und geschlossen, dass Tempel wie jener aus Zelda prinzipiell als gerichteter Graph dargestellt werden können, wobei der Startknoten den Eingang in den Tempel darstellt und der Endknoten den Endboss (oder Ausgang).

Mission Space

Um einen solchen Graph (und damit einen gesamten Tempel) prozedural zu generieren, gibt es verschiedene Strategien, eine Möglichkeit stellen so genannte Generative Grammatiken dar. Generative Grammatiken stammen ursprünglich aus der Linguistik und werden dort verwendet, um natürliche Sprache zu modellieren. Sie beinhalten eine Menge an Regeln, die nach dem Puzzleteil-Prinzip kombiniert werden können, um daraus komplexere Sätze zu erzeugen. Angewendet auf die Generierung von Spielwelten bedeutet das, dass von den Entwicklern eine Grammatik festgelegt wird, auf Basis derer Schritt für Schritt ein Graph gebaut wird – man spricht hierbei von Graph Grammar. Die Knoten und Kanten des Graphen können dabei je nach Spiel für verschiedene Dinge stehen, etwa für Gänge und Räume aber auch für Hindernisse und Gegner. Prinzipiell läuft die Generierung wie folgt ab: Man definiere einen Anfangs- und End-Graph und eine Menge an Ersetzungsregeln. Eine Ersetzungsregel tauscht Teile eines Graphen gegen andere Teile aus. Das nachfolgende Bild zeigt eine solche Grammatik wobei Teile die links des Pfeiles stehen durch Teile die rechts des Graphen stehen getauscht werden können:

Graph production rules

Eckige Knoten stellen in diesem Beispiel  jene Anknüpfungspunkte dar, die durch andere Graphteile ausgewechselt werden. Beginnend mit der “start rule” kann beispielweise die Knotenfolge 2:C –> 3:G mit der parallel ablaufenden Kette 1:CP –> 2:G oder aber auch der linearen Kette 1:CL –> 3:CL –> 2CL ersetzt werden (welche Regel ausgewählt wird, wird zufällig bestimmt). Runde Knoten sind “Räume”, in denen bestimmte Objekte auffindbar sind oder Hindernisse warten (e = Eingang/Startknoten, k = Schlüssel, der eine Tür aufsperrt, l = versperrte Tür, g = Ausgang/Ende, etc).
Durch eine so definierte Grammatik kann zB. der folgende Graph generiert werden:

Graph sample

Von Graphen zu Formen

Ein Missionsgraph ist schön und gut, allerdings noch weit von einem tatsächlichen Spiel entfernt. Um aus dem Modell Räume und Objekte zu generieren, gibt es eine Fülle an Möglichkeiten und welche eingesetzt werden können oder sollen, hängt stark vom Typ und Charakter des Spiels ab. No Man’s Sky etwa nutzte eine von Johan Gielis veröffentliche Formel, die den demütigen Namen Superformula bekam. Mit ihr ist es möglich, durch vergleichsweise wenig Rechenschritte natürlich wirkende zweidimensionale Formen prozedural zu generieren. Eine JavaScript-Implementierung besagter Formel namens Supershape.js wurde auf Github veröffentlicht.

supershape.js

Wer von Grammatiken noch nicht genug hat, kann auch einen Blick auf sogenannte Shape Grammars werfen. Wie auch bei den Graph Grammars werden Regeln definiert, anhand derer einfache Formen zu komplexeren Gebilden zusammengefügt werden. Ein einfaches hier entlehntes Beispiel: Im folgenden Fall sind zwei Regeln definiert (a), die ein Quadrat mit Punkt entweder zu zwei verschachtelten Quadraten mit Punkt oder zu einem einfachen Quadrat ersetzt. Ausgangspunkt ist ein Quadrat mit Punkt (b).

Shape grammar

Zufällig wird nun die erste oder zweite Regel angewendet, um aus (b) eine komplexere Form zu kreieren. Angenommen, zunächst wird zufällig Regel 1 ausgewählt – aus dem Quadrat mit Punkt entstehen zwei verschachtelte Quadrate mit Punkt. Danach wird nochmals Regel 1 angewendet – aus dem zweifach verschachtelten Quadrat wird ein dreifach verschachteltes Quadrat. Zuletzt wählt der Algorithmus zufällig Regel 2 aus – aus dem Quadrat mit Punkt wird ein Quadrat ohne Punkt und aus dem anfänglichen Quadrat mit Punkt ist eine komplexere Form entstanden.

Shape grammar production rule

Was hier in einem simplen Beispiel veranschaulicht wird, kann zu umfangreicheren Algorithmen erweitert werden, die in der Lage sind, dreidimensionale Häuser oder ganze Städte zu generieren. Eine Einführung dazu gibt es unter anderem hier.

Anwendungsbeispiel: Who Dies?

Soweit die Theorie, jetzt zur Praxis: Inspiriert durch die vielfältigen Möglichkeiten die PCG bietet, habe ich vor einigen Monaten selbst begonnen, ein Spiel zu entwickeln, dessen Welten praktisch gänzlich prozedural generiert werden. Die App nennt sich “Who Dies?” und wurde vollständig in Visual Studio 2015 mit Apache Cordova Support umgesetzt. Es gab zwei Hauptgründe, warum ich dieses setup bevorzugt habe: Erstens erlaubt Cordova die plattformunabhängige Entwicklung von Apps – das bedeutet, es ist nur eine Codebasis erforderlich, aus der die App (mit wenigen Adaptionen) für alle möglichen Plattformen veröffentlicht werden kann – von Android über iOS bis zu Windows. Zweitens basiert Cordova auf JavaScript und es existieren eine Fülle an JavaScript libraries, die die Spieleentwicklung vereinfachen. Ich habe für “Who Dies?” jQuery, openFB (für die Facebook-Integration) und Phaser verwendet. Phaser ist eine komplett in JavaScript geschriebene Spiele-Engine, die unter anderem verschiedene Physik-Systeme unterstützt und Support für tilemaps liefert.

In “Who Dies?” muss der User in einer Welt, die aus Blöcken, Objekten, Monster und Steinen besteht, erraten, welches Monster von einem Stein getroffen wird oder von der Plattform fällt, sobald Gravitation einwirkt. Tippt der Spieler richtig, bekommt er dafür Punkte, für Punkte gibt es Level-Upgrades und je höher das Level eines Spielers, desto komplexer werden die Welten. Alle Welten werden dabei durch einen Algorithmus erzeugt, der auf Markow-Ketten beruht. Eine Markow-Kette ist eine Menge an Zuständen, die durch Übergänge verknüpft sind, wobei das System nach einem selbst definierten Zeitraum von einem Zustand in den anderen wechselt. Für jeden Übergang kann eine Wahrscheinlichkeit angegeben werden, mit der dieser Übergang beim nächsten Zustandswechsel gewählt wird. Der Algorithmus durchläuft dabei die folgenden Phasen:

Schritt 1: Die Wahl des Rechtecks
Jede Welt besteht aus einer 35x20 Grid, in der Objekte platziert werden können. Zunächst wird in dieser Welt zufällig eine Startposition bestimmt und darin ein Rechteck definiert, das eine zufällige Breite und Höhe hat. In dem im nachfolgenden Bild dargestellten Beispiel wurde das Rechteck an die Startposition (0,7) gesetzt mit einer Breite von 7 und einer Höhe von 4. Das Rechteck ist für den Spieler nicht sichtbar sondern definiert nur intern den Bereich, in dem im nächsten Schritt die Blöcke platziert werden.

Who Dies? - Physics Puzzle

Schritt 2: Auswahl der Objekte
In “Who Dies?” gibt es verschiedene Objekte: Blöcke, Spins, Sprungfedern, Kisten, etc. Welche Objekte platziert werden, wird durch Markow-Ketten bestimmt. Im Spiel sind verschiedene Markow-Ketten implementiert, die abhängig vom Level des Spielers verwendet werden. Die Markow-Kette für die Level 1 bis 5 sieht wie folgt aus:

Markow-Kette

Der Algorithmus startet in Zustand S und kann nun in einen von 3 Zuständen übergehen. In welchen, wird bei der Generierung der Welt entschieden, wobei die Wahrscheinlichkeit abhängig von der Position des in Schritt 1 definierten Rechtecks ist. Ist das Rechteck eher in der linken Seite des Bildschirms angesiedelt (xPos <= 17), ist die Wahrscheinlichkeit, dass eine Stufe nach rechts entsteht höher (60%), als das die Stufen nach links führen (10%).

Schritt 3: Adaption der Objekte
Ist ein Objekt ausgewählt, wird dieses leicht verändert, damit nicht stets die gleichen Formen generiert werden. Es existieren je nach Objekt verschiedene Modifizierungsarten, bei Blöcken sind dies: Strecken (dabei wird die letzte Ebene auf die Länge des Rechtecks erweitert), Stückeln (dabei werden zufällig Löcher in die Treppe eingefügt), Stauchen (dabei wird die Stufe verkürzt) oder Erweitern (dabei werden Blöcke hinzugefügt). Ist das Objekt ein Startobjekt (also das erste im Level hinzugefügte Objekt), wird auch ein Stein zufällig oberhalb des Rechtecks hinzugefügt.
Angenommen, der Algorithmus hat Block-right und Strecken ausgewählt, die bisher generierte Welt würde danach so aussehen:

Who Dies? Tileset

Schritt 4: Berechnung des Lösungspfades
Im letzten Schritt wird der Lösungspfad berechnet. Das ist jener Pfad, den die Kugel vermutlich nehmen wird, wenn Gravitation auf sie einwirkt. Der Lösungspfad ist im nachfolgenden Bild als punktierte Linie eingezeichnet und für den Nutzer natürlich ebenfalls nicht sichtbar:

Who Dies? Solution path

Der Endpunkt des Lösungspfades ist der Ausgangspunkt für ein neues Rechteck. Zwischen Ende des Lösungspfades und Beginn des neuen Rechtecks wird noch ein offset Wert eingefügt, der eine Höhe und Breite zwischen 0 und 4 annehmen kann (das verhindert, dass der neue Block stets dicht am alten klebt). Der Algorithmus folgt nun wieder den Schritten 1 bis 4, wobei der aktuelle Zustand der Markow-Kette gespeichert bleibt. Das bedeutet: Die Wahrscheinlichkeit, dass nun erneut ein Block-right folgt, liegt bei 30%. Die Wahrscheinlichkeit, dass nun ein Block-middle folgt jedoch bei 70%. Der Algorithmus endet, wenn entweder ein zuvor definierte Anzahl an Durchläufe erreicht wird (bis Level 5 werden maximal 2 Runden ausgeführt) oder ein Rechteck eine Grenze der Welt erreicht. Die bis Level 5 verwendete Markow-Kette beinhaltet nur Blöcke, ab Level 6 kommen auch andere Objekte wie Spins oder Sprungfedern dazu, die das Modell etwas komplexer machen.

Who Dies? Level

Ist die Welt generiert, werden die Monster platziert. Das passiert - sehr unspektakulär - durch Zufall, eingeschränkt durch eine Menge an Regeln (zB. werden Monster nicht so platziert, dass sie sofort nach unten fallen, übereinander liegen oder sich gegenseitig blockieren). Am Ende werden jene Blöcke, die die untere Bildschirmgrenze berühren als Graslandschaft dargestellt und die Welt mit Hintergrundobjekten wie Bäumen oder Zäune verschönert.

Who Dies? World complete

 

Fazit: Ohne menschliche Kreativität geht es nicht

Obwohl der von mir verwendete Algorithmus äußerst simpel ist, war die Implementierung schwieriger als gedacht. Es gab 3 große Herausforderungen:

1. Die Komplexität der Welten abhängig vom Level
Ein gutes Spiel sollte eine kontinuierlich steigende Lernkurve haben, sodass Anfänger sehr schnell vorankommen und sich erfahrene Spieler nicht langweilen. In “Who Dies?” wird die Komplexität definiert als Anzahl der Entscheidungsweichen multipliziert mit der Anzahl an Steinen. Eine Entscheidungsweiche ist jeder Punkt im Spiel, in dem es für den Spieler nicht sofort offensichtlich ist, welchen Weg der Stein nehmen wird. Die Herausforderung liegt nun darin, gezielt einfache oder komplexe Level zu erstellen, abhängig davon, wie erfahren der Spieler ist. Bei der Generierung der Welten lässt sich allerdings nicht immer einfach bestimmen, ob eine Entscheidungsweiche für den Spieler offensichtlich ist oder nicht – insbesondere nicht für einen Algorithmus.

2. Gutes Design ist wichtig, eine gute Teststrategie noch wichtiger
Da PCG auf Modellen und Algorithmen beruht, kann jeder kleine Fehler in diesen Strukturen enorme Auswirkungen haben. Erschwerend hinzu kommt, dass Fehler oft nicht sofort entdeckt werden, da keine Welt wie der anderen gleicht und man eventuell tausende einwandfreie Welten generieren kann, die 1001. jedoch das Spiel zum Absturz bringt. Aus diesem Grund sollte man die Implementierung der Algorithmen mehrmals überprüfen und sich gleich zu Beginn eine Strategie überlegen, wie man das Spiel testen kann. Die Entwickler von No Man’s Sky etwa kreierten eigene Bots, die auf Planeten umherwanderten und Fotos der Landschaft machten – diese wurden dann vom Test-Team auf Inkonsistenzen überprüft.

3. Diversität der Welten
Einer der größten Herausforderungen war und ist, einen Algorithmus zu entwickeln, der interessante Welten generiert. Interessant heißt im Fall von “Who Dies?”, dass der Weg, den der Stein nimmt, nicht offensichtlich ist, dass die Monster intelligent platziert sind (und getroffen werden können) und Objekte nicht dort platziert werden, wo sie niemals in Kontakt mit einem der Steine kommen können. “Who Dies?” erreicht dieses Ziel nur teilweise, denn nach gewisser Zeit merkt der Spieler, dass sich bestimmte Konzepte wiederholen. Das ist natürlich nicht verwunderlich, denn hinter dem Spiel steckt keine schwarze Magie sondern immer die gleichen Modelle (die Markow-Ketten) sodass auch der Output (die Welt) deterministisch ist. Für die Spielehersteller besteht hier das hohe Risiko, dass Spieler aufgrund der fehlenden Abwechslung abspringen und die App nicht weiter verwenden. Und hierbei offenbart sich ein Dilemma, denn wenn ein Spiel wirklich völlig zufällig ohne jegliche Regeln generiert wird, ist es aller Voraussicht nach nicht spielbar (oder es macht zumindest keinen Spaß). Steht aber ein Regelset hinter dem Algorithmus, gibt es nur eine endliche Anzahl an Strukturen, die generiert werden können. Es gibt verschiedene Ansätze, um diesem Problem Herr zu werden, die Hoffnung ruht dabei für viele auf künstlicher Intelligenz. Die Forschung im Bereich AI schreitet zwar immer weiter voran, aber was einem Computer fehlt (und was auch in absehbarer Zeit nicht künstlich geschaffen werden kann), sind menschliche Kreativität und ein Gespür für Harmonie und Schönheit. Spielwelten-Designer können auf ihren Erfahrungsschatz und ihre Visionen bauen, wenn sie Level konstruieren – Computer können sich nur stur an Regeln halten, die ihnen vorgegeben wurde. Aus diesem Grund sollte PCG mehr als Unterstützung und Erweiterung unserer Möglichkeiten gesehen werden, aber nie als allmächtiges Werkzeug, das Menschen über kurz oder lang ersetzen kann. Richtig eingesetzt und gut implementiert haben solche Spiele jedoch das Potential, Spieler zu begeistern und andere Entwickler zu inspirieren, ihr eigenes prozedural generiertes Universum zu erschaffen.

Skip to main content