© Liashko/Shutterstock.com
Wege durch das Labyrinth

Classic Games Reloaded


Klassikern wie Pac-Man haben wir es zu verdanken, dass Irrgärten und verschlungene Höhlensysteme zu den beliebtesten Spielesettings zählen. Im Rahmen des heutigen Artikels werden wir unser Augenmerk auf die prozedurale Erzeugung solcher Strukturen richten und sicherstellen, dass unsere Spielfiguren auch an den unübersichtlichsten Stellen niemals ihre Orientierung verlieren.

Hin und wieder stelle ich mir die Frage, ob solch legendäre Klassiker wie das im Jahre 1980 von Toru Iwatani entwickelte Spiel Pac-Man nur deshalb das Licht der Welt erblickt haben, weil man für die damals existierende Computerhardware schlichtweg keine komplexeren Titel programmieren konnte. Nun ja, es dürften wohl nicht ausschließlich künstlerische Erwägungen dazu geführt haben, dass die vom Spieler gesteuerte Figur wie eine gelbe Pizza oder Torte ausschaut, aus der man bereits ein Stück herausgeschnitten hat. Andererseits sähe ein Pac-Man mit Armen und Beinen wohl definitiv weniger cool aus und hätte wahrscheinlich niemals den Kultstatus erreicht, den er nun einmal innehat. Auch wenn die im Spiel gezeigten horizontalen und vertikalen Wegbegrenzungen nur mit viel Wohlwollen die Bezeichnung Labyrinth verdienen, gilt Pac-Man nichtsdestotrotz als der Urvater aller Maze-Games – also als der Ahnherr aller Spiele, deren Welten aus mehr oder weniger komplexen Irrgärten und Höhlensystemen bestehen. Die Bewegungsmöglichkeiten von Pac-Man und den im Labyrinth herumspukenden Geistern sind überaus begrenzt, da lediglich horizontale und vertikale Richtungsänderungen möglich sind. Aus dem Blickwinkel eines Programmierers ist der Verzicht auf eine diagonale Bewegungsmöglichkeit eine überaus kluge Entscheidung, da sich hierdurch die erforderlichen KI-Berechnungen enorm vereinfachen lassen, ohne dass der Spielspaß sonderlich darunter leidet.

In den vorangegangenen Artikeln sind wir bereits ausführlich darauf zu sprechen gekommen, wie sich zweidimensionale, Tile-basierte Spielewelten unter Einbeziehung der bereits mehrfach genannten C2DTileSurface-Klasse darstellen lassen. Bezüglich der Visualisierung der in den Abbildungen 1 bis 3 gezeigten Irrgärten und Höhlensysteme gibt es daher an dieser Stelle nicht viel Neues zu berichten. Aus diesem Grund werden wir im Rahmen des heutigen Artikels unser Augenmerk auf die prozedurale Erzeugung der besagten Strukturen richten und sicherstellen, dass unsere Spielfiguren auch an den unübersichtlichsten Stellen niemals ihre Orientierung verlieren.

rudolph_spieleklassiker6_1.tif_fmt1.jpgAbb. 1: Ein prozedural erzeugtes Höhlensystem (Screenshot)
rudolph_spieleklassiker6_2.tif_fmt1.jpgAbb. 2: Auf Entdeckungsreise mit dem Spieler (Screenshot)
rudolph_spieleklassiker6_3.tif_fmt1.jpgAbb. 3: Wegpunktesystem innerhalb eines Labyrinths (Screenshot)

Zelluläre Automaten als Weltenbauer

Im Prinzip sind die einzelnen Level in einem Pac-Man-Spiel derartig einfach aufgebaut, dass man sie mit ein wenig Geduld problemlos von Hand erstellen könnte. Doch seien wir mal ehrlich, früher oder später hätte wohl keiner von uns mehr Lust dazu, eine Spielfigur durch das immer gleiche Labyrinth zu steuern. Langfristiger Spielspaß lässt sich nur durch Abwechslung garantieren. Und genau aus diesem Grund benötigen wir ein prozedurales Verfahren, mit dessen Hilfe wir uns schnell und einfach eine Vielzahl von unterschiedlichen Levels zusammenbauen können. In diesem Zusammenhang könnten wir beispielsweise auf eine Reihe von vorgefertigten Levelbausteinen zurückgreifen, die sich auf verschiedenste Art und Weise aneinanderreihen lassen. Ein komplexeres Höhlensystem, wie das in Abbildung 1 gezeigte, lässt sich mit Hilfe dieser Methode allerdings nicht generieren.

