Ich stieß erstmals im Jahr 2012 während meines Studiums in der Vorlesung ‚Künstliches Leben‘ auf das Konzept der zellularen Automaten. Schon damals fand ich es faszinierend, obwohl ich keine Gelegenheit hatte, diese Technik praktisch anzuwenden. In ‚TRAILS‘ werden nun zufallsbasierte Level mithilfe eines zellularen Automaten generiert. Jeder Level repräsentiert eine malerische Waldlichtung und vermittelt dem Spieler den Eindruck eines schier endlosen Waldes. Dank des Automaten weisen alle Level eine organische Struktur auf, die der Natur erstaunlich nahekommt. Zellulare Automaten sind äußerst vielseitig! Hier erfährst Du, wie du diese erstellen kannst.

Anwendungsgebiete

Mit zellularen Automaten können sowohl höhlenartige Strukturen wie Dungeons in RPGs als auch Waldlichtungen oder Pfade in Spielen wie ‚TRAILS‘ generiert werden. Sogar in Titeln wie SimCity (Maxis, 1989) wurden zellulare Automaten eingesetzt, um Städte zu modellieren und deren Entwicklung zu simulieren. Darüber hinaus können sie verwendet werden, um taktische Positionen, beispielsweise für Scharfschützen auf einer Karte, zu bestimmen (vgl. [MiFu2009, S. 549]). Die bekannteste Anwendung zellularer Automaten wurde von John Conway entwickelt. Die bekannteste Anwendung zellularer Automaten ist wohl das von John Conway entwickelte ‚Game of Life‘, das künstliches Leben simuliert (vgl. [SaZi2004]).

Abseits von höhlenartigen Strukturen, Landschaften und urbanen Modellierungen haben zellulare Automaten auch in anderen Bereichen ihren Platz gefunden. In der Medizin werden sie beispielsweise eingesetzt, um die Ausbreitung von Tumorzellen oder die Verbreitung von Krankheiten zu modellieren. In der Biologie dienen sie zur Simulation von Verhaltensweisen von Organismen und zur Erforschung ökologischer Systeme. Ebenso werden zellulare Automaten in der Materialforschung genutzt, um die Mikrostruktur von Materialien zu analysieren. Ihre Vielseitigkeit zeigt sich in einer breiten Palette von Anwendungen, die von der Wissenschaft bis zur Unterhaltungsindustrie reichen.

Funktionsweise

Zellulare Automaten sind rasterbasierte Systeme, die sich als eine Art Tabelle mit Spalten, Zeilen und individuellen Zellen vorstellen lassen. Jeder Zelle wird ein bestimmter Wert zugewiesen, der innerhalb eines Computerspiels zu vorher festgelegten Zeitpunkten basierend auf festen Regeln festgelegt und gegebenenfalls verändert wird. In ‚TRAILS‘ kann dieses Raster ähnlich einem Schachbrett visualisiert werden, wobei jede Zelle entweder als Wand (Wert = 0) oder als Waldboden (Wert = 1) gekennzeichnet ist. Die Anwendung dieser Regeln bestimmt schließlich das Erscheinungsbild des Spielbretts.

An folgenden Merkmalen kann man zellulare Automaten erkennen (siehe auch [Ilac2001, S. 5]):

ein-, zwei- oder dreidimensionales Zellengitter
alle Zellen sind gleichwertig
jede Zelle kann einen vorher festgelegten Wert annehmen
jede Zelle interagiert ausschließlich mit ihren Nachbarn
zu einem bestimmten Zeitpunkt aktualisiert jede Zelle ihren Zustand entsprechend einer Regel unter Einbeziehung der Werte der Zellen ihrer Nachbarschaft

Zellulare Automaten in Trails

Die Level-Generierung ist in drei Phasen aufgeteilt: Initialisierung, Simulation und Säuberung.

Initialisierung

Zuerst wird alles für die eigentliche Simulation vorbereitet. Die Größe des Gitters wird festgelegt, ein Prozentsatz für die Anzahl der Wände bestimmt (z. Bsp. 50 %) und für jede einzelne Zelle ein Zufallswert, auf Basis des Prozentsatzes, generiert und vorgemerkt.

