Labyrinthe bauen

Es ist erstaunlich einfach, ein Labyrinth zu bauen, und man findet dazu auch eine Menge Anleitungen. Ich möchte hier die Beschreibung von MazeWorks aufgreifen und in Java umsetzen.

Im Rohzustand besteht das Labyrinth aus einer Anzahl von Zellen, die alle von vier Wänden begrenzt sind. Darin entstehen dann die Gänge, indem man an einer beliebigen Stelle startet und dann die folgenden Schritte so lange wiederholt, bis man in allen Zellen einmal gewesen ist:

  1. Wähle eine beliebige Nachbarzelle, in der Du noch nicht warst.
  2. Wenn Du eine findest, dann entferne die Zwischenwand zu dieser Zelle und begebe Dich dorthin. Wenn Du keine solche Nachbarzelle findest, gehe zurück zur letzten besuchten Zelle.

Klingt ganz einfach, und die Umsetzung ist auch nicht schwer.

Fangen wir mit der Beschreibung einer Labyrinthzelle an. Dazu brauchen wir eine kleine Java-Klasse, mit der wir beliebig viele "Zellen-Objekte" erzeugen können. Jede dieser Zellen muss sich merken, auf welchen Seiten sie von Wänden begrenzt ist.

Code

package labyrinth;
 
public class Zelle {
 
    boolean wand_nord = true;
    boolean wand_ost = true;
    boolean wand_sued = true;
    boolean wand_west = true;
    final int zeilenposition;
    final int spaltenposition;
 
    public Zelle(int zeile, int spalte) {
        zeilenposition = zeile;
        spaltenposition = spalte;
    }
}

Erläuterung:
Ich habe im Quellverzeichnis einen Ordner namens "labyrinth" angelegt, in dem ich alle Java-Quelldateien speichern werde. Dieses Verzeichnis muss im Programm an allererster Stelle als "Package" genannt sein.
Nach der Benennung der Klasse folgen die Variablen, die die vier möglichen Wände einer Zelle beschreiben. Auf jeder Seite gibt es entweder eine Wand oder es gibt keine. Das beschreibt man am besten mit einer Variable vom Typ "boolean", die entweder wahr (true) oder falsch (false) sein kann.
Ich habe jede der vier Wände auf "true" gesetzt, weil alle Zellen gemäß Labyrinth-Bauanleitung zu Beginn rundherum geschlossen sein sollen.
Darunter finden sich noch zwei "int"-Variablen, also ganzzahlige Werte. Darin möchte ich jeder Zelle bei der Erzeugung mitgeben, an welcher Stelle sie sich im Labyrinth befindet. Aber was bedeutet "final"? Damit stelle ich ganz einfach sicher, dass die beiden Zahlenwerte später nicht mehr verändert werden. Eine Zelle in Reihe 7, Spalte 12 muss unbedingt an dieser Stelle bleiben und darf nicht versehentlich an eine andere Stelle gerückt werden. Ich hätte "final" auch weglassen können, aber so ist das Ganze etwas abgesichert und vermeidet später Fehler.
Zuletzt haben wir noch den Block, der mit "public Zelle" beginnt. Das ist ein Konstruktor. Nicht jede Klasse braucht einen Konstruktor, hier ist er aber ganz hilfreich. Er sorgt dafür, dass man Zellen grundsätzlich nur mit einer Positionsangabe neu erstellen kann, also z.B. so:
Zelle z = new Zelle(5, 3);

Aufbau des Labyrinths
Mit Hilfe der Zellen können wir nun das Labyrinth bauen. Dazu fangen wir mit einer eigenen Klasse an und erweitern sie Schritt für Schritt.

Code

package labyrinth;
 
public class Labyrinth {
 
    final int ANZAHL_ZEILEN = 40;
    final int ANZAHL_SPALTEN = 70;
    Zelle[][] labyrinthfeld = new Zelle[ANZAHL_ZEILEN][ANZAHL_SPALTEN];
}

Auch hier gibt es zwei "final"-Werte: Die Anzahl der Zeilen und Spalten im Labyrinth. Natürlich sind hier auch andere Werte als 40 und 70 möglich. Nach dem Aufbau des Labyrinths dürfen sich die beiden aber nicht mehr ändern.
Die Variable "labyrinthfeld" ist etwas Besonders: ein zweidimensionales Array, das ausschließlich Zellen enthalten kann. Indem die beiden vorherigen Größenangaben übernommen werden, reserviert sich das Programm genug Speicherplatz für 40 x 70 Zellen. Jede einzelne können wir später über Koordinaten ansprechen, z.B.
labyrinthfeld[14][23]

