Unity Tutorial 3D Labyrinth Generator (Maze Generator) – Teil 1

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:


  1. Make the initial cell the current cell and mark it as visited
  2. While there are unvisited cells
    1. If the current cell has any neighbours which have not been visited
      1. Choose randomly one of the unvisited neighbours
      2. Push the current cell to the stack
      3. Remove the wall between the current cell and the chosen cell
      4. Make the chosen cell the current cell and mark it as visited
    2. Else if stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell

 

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:

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:

Bild: Beispiel für Zellen im Labyrinth

 

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.

Bild: Nummerierung der Wände einer Zelle

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:

 

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:

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.

Die Klasse MazePosition enthält lediglich die Eigenschaften der Position im Raum. Wir deklarieren sie in der selben Datei wie die Klasse MazeGenerator3D:

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:

 

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.

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:

 

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.

 

Das fertige Projekt könnt ihr hier runterladen und damit herumexperimentieren:

Download Tutorial Dateien

Ein Kommentar

  1. […] indefinitely. Prim’s algorithm should potentially support that. I also found a great Unity 3D labyrinth tutorial by Gaik Software which I’ll shelf for later […]

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.