/// <summary>
/// Fills the cell grid with random noise (the chance of a cell being a wall
/// is Percentage, e.g. 50 = 50% wall, 45 = %45 wall).
/// </summary>
private MapTileType RandomTileType() { 
return (Percentage >= random.Next(1, 101)) ? MapTileType.WALL : MapTileType.PASSAGE;
}

Simulation

Im nächsten Schritt wird der eigentliche Level gebildet. Dafür benötigen wir zunächst Regeln, die ausgeführt unser gewünschtes Resultat (nämlich einen zusammenhängenden Pfad) ergeben.

Folgende Basis-Regeln gibt es in Trails:

Wenn die Zelle eine Wand ist und weniger als vier Nachbarn Wände sind, dann wird die Zelle zu Waldboden.
Wenn die Zelle ein Waldboden ist und mehr als fünf Nachbarn Wände sind, dann wird die Zelle zu einer Wand.
Trifft nichts der beiden oberen Regeln zu, dann bleibt der Wert der Zelle unverändert.
Wenn die Zelle auf dem Rand des Gitters liegt, dann wird diese immer zur Wand.

Liest man sich die Regeln durch, fällt auf, dass zunächst die Anzahl aller Nachbarwände einer Zelle berechnet werden müssen. Insgesamt gibt es acht Nachbarn, wenn man die schrägen Zellen mitzählt. Im Fachjargon nennt man das auch die Moore-Nachbarschaft. Danach wendet man die Regeln auf jede Zelle im Gitter solange an, bis das gewünschte Ergebnis erreicht ist.

Hier in der Grafik wurden die Regeln drei Mal angewandt. Bei genauerem Hinsehen fällt auf, dass mehrere unverbundene Teile entstehen. Um diesen Fehler zu beheben, folgt Schritt drei —> Säuberung.

Säuberung

Im Bild (Simulation) kann man erkennen, dass mehrere Gebiete aus Waldboden bei der Simulation entstehen. Diese sind nicht miteinander verbunden und können zum Beispiel auch nur aus einer einzelnen Zelle bestehen. Solche Unschönheiten sollen im Säuberungsschritt optimiert werden.

In Trails benötige ich nur ein einziges großes Areal pro Karte. Deshalb wird zum Schluss nur das größte Gebiet verwendet. Alle kleineren Gebiete werden von der Karte gelöscht. Um zu erkennen, wie viele Gebiete es gibt und welches das Größte ist, verwende ich den sogenannten Floodfill-Algorithmus (dieser wird unten erklärt). Nach der Generation teste ich außerdem, ob die Karte groß genug für den Spieler ist.

Als Ergebnis erhält man einen zufallsbasierten Level auf Basis der vorher festgelegten Werte. Jedes Mal, wenn der Algorithmus ausgeführt wird, wird wieder eine neue Karte generiert.

Floodfill-Algorithmus

Der Floodfill-Algorithmus ist nicht nur ein nützliches Werkzeug in der Spieleentwicklung, sondern wird auch in der Grafikverarbeitung eingesetzt. Man kann ihn sich vorstellen wie einen „Farbfüll-Eimer“ in einer Mal-App. Der Algorithmus startet an einer bestimmten Zelle, z.B., dem Punkt, an dem Du auf eine Fläche klickst. Von hier aus überprüft er benachbarte Zellen auf eine bestimmte Bedingung, die du frei wählen kannst, solange die Zellen die gleiche Bedingung erfüllen. Dieser Prozess wiederholt sich, bis alle zusammenhängenden Zellen abgearbeitet sind oder eine Grenze erreicht wird. Für TRAILS bedeutet dies, dass der Floodfill-Algorithmus verwendet wird, um den größten Bereich auf dem Gitter zu finden, indem er sich von einem Startpunkt aus ausbreitet und alle zusammenhängenden Zellen zusammenzählt. Der Bereich mit den meisten Zellen wird dann zum neuen Level.