In Java gibt es viele Möglichkeiten, gleichartige Dinge in einer Sammlung aufzureihen. Es lohnt sich, diese Collections genauer anzuschauen, weil sie für ganz verschiedene Einsatzzwecke gebaut sind und deshalb verschiedene Eigenarten besitzen.
Gerade eben habe ich ein Array verwendet, das sich für eine bekannte und unveränderliche Anzahl von Objekten eignet. Als nächstes verwende ich einen Stapel (Stack) und einen Vector. Die beiden füge ich so ein:

Code

package labyrinth;
 
import java.util.Stack;
import java.util.Vector;
 
public class Labyrinth {
 
    final int ANZAHL_ZEILEN = 40;
    final int ANZAHL_SPALTEN = 70;
    Zelle[][] labyrinthfeld = new Zelle[ANZAHL_ZEILEN][ANZAHL_SPALTEN];
    Stack<Zelle> arbeitspfad = new Stack<Zelle>();
    Vector<Zelle> restlicheZellen = new Vector<Zelle>();
}

Ohne die beiden import-Befehle müsste ich im Programmcode immer "java.util.Stack" statt "Stack" schreiben und entsprechend "java.util.Vector" statt einfach nur "Vector".

Wie unterscheiden sich diese beiden nun? Und warum verwende ich hier keine Arrays?
Die beiden Variablen "arbeitspfad" und "restlicheZellen" benötige ich zum Aufbau des Labyrinths:

  • Im Arbeitspfad soll nachvollziehbar sein, welchen Weg das Programm bisher gegangen ist. Er enthält also eine ganz bestimmte Reihenfolge von Zellen und das Programm soll von der letzten Zelle aus beliebig viele Schritte zurück gehen können. Das ist im Prinzip nichts anderes als ein Kartenstapel, von dem man die obersten Karten abnimmt. Und deshalb verwende ich für den Arbeitspfad den Collectiontyp Stack.
  • Das Programm muss bei jedem Schritt prüfen, ob die umliegenden Zellen schon abgearbeitet sind. Also erzeuge ich eine Sammlung aller Felder und entnehme ihr nach und nach die bearbeiteten Zellen. Hier spielt die Reihenfolge keine Rolle, und Zellen werden an beliebigen Stellen aus der Sammlung genommen. Für diese Arbeit eignet sich ein Vector besser als ein Stack.

Der ganze Aufbau des Labyrinths ist eigentlich nichts anderes als eine Umschichtung sämtlicher Zellen vom Vector "restlicheZellen" in den Stack "arbeitspfad". Am Anfang ist der Arbeitspfad leer, am Ende enthält er alle Zellen und dafür ist der Vector "restlicheZellen" dann leer. Während dieser Umschichtung entfernt das Programm nach und nach die Zwischenwände.

Jetzt machen wir uns an das eigentliche Programm. Dafür bekommt die Klasse "Labyrinth" einen Konstruktor:

Code

public Labyrinth() {
        zellenVorbereiten();
        baueGaenge();
        baueAusgaenge();
    }

Ich finde es hilfreich, einzelne Vorgänge in eigene Funktionen bzw. Methoden mit aussagekräftigen Namen zu packen. Hier lasse ich den Konstruktor nacheinander drei Dinge tun:

  1. Zellen vorbereiten
  2. Gänge bauen
  3. Ausgänge bauen

Vielleicht überrascht es, die Ausgänge am Ende zu bauen. Das funktioniert, weil durch die Art des Labyrinthbaus grundsätzlich alle Zellen erreichbar sind. Es gibt keine abgetrennten Bereiche. Und wenn man von jedem Punkt des Labyrinths jeden anderen erreichen kann, ist es egal, welche zwei Felder den Eingang und den Ausgang bilden. Die beiden müssen nicht mal am Rand des Labyrinths liegen.

Jetzt füge ich die drei Methoden in die Labyrinth-Klasse ein, angefangen mit "zellenVorbereiten". Diese Methode soll alle Zellen erzeugen und diese sowohl im Array "labyrinthfeld" als auch im Vector "restlicheZellen" speichern.

Code