Im Unterschied zu dem zuvor genannten 1-Schritt-Verfahren spiegeln prozedural erzeugte Spielewelten normalerweise das Resultat einer Vielzahl aufeinanderfolgender Berechnungsschritte wider. Im Rahmen unseres Demoprogramms beginnen wir beispielsweise zunächst damit, eine mehr oder weniger große Anzahl von Spieleweltkacheln (Felsgestein) nach dem Zufallsprinzip in einer ansonsten frei begehbaren Spielewelt zu platzieren. Im Anschluss daran definieren wir uns eine Reihe von Regeln, gemäß derer wir unsere zufallsbasierte Spielewelt in mehreren kleinen Schritten modifizieren, bis sich schließlich das zu erzeugende Höhlensystem ausgebildet hat. Die einzelnen Regeln, auf die wir bei der prozeduralen Generierung unserer Spielewelten zurückgreifen, haben ausschließlich einen lokalen Gültigkeitsbereich. Hiermit ist gemeint, dass sämtliche Veränderungen, die sich im Zuge eines Berechnungsschritts ereignen, ausschließlich davon abhängig sind, von welchen benachbarten Kacheln die einzelnen Spielewelt-Tiles umgeben sind. Für den Fall, dass man in diesem Zusammenhang alle acht benachbarten Kacheln berücksichtigt, spricht man von der sogenannten Moore-Nachbarschaft. Finden stattdessen lediglich die angrenzenden horizontalen und vertikalen Kacheln Beachtung, spricht man hingegen von einer Von-Neumann-Nachbarschaft (Vierer-Nachbarschaft).

Wissenschaftlich ausgedrückt greifen wir bei der algorithmischen Generierung unserer Spielewelt auf das Konzept eines sogenannten zweidimensionalen zellulären bzw. zellularen Automaten (engl.: Cellular Automaton im Singular bzw. Cellular Automata im Plural) zurück. Zum ersten Mal vorgestellt wurde dieses Konzept in den 1940er Jahren von Stanislaw Ulam, der damals in Los Alamos zu den Mitarbeitern des berühmt-berüchtigten Manhattan-Projekts gehörte. John von Neumann, ein damaliger Kollege Ulams, der heute als einer der Väter der Informatik gilt, griff diese Idee auf und erweiterte sie zu einem universellen Berechnungsmodell. Noch eine Anmerkung zur Namensgebung: Im Grunde genommen stellt ein „zellulärer Automat“ das formale (mathematische) Äquivalent zu einer biologischen Zelle dar. Es handelt sich in beiden Fällen um die kleinsten funktionierenden, miteinander in direktem Kontakt stehenden Einheiten eines real existierenden oder zu simulierenden Systems.

Das Funktionsprinzip eines zellulären Automaten ist so einfach wie genial. Betrachten wir als Beispiel einmal die Ausbreitung einer Grippeepidemie. Letzten Endes hängt die Ausbreitungsgeschwindigkeit davon ab, wie schnell sich die einzelnen Menschen mit dem Virus infizieren und wie häufig sie mit anderen Menschen in Kontakt treten. Die kleinsten Elemente, die wir in unserem Beispiel mit Hilfe einer Vielzahl von zellulären Automaten simulieren müssten, sind folgerichtig die einzelnen Menschen. Und auch bei der prozeduralen Generierung unserer Spielewelt gehen wir im Prinzip auf eine ganz ähnliche Weise vor: Wir ordnen jeder Spieleweltkachel einen gesonderten Automaten zu und starten die Simulation.

Die Tatsache, dass heutzutage nahezu jeder Programmierer mit dem Funktionsprinzip eines zellulären Automaten vertraut ist, verdanken wir letztlich einer einzelnen Person: dem Mathematiker John Horton Conway. Noch heute gilt das von ihm in den 1970er Jahren entwickelte „Game of Life“ (zu Deutsch: Conways Spiel des Lebens) als die populärste Umsetzung eines zweidimensionalen zellulären Automaten. Beobachtet man den Spielverlauf über einen längeren Zeitraum hinweg, dann erkennt man, dass die Bezeichnung „Spiel des Lebens“ nicht von ungefähr kommt. Die einzelnen Strukturen, die im Verlauf der Simulation entstehen und wieder vergehen, wirken in der Tat wie kleine künstliche Lebensformen.

Heutzutage vertreten einige Physiker sogar die Hypothese, dass sich unser komplettes Universum mit Hilfe einer gigantisch großen Anzahl von zellulären Automaten simulieren lassen müsste. In „Conways Spiel des Lebens“ besitzen die einzelnen zellulären Automaten bemerkenswerterweise lediglich zwei mögliche Zustände: Die Zellen können entweder lebendig oder tot sein. Im Rahmen komplexerer Simulationen (Beispiele: Räuber-Beute-Systeme, Verkehrsflussmodelle, Animation elektrischer Schaltkreise, Ausbreitung eines Waldbrands oder einer Pandemie usw.) müssen die einzelnen Zellen selbstverständlich mehr als nur zwei Zustände verarbeiten können und mitunter auch auf Zufallsereignisse reagieren.

Die zellulären Automaten, die wir für die Generierung unserer Höhlensysteme verwenden, kommen ebenfalls mit zwei einzelnen Zuständen aus: Während die lebenden Zellen die einzelnen Gesteinskacheln repräsentieren, verkörpern die toten Zellen die vom Spieler begehbaren Tiles (mit anderen Worten die Höhlenkacheln).

Das Regelwerk, auf das die zellulären Automaten im Zuge der Simulation zurückgreifen, speichern wir in einem Objekt der in Listing 1 (online auf www.entwickler.de) vorgestellten CTwoState2DCellularAutomatonRules-Klasse:

CTwoState2DCellularAutomatonRules...

headline from sands settings