Zellulare Automaten

Von zellularen Automaten hörte ich zum ersten Mal im Studium 2012 in der Vorlesung „Künstliches Leben“. Schon damals fand ich das Konzept interessant, hatte aber bisher keine Chance, es irgendwo anzuwenden. In Trails gibt es zufallsbasierte Level in einem endlos großen Wald. Wälder sind organisch aufgebaut, weshalb ich Lichtungen nicht einfach quadratisch oder rechteckig wie Räume darstellen wollte. Hier kamen mir die zellularen Automaten wieder in den Sinn.

Anwendungsgebiete

Mit zellularen Automaten können höhlenartige Strukturen (zum Beispiel Dungeons in RPGs) erschaffen werden. Im Falle von Trails werden Waldlichtungen oder Pfade durch den Wald erstellt. In SimCity (Maxis, 1989) wurden zellulare Automaten zur Modellierung der Stadt verwendet, um herauszufinden, wie die Stadt sich entwickelt. Des Weiteren können auch taktische Positionen von zum Beispiel Scharfschützen auf einer Karte damit ermittelt werden (vgl. [MiFu2009, S. 549]). Die bekannteste Anwendung zellularer Automaten wurde von John Conway entwickelt. Das im Scientific American als Puzzle veröffentlichte „Game of Life“ simuliert künstliches Leben (vgl. [SaZi2004]).

Funktionsweise

Zellulare Automaten sind rasterbasierte Systeme. Man kann sich dies in etwa wie eine Tabelle mit Spalten, Zeilen und einzelnen Zellen vorstellen. Jeder Zelle wird ein Wert zugewiesen, der zu einem bestimmten Zeitpunkt im Computerspiel anhand von vorher festgelegten Regeln gesetzt und ggf. geändert wird. In Trails kann man sich dieses Raster wie ein Schachbrett vorstellen. Jede Zelle ist entweder eine Wand (Wert = 0) oder Waldboden (Wert = 1). Die Regeln bestimmen, wie das Spielbrett letztendlich aussieht.

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 – Punkt 3) 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. 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.

Vorteile

schnelle Implementierung
viele Quellen im Internet mit Beispielen (siehe unten)

Nachteile

Update-Funktionen von zellularen Automaten sind oft sehr verzweigt. Was zu einer erhöhten CPU-Last führen kann → langsame Performanz.
Komplexität vergleichsweise hoch
schwer vorhersehbare Resultate

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 Resourcen

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/Artikel

[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, Fotografieren, Kiten, Schreiben und Bücher. Hier auf meinem persönlichen Blog geht es vor allem um Software-Entwicklung, mein Unternehmen codepixie und persönliche Themen, die mich beschäftigen.