private void zellenVorbereiten() {
        for (int i = 0; i < ANZAHL_ZEILEN; i++) {
            for (int j = 0; j < ANZAHL_SPALTEN; j++) {
                labyrinthfeld[i][j] = new Zelle(i, j);
                restlicheZellen.push(labyrinthfeld[i][j]);
            }
        }
    }

Hier sind zwei for-Schleifen ineiander verschachtelt, um alle Zeilen und alle Spalten zu durchlaufen. Mit i zähle ich die Zeilen, mit j die Spalten. In der vierten Spalte erzeugt das Programm eine neue Zelle mit den Koordinaten i, j und speichert diese im Array labyrinthfeld unter den gleichen Koordinaten. Hier muss beachtet werden, dass das erste Element eines Arrays immer die Nummer 0 hat. Also hat das erste Feld die Koordinaten 0, 0 und das letzte die Koordinaten 39, 69. Darum steht in beiden for-Schleifen als Prüfbedingung "kleiner als" und nicht "kleiner gleich" dem jeweiligen Maximalwert.
Die fünfte Zeile sorgt dafür, dass die gleiche Zelle auch noch im Vector "restlicheZellen" steht.

Weiter geht's mit der Methode "baueGaenge":

Code

private void baueGaenge() {
        int zeile = zufall(ANZAHL_ZEILEN);
        int spalte = zufall(ANZAHL_SPALTEN);
        Zelle aktuelleZelle = labyrinthfeld[zeile][spalte];
        arbeitspfad.push(aktuelleZelle);
        restlicheZellen.remove(aktuelleZelle);
 
        while (restlicheZellen.size() > 0) {
            aktuelleZelle = arbeitspfad.peek();
            Vector nachbarn = findeUnverarbeiteteNachbarn(aktuelleZelle);
            if (nachbarn.size() > 0) {
                Zelle zufaelligerNachbar = (Zelle) nachbarn.get(zufall(nachbarn.size()));
                entferneZwischenwand(aktuelleZelle, zufaelligerNachbar);
                aktuelleZelle = zufaelligerNachbar;
                arbeitspfad.push(aktuelleZelle);
                restlicheZellen.remove(aktuelleZelle);
            } else {
                arbeitspfad.pop();
            }
        }
    }

Das sieht auf den ersten Blick schon etwas komplizierter aus, deshalb erkläre ich Schritt für Schritt, was hier passiert:
In Zeile 2 und 3 wählt das Programm eine zufällige Startzelle und speichert sie in Zeile 4 als "aktuelleZelle". Dann kommt der Arbeitspfad ins Spiel: Er soll ja alle Zellen in der Reihenfolge des Labyrinthaufbaus enthalten. Also füge ich die aktuelle Zelle dort mit dem push-Befehl ein. Aus dem Vector "restlicheZellen" kann die aktuelle Zelle entfernt werden.
Nun beginnt eine Schleife, die solange wiederholt wird, bis "restlicheZellen" leer ist. Erst dann liefert die Methode "size" als Ergebnis "0". In der Schleife geschieht folgendes:
Als aktuelle Zelle betrachtet das Programm die Zelle, die ganz oben auf dem Stapel "arbeitspfad" liegt. Diese Zelle bleibt auf dem Arbeitspfad, dehalb die Methode "peek". Mit "findeUnverarbeiteteNachbarn" ermittelt es dann die Nachbarzellen, die noch nicht abgearbeitet sind. Wenn es eine oder mehrere davon gibt, wählt das Programm zufällig eine davon aus, entfernt die Zwischenwand dorthin und "geht" in diese Zelle. Die neue Zelle kommt in den Arbeitspfad und wird aus der Sammlung der restlichen Zellen gelöscht. Wir sind also erfolgreich einen Schritt näher ans Ziel gekommen.
Wenn das Programm keine Nachbarn findet, nimmt es mit der "pop"-Methode die letzte Zelle vom Stapel "arbeitspfad" und wandert damit eine Zelle rückwärts. Und das geschieht so lange, bis das Programm wieder eine Zelle mit nicht abgearbeiteten Nachbarn findet. So gräbt sich das Programm durch das ganze Gitter.

Ich habe hier drei Methoden ausgelagert, damit es nicht unübersichtlich wird: "zufall", "findeUnverarbeiteteNachbarn" und "entferneZwischenwand". Hier die Methode "zufall", die einfach einen Zufallswert zwischen 0 und einem gegebenen Maximalwert zurückgibt:

Code

public int zufall(int max) {
        return (int) Math.floor(Math.random() * max);
    }