Vorteile

Einfache Konzeption: Zellulare Automaten sind einfach zu verstehen und zu implementieren. Ihr Raster-basiertes Design erleichtert die Modellierung komplexer Systeme.

Skalierbarkeit: Sie können auf unterschiedlichen Skalen angewendet werden, von Mikroebene (z.B., Zellen in einem Spiel) bis zur Makroebene (z.B., städtische Entwicklung).

Flexibilität: Die Regeln eines zellularen Automaten sind anpassbar. Entwickler können Regeln festlegen, die den Anforderungen ihres speziellen Anwendungsfalls entsprechen.

Komplexe Musterbildung: Sie können die Entstehung komplexer Muster und Strukturen aus einfachen Regeln ermöglichen. Dies ist nützlich, um realistische Umgebungen zu schaffen.

Spaß und Kreativität: In der Spieleentwicklung können zellulare Automaten dazu verwendet werden, einzigartige und dynamische Welten zu erschaffen, die den Spieler herausfordern und faszinieren.

Nachteile

Rechenaufwand: Für komplexe Simulationen können zellulare Automaten erhebliche Rechenressourcen erfordern. → langsame Performanz.

Schwierigkeiten bei der Feinabstimmung: Die Feinabstimmung von zellularen Automaten-Regeln kann zeitaufwändig sein und erfordert möglicherweise mehrere Iterationen, um die gewünschten Ergebnisse zu erzielen.

Verzerrte Musterbildung: Zellulare Automaten können dazu neigen, bestimmte Muster oder Strukturen zu erzeugen, die in der realen Welt nicht vorkommen. Dies kann zu unrealistischen Simulationsergebnissen führen.

Begrenzte Interaktion: Die Interaktion zwischen Zellen ist in vielen zellularen Automaten begrenzt. Sie können sich nur auf unmittelbare Nachbarn beziehen, was die Modellierung bestimmter Phänomene einschränken kann.

Beispielprojekt

Du möchtest gerne sehen, wie ich die Thematik programmiert habe? Dann lade dir jetzt das kostenlose Beispielprojekt bei Ko-Fi herunter! Quellcode herunterladen (bei Ko-fi)

Quellen und Ressourcen

Links

[Celu2019] – Celusniak, Martin – Cave Generator. https://github.com/celusniak/cavegenerator/blob/master/CellularAutomaton.java, 19.03.2019, Abruf am 01.07.2021.

[Roug2016] – RougeBasin: Cellular Automata Method for Generating Random Cave-Like Levels. http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels, 19.09.2016, Abruf am 18.06.2021.

[Cook2013] – Cook, Michael: Generate Random Cave Levels Using Cellular Automata. https://gamedevelopment.tutsplus.com/tutorials/cave- levels-cellular-automata–gamedev-9664, 23.07.2013, Abruf am 18.06.2021.

Bücher und Texte

[Berg2014] – Bergauer, Korbinian: Prozedurale Generierung dreidimensionaler Höhlen mittels zellulärer Automaten. Forschungsarbeit – SRH Hochschule Heidelberg, März 2014.

[MiFu2009] – Millington, Ian; Funge, John: Artificial Intelligence for Games – Second Edition. Morgan Kaufmann Publishers (Elsevier). ISBN 978-0-12-374731-0, S. 549-553, 2009.

[SaZi2004] – Salen, Katie; Zimmermann, Eric: Rules of Play – Game Design Fundamentals. Massachusetts Institute of Technology. ISBN 0-262-24045-9, S. 161-163, 2004.

[Ilac2001] – Ilachinski, Andrew: Cellular automata: A discrete universe. World Scientific, 2001.

About Me

Mein Name ist Anika und ich bin Software-Entwicklerin. Ich liebe Computerspiele, Zeichnen, Kiten, Schreiben und Bücher. Hier auf meinem persönlichen Blog geht es vor allem um die Spiele-Entwicklung, mein Unternehmen codepixie und persönliche Themen, die mich beschäftigen.

Zellulare Automaten