Manchmal benötigt man für seine Spiele einen Irrgarten / Labyrinth oder einfach nur ein prozedural generiertes Level. In Wikipedia findet man zum Thema „Maze Algorithm“ einige Algorithmen, die einfach umzusetzen sind. Hier möchte wir nun am Beispiel des „Depth-first search – Algorithmus“ einen 3D Labyrinth Generator in Unity erstellen. Das heißt unser Labyrinth soll nicht nur Räume in der zweidimensionalen Ebene haben, sondern Abzweigungen können genauso gut nach oben oder nach unten gehen.
Wikipedia beschreibt den Algorithmus so:
- Make the initial cell the current cell and mark it as visited
- While there are unvisited cells
- If the current cell has any neighbours which have not been visited
- Choose randomly one of the unvisited neighbours
- Push the current cell to the stack
- Remove the wall between the current cell and the chosen cell
- Make the chosen cell the current cell and mark it as visited
- Else if stack is not empty
- Pop a cell from the stack
- Make it the current cell
- If the current cell has any neighbours which have not been visited
Unity Projekt und Dateien
Auf den Algorithmus kommen wir später zurück, beginnen wir mit Unity. Zunächst erstellen wir ein neues Projekt. Da wir später unser Labyrinth auch noch visualisieren wollen, wählen wir als Preset 3D aus.
In unserem Projekt erstellen wir dann ein neues Skript und nennen es MazeGenerator3D.cs. Dieses Skript soll den Algorithmus ausführen.
Die nun erstellte Klasse MazeGenerator3D leitet sich, wie es primär mal alle neu erstellten Klassen sollten, von der Klasse MonoBehaviour ab. Das brauchen wir im Moment nicht, daher entfernen wir die Ableitung und die automatisch erstellten Funktionen Start() und Update(). Das Skript sollte dann wie folgt aussehen:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class MazeGenerator3D {
}
Da der Algorithmus auf Zellen basiert, benötigen wir allerdings noch eine weitere Klasse, die die Eigenschaften einer Zelle des Labyrinths beschreibt. Dazu erstellen wir ein neues Skript und nennen es MazeCell.cs. Wir löschen hier ebenfalls die Ableitung und die Funktionen.
Grundüberlegungen zur Zelle
Nun machen wir uns einige Überlegungen dazu, wie so eine Zelle aussehen könnte. Primär ist unsere Zelle ein Raum mit einer nicht ganz beliebigen Anzahl an Wänden. Zum Besseren Verständnis stellen wir uns ein zweidimensionales Quadrat vor. Dieses Quadrat hat vier Wände. Jede dieser Wände kann einen Durchgang zur nächsten Zelle bieten oder verschlossen sein. Unsere Zelle kann aber genauso gut nur drei Wände haben. Dann würde sich unser zweidimensionales Labyrinth aus Dreiecken aufbauen. Wenn unsere Zelle sechs Wände hat, könnten wir ein zweidimensionales Labyrinth haben, das aus Hexagons besteht – oder, jetzt sprengt es das Vorstellungsvermögen, ein dreidimensionales Labyrinth, dass aus Würfeln besteht. Letzteres ist genau das, was wir für unser dreidimensionales Labyrinth benötigen.
Während wir jetzt Beispiele hatten, die praktisch umsetzbar sind, wäre eine Zelle mit zum Beispiel acht Wänden in einem zweidimensionalen Labyrinth nicht umsetzbar, wenn alle Zellen die gleiche Größe haben und alle Wände eine potenzielle Nachbarzelle haben sollen. Das folgende Bild verdeutlicht dieses Problem:
Eigenschaften einer der Zelle
Da wir für unser dreidimensionales Labyrinth als Zellen Würfel mit genau sechs Seiten benötigen, benutzen wir zum Festlegen der Wände ein Array der Größe 6.
Dazu legen wir für uns genau fest welches Element, also welche Wand, in welche Richtung zeigt. Mit true oder false wird dann gespeichert, ob die Wand existiert (true) oder nicht (false).
In diesem Tutorial legen wir uns wie in folgendem Bild erkennbar fest. Wir wählen diese Nummerierung, da die Summe gegenüberliegender Wände immer 5 ergibt und somit einfach herauszufinden ist, welche Wand auf der gegenüberliegenden Seite liegt.
Letztendlich brauchen wir nur noch die Eigenschaft ob unser Algorithmus diese Zelle bereits besucht hat oder nicht. Auch hier reicht eine bool Variable.
Im Konstruktor unserer Klasse legen wir die Array-Größe fest und setzen alle Wände auf existieren (= true).
Der fertige Code unserer Klasse MazeCell sollte dann so aussehen:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class MazeCell {
public bool[] walls;
public bool visited;
public MazeCell()
{
walls = new bool[6] { true, true, true, true, true, true };
visited = false;
}
}
Vorbereitung und Eigenschaften der Klasse MazeGenerator3D
Unser Algorithmus muss wissen welche Größe das zu erstellende Labyrinth haben soll. Dazu legen wir in der Klasse MazeGenerator3D drei Variablen an:
private int sizeX;
private int sizeY;
private int sizeZ;
Außerdem brauchen wir noch unsere Zellen, die wir in einem dreidimensionalen Array speichern und, wie es der Algorithmus vorgibt, einen Stack in dem wir die Reihenfolge der besuchten Zellen speichern. Die Größe des Arrays vom Stack entspricht der Gesamtanzahl der Zellen des Labyrinths. Diese berechnet sich aus Länge * Breite * Höhe.
public MazeCell[,,] cells;
private MazePosition[] stack;
Die Klasse MazePosition enthält lediglich die Eigenschaften der Position im Raum. Wir deklarieren sie in der selben Datei wie die Klasse MazeGenerator3D:
public class MazePosition
{
public int x, y, z;
public MazePosition(int posX, int posY, int posZ)
{
x = posX;
y = posY;
z = posZ;
}
}
Im Konstruktor definieren wir die Größe des Arrays für die Zellen und initialisieren jede einzelne Zelle in einer Schleife. Des weiteren wird die Größe des Stacks festgelegt und die Startposition des Algorithmus zufällig festgelegt. Dabei wird dann gleichzeitig die erste Zelle als als besucht markiert. Die Wände bleiben bisher alle verschlossen (true), müssen also hier nicht verändert werden. Als Parameter des Konstruktors lassen wir uns die Größe unseres Labyrinths übergeben:
public MazeGenerator3D (int size_X, int size_Y, int size_Z)
{
sizeX = size_X;
sizeY = size_Y;
sizeZ = size_Z;
cells = new MazeCell[sizeX, sizeY, sizeZ];
// Initialisieren aller Zellen
for (int x = 0; x < sizeX; x++)
{
for (int y = 0; y < sizeY; y++)
{
for (int z = 0; z < sizeZ; z++)
{
cells[x, y, z] = new MazeCell();
}
}
}
// Arraygröße des Stacks entspricht aller Zellen im Labyrinth
// Die Initialisierung der einzelnen Positionen ist erst später wichtig.
stack = new MazePosition[sizeX * sizeY * sizeZ];
// Lediglich die erste Position wird initialisiert und zufällig festgelegt.
int startX = Random.Range(0, sizeX);
int startY = Random.Range(0, sizeY);
int startZ = Random.Range(0, sizeZ);
stack[0] = new MazePosition(startX, startY, startZ);
positionInStack = 0;
// Die erste Zelle an der Startposition wird auf besucht gesetzt: visited = true
cells[startX, startY, startZ].visited = true;
}
Programmierung des Algorithmus
Der Algorithmus macht es erforderlich herauszufinden welche der Nachbarzellen noch nicht besucht worden sind. Dazu erstellen wir nun die Methode checkNeighbours(). Die Methode gibt uns ein Array zurück, mit den Wänden, durch die wir zu einer noch nicht besuchten Zelle gehen können. Ist die Größe des Arrays 0, so gibt es keine nicht besuchten Zellen um die aktuelle Zelle.
private int[] checkNeighbours(MazePosition currentPosition)
{
List<int> result = new List<int>();
int x = currentPosition.x;
int y = currentPosition.y;
int z = currentPosition.z;
// Wand 0 überprüfen
if (x - 1 >= 0) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x - 1, y, z].visited == false) result.Add(0); // Füge die Wand 0 hinzu
}
// Wand 5 überprüfen
if (x + 1 < sizeX) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x + 1, y, z].visited == false) result.Add(5); // Füge die Wand 5 hinzu
}
// Wand 1 überprüfen
if (y - 1 >= 0) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x, y - 1, z].visited == false) result.Add(1); // Füge die Wand 1 hinzu
}
// Wand 4 überprüfen
if (y + 1 < sizeY) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x, y + 1, z].visited == false) result.Add(4); // Füge die Wand 4 hinzu
}
// Wand 2 überprüfen
if (z - 1 >= 0) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x, y, z - 1].visited == false) result.Add(2); // Füge die Wand 2 hinzu
}
// Wand 3 überprüfen
if (z + 1 < sizeZ) // Zuerst überprüfen ob wir überhaupt noch innerhalb der vorgegeben Größe sind
{
if (cells[x, y, z + 1].visited == false) result.Add(3); // Füge die Wand 3 hinzu
}
return result.ToArray();
}
Als letztes müssen wir noch die Methode generate() implementieren. Hier wird in einer Schleife Schritt für Schritt durch die Zellen gegangen und überprüft ob es weitere unbesuchte Nachbarzellen gibt. Der Code ist im folgenden in den Kommentaren erläutert:
public void generate()
{
// Da der Algorithmus immer dann rückwärts läuft, wenn keine unbesuchten Nachbarzellen gefunden werden,
// führen wir ihn so lange aus, bis wir wieder am Anfang unseres Stacks sind.
while (positionInStack >= 0)
{
// Die aktuell zu überprüfende Zelle ist im Stack unter der aktuellen Position gespeichert.
int x = stack[positionInStack].x;
int y = stack[positionInStack].y;
int z = stack[positionInStack].z;
// Überprüfe die Nachbarzellen
int[] possibleNeighbours = checkNeighbours(stack[positionInStack]);
if (possibleNeighbours.Length > 0) // Es wurden unbesuchte Nachbarzellen gefunden
{
// Wähle eine zufällige Wand aus, durch die der Algorithmus jetzt zur nächsten Zelle geht
int wall = possibleNeighbours[Random.Range(0, possibleNeighbours.Length)];
// Setze die gewählte Wand in der aktuellen Zelle auf false (= existiert nicht = Durchgang)
cells[x, y, z].walls[wall] = false;
// Bestimme die neuen Koordinaten anhand der ausgewählten Wand
if (wall == 0) x--;
else if (wall == 5) x++;
else if (wall == 1) y--;
else if (wall == 4) y++;
else if (wall == 2) z--;
else if (wall == 3) z++;
// Und setze die neue Zelle auf besucht und öffne die Wand (die gegenüberliegend von der, der vorherigen Zelle ist)
// sowie erhöhe den Stack um eins und setze die neue Position
positionInStack++;
stack[positionInStack] = new MazePosition(x, y, z);
cells[x, y, z].visited = true;
cells[x, y, z].walls[5-wall] = false;
}
else // Es wurden keine unbesuchten Nachbarzellen gefunden
{
// Also gehe eine Position im Stack zurück
positionInStack--;
// Und überprüfe anschließend erneut die jetzt aktuelle Zelle auf unbesuchte Nachbarzellen
}
}
}
Das war bereits alles. Ein weiteres Tutorial folgt in Kürze, in dem kurz und knapp erläutert wird, wie das Labyrinth in Unity dargestellt und als Level genutzt werden kann.