Dabei sorgt "floor" für ein Abrunden. Das muss sein, denn die Zufallszahl kann 0 sein, darf aber den Maximalwert nicht erreichen. Warum? Weil Arrays bei 0 beginnen und das 40. Element die Nummer 39 hat.

So finden wir die noch nicht verarbeiteten Nachbarzellen:

Code

private Vector findeUnverarbeiteteNachbarn(Zelle zelle) {
        int zeile = zelle.zeilenposition;
        int spalte = zelle.spaltenposition;
        Vector<Zelle> nachbarn = new Vector<Zelle>();
        if (zeile > 0) {
            Zelle noerdlicherNachbar = labyrinthfeld[zeile - 1][spalte];
            if (restlicheZellen.contains(noerdlicherNachbar)) {
                nachbarn.add(noerdlicherNachbar);
            }
        }
        if (zeile < ANZAHL_ZEILEN - 1) {
            Zelle suedlicherNachbar = labyrinthfeld[zeile + 1][spalte];
            if (restlicheZellen.contains(suedlicherNachbar)) {
                nachbarn.add(suedlicherNachbar);
            }
        }
        if (spalte > 0) {
            Zelle westlicherNachbar = labyrinthfeld[zeile][spalte - 1];
            if (restlicheZellen.contains(westlicherNachbar)) {
                nachbarn.add(westlicherNachbar);
            }
        }
        if (spalte < ANZAHL_SPALTEN - 1) {
            Zelle oestlicherNachbar = labyrinthfeld[zeile][spalte + 1];
            if (restlicheZellen.contains(oestlicherNachbar)) {
                nachbarn.add(oestlicherNachbar);
            }
        }
        return nachbarn;
    }

Die if-Bedingungen sind nötig, weil es Randzellen mit nur drei Nachbarn und Eckfelder mit nur zwei Nachbarn gibt.

Und nun weg mit der Zwischenwand:

Code

private void entferneZwischenwand(Zelle zelle, Zelle nachbar) {
        if (zelle.zeilenposition > nachbar.zeilenposition) {
            //Nachbar liegt nördlich
            zelle.wand_nord = false;
            nachbar.wand_sued = false;
        }
        if (zelle.zeilenposition < nachbar.zeilenposition) {
            //Nachbar liegt südlich
            zelle.wand_sued = false;
            nachbar.wand_nord = false;
        }
        if (zelle.spaltenposition > nachbar.spaltenposition) {
            //Nachbar liegt westlich
            zelle.wand_west = false;
            nachbar.wand_ost = false;
        }
        if (zelle.spaltenposition < nachbar.spaltenposition) {
            //Nachbar liegt östlich
            zelle.wand_ost = false;
            nachbar.wand_west = false;
        }
    }

Hier kann grundsätzlich nur eine der if-Bedingungen zutreffen, aber die Wand muss sowohl in der aktuellen als auch in der Nachbarzelle entfernt werden.

Bleibt noch eine letzte Sache: Ein- und Ausgang bauen. Die Methode "baueAusgaenge" hatte ich ja schon im Konstruktor aufgerufen.

Code

private void baueAusgaenge() {
        Zelle eingang = labyrinthfeld[0][zufall(ANZAHL_SPALTEN)];
        eingang.wand_nord = false;
        Zelle ausgang = labyrinthfeld[ANZAHL_ZEILEN - 1][zufall(ANZAHL_SPALTEN)];
        ausgang.wand_sued = false;
    }

Der Eingang soll in der ersten Zeile (Nr. 0) liegen, der Ausgang in der letzten (ANZAHL_ZEILEN minus 1). Die Spalte wird zufällig gewählt.

Damit ist der Bau des Labyrinths fertig. Bleibt nur ein Problem: Wir sehen es nicht.
Unser Labyrinth-Programm muss auch zeichnen können, sonst war die ganze Mühe umsonst. Das erreichen wir mit diesen Schritten:

  1. Wir lassen die Klasse Labyrinth alle Eigenschaften einer grafische Komponente erben, dem JPanel.
  2. Wir fügen eine weitere Methode namens "paint" ein, die alle Zellen zeichnet.
  3. Das fertige JPanel zeigen wir innerhalb eines JFrame an.

Diese Schritte können im Programmcode nachvollzogen werden.

Download: komplettes Netbeans-Projekt (ZIP-Datei, 24 KB)

Ausprobieren:

Noch kein Feedback