# Rekursive Labyrinthe

Dieses Buch steht im Regal Programmierung.
Dieses Wikibook beschäftigt sich mit der softwaretechnischen Erstellung von Labyrinthen mit der Hilfe von strukturierten Java-Programmen. Hierbei wird ein rekursiver Algorithmus eingesetzt, der für diese Aufgabe besonders effizient und elegant formuliert werden kann.

## Rekursive Labyrinthe

Ein rekursiv bestimmtes Labyrinth ist im Sinne der Darstellung in diesem Wikibook ein System von Pfaden mit vielfältigen Möglichkeiten der Verzweigung, das aus einer abzählbaren Menge von zusammenhängenden Labyrinth-Feldern besteht. Mit zunehmender Größe wird es immer aufwendiger, den eindeutigen Pfad zwischen zwei beliebig ausgewählten begehbaren Labyrinth-Feldern zu finden. Labyrinthe, die keine Verzweigung enthalten, können im Sinne dieser „Irrgarten“-Definition mit dem hier beschriebenen rekursiven Verfahren nur mit einigen Modifikationen und unter besonderen Anfangs- und Randbedingungen berechnet werden (zum Beispiel ohne pseudozufällige Richtungswechsel und ohne beliebig positionierte Hindernisse im Labyrinth).
Zu Beginn sind alle Pfade durch Zwischenmauern blockiert, und es muss ein beliebiges begehbares Startfeld festgelegt werden, von dem aus das Labyrinth rekursiv gebildet werden soll. Der Labyrinth-Pfad wird immer wieder vom aktuellen Labyrinth-Feld aus solange auf einem noch unbegangenen und gegebenenfalls pseudozufällig zu bestimmenden benachbarten Labyrinth-Feld fortgeführt, bis alle benachbarten Labyrinth-Feldern bereits zum Pfad gehören. Dann wird immer wieder entlang des bereits gebildeten Labyrinth-Pfads zur nächsten Stelle zurückgegangen, wo eine Fortsetzung in eine neue, also noch unbegangene Richtung möglich ist. Dies wird solange fortgesetzt, bis alle Labyrinth-Felder beschritten worden sind und der rekursive Algorithmus daher zum Startfeld zurückgekehrt ist.
Im fertigen Labyrinth gibt es zwischen allen paarweise ausgewählten begehbaren Labyrinth-Feldern genau einen möglichen Pfad, bei dem jedes Feld des Pfades genau einmal betreten werden muss.

## Programmbestandteile

Das hier vorgestellte Java-Programm berechnet ein rechteckiges, rekursiv berechnetes Labyrinth. Hierzu werden mehrere Java-Klassen verwendet, die im folgenden beschrieben werden.

### MazeField

In der Java-Klasse MazeField wird ein einzelnes Labyrinth-Feld implementiert. Aus mehreren Labyrinth-Feldern kann ein Labyrinth zusammengesetzt werden.
Ein Labyrinth-Feld ist rechteckig und hat vier Seiten, die durch die vier Himmelsrichtungen Norden (oben), Osten (rechts), Süden (unten) und Westen (links) gekennzeichnet sind.
Jede Seite kann geöffnet sein, eine feste Grenze (englisch: border) haben oder aus einer Mauer (englisch: wall) bestehen, die zur Ausbildung eines Labyrinths entfernt, also zu einer Öffnung umgestaltet werden kann.
Jedes Feld hat eine eineindeutige Lage in einem Labyrinth, die durch einen ganzzahligen Rechtswert (locationX) und einen ganzzahlingen Hochwert (locationY) gekennzeichnet ist, die als 2-Tupel ganzer Zahlen dargestellt werden können: (Rechtswert | Hochwert).
Nach der Ausbildung des Labyrinths hat jedes begehbare Labyrinth-Feld einen Vorgänger (previousField) und einen Nachfolger (nextField).
Die Java-Klasse MazeField stellt auch mehrere Methoden zur Abfrage und Steuerung der Eigenschaften der Labyrinth-Felder zur Verfügung:
* Der Konstruktor MazeField (int locationX, int locationY) dient zur Initialisierung eines Labyrinth-Feldes bei der Labyrinth-Koordinate (x | y). Bei der Initialisierung eines Labyrinth-Feldes werden alle Grenzen entfernt und alle Mauern gesetzt.
* Die parameterlose Methode checkBorders prüft, ob bei allen Seiten eines Labyrinth-Feldes, die eine Grenze haben, auch die entsprechenden Mauern gesetzt sind.
* Mit den get-Methoden können die Attribute eines Labyrinth-Feldes abgefragt werden.
* Mit den set-Methoden können die Attribute eines Labyrinth-Feldes gesetzt werden.
* Mit den remove-Methoden können Grenzen oder Mauern entfernt werden.
* Mit den has-Methoden kann abgefragt werden, ob eine bestimmte Grenze oder eine bestimmte Mauer gesetzt ist. Der Rückgabewert in Boolesch.
Mit dem folgenden Java-Programm mit der Klasse MazeField können einzelne Labyrinth-Felder verwaltet werden:
→ Java-Programm "MazeField"

### MazeException

Die kurze Java-Klasse MazeException dient lediglich zur Behandlung von Gestaltungsfehlern, nachdem von den betreffenden Programmteilen eine entsprechende MazeException geworfen wurde.
Der Quelltext kann hier eingesehen werden:
→ Java-Programm "MazeException"

### MazeArray

In der Java-Klasse MazeArray wird ein rechteckiges Labyrinth in der Ebene implementiert, das sich aus mehreren, in regelmäßigen Spalten und Zeilen angeordneten Labyrinth-Feldern zusammensetzt und in der Instanzvariable fields vom Datentyp MazeField (ein zweidimensionales Array von Labyrinth-Feldern) gespeichert wird. Das Labyrinth hat eine definierte Breite width und eine definierte Höhe height.
Ein Labyrinth muss einfach zusammenhängend sein, was bedeutet, dass alle äußeren Seiten aller Labyrinth-Felder eine feste Grenze darstellen, und alle innen liegenden Labyrinth-Felder an allen Seiten ein benachbartes Labyrinth-Feld haben müssen. Vor der Berechnung eines Labyrinth-Pfades müssen alle innen liegenden Seiten aller Labyrinth-Felder mit einer Mauer versehen werden. Es ist nicht notwendig, dass alle innen liegenden Labyrinth-Felder keine Grenzen haben, sondern bestimmte Übergänge zwischen zwei benachbarten Labyrinth-Feldern können durch das Setzen der entsprechenden Grenzen verboten werden. Hat ein Labyrinth-Feld vier Grenzen, kann es nicht begangen werden, und es wird somit vom zu berechnenden Labyrinth-Pfad ausgeschlossen.
Die Java-Klasse MazeArray stellt einige Methoden zur Abfrage und Steuerung der Eigenschaften eines Labyrinth-Arrays zur Verfügung, wie zum Beispiel:
* Der Konstruktor MazeArray (int width, int height) dient zur Initialisierung eines Labyrinth-Arrays mit der Breite width und der Höhe height. Bei der Initialisierung eines Labyrinth-Arrays werden alle erforderlichen Labyrinth-Felder mit der parameterlosen Methode createMazeFields erzeugt.
* Die parameterlose Methode checkMaze prüft, ob bei allen Labyrinth-Feldern eines Labyrinth-Arrays, die Grenzen haben, auch die entsprechenden Mauern gesetzt sind. Ist dies nicht der Fall, ist die Konfiguration des Labyrinths nicht in Ordnung, und es wird eine Ausnahme MazeException geworfen.
Mit dem folgenden Java-Programm mit der Klasse MazeArray können einzelne Labyrinth-Arrays verwaltet werden:
→ Java-Programm "MazeArray"

### MazeGraphs

In der Java-Klasse MazeGraphs wird mit Hilfe einer Instanz mazeArray des Datentyps MazeArray das zu berechnende Labyrinth implementiert. Die Klasse MazeGraphs dient ferner zur graphischen Darstellung der Labyrinthe. Hierzu wird die Methode drawMaze aufgerufen.
Das Labyrinth hat die Breite (MAZE_GRID_WIDTH) und die Höhe (MAZE_GRID_HEIGHT). Jedes Labyrinth hat genau ein Startfeld (startField) und ein Endfeld (endField), die jeweils maximal drei begrenzte Seiten haben dürfen.
Bei der rekursiven Berechnung des Labyrinths gibt es zu jeden Zeitpunkt einen eindeutigen Pfad mit einer bestimmten Schrittlänge vom Startfeld zum jeweils aktuell untersuchten Labyrinth-Feld (currentLengthOfPath). In einem berechneten Labyrinth gibt es einen eindeutigen Pfad mit einer bestimmten Schrittlänge vom Startfeld zum Endfeld (lengthOfPathToEndField).
Alle Labyrinth-Felder haben die gleichen Breiten (FIELD_WIDTH), Höhen (FIELD_HEIGHT), und Grenzlinienstärken (BORDER_THICKNESS).
Bei der hier vorgestellten Implementierung befindet sich das Labyrinth-Feld mit dem kleinsten Rechtswert und dem kleinsten Hochwert (0 | 0) oben links, die positiven Rechtswerte laufen nach rechts und die positiven Hochwerten laufen nach unten. Die Eigenschaften des Labyrinths bleiben bei einer Achsenspiegelung um die horizontale oder vertikale Achse oder bei einer Punktspiegelung erhalten.

#### Ausschluss von bestimmten Labyrinth-Feldern vom Labyrinth-Pfad

Mit dem Aufruf der öffentlichen, typengebundenen Methode excludeMazeField kann jedes beliebige Labyrinth-Feld mit der Koordinate (x | y) vom Labyrinth-Pfad ausgeschlossen werden.

#### Berechnung des Labyrinths

Die öffentliche, typengebundene Methode buildMaze dient zur rekursiven Berechnung eines Labyrinths:
* Zu Beginn werden über den Aufruf der Methode setBorders die Außengrenzen des Labyrinths gesetzt.
* Dann wird ein Startfeld startField gesucht, das mit Hilfe der aufgerufenen Methode findFirstField ermittelt wird. Das Endfeld endField ist zunächst identische mit dem Startfeld.
* Mit dem Aufruf der Methode findNeighbours mit dem Parameter startField wird das Labyrinth vom Startfeld ausgehend rekursiv berechnet.
* Anschließend wird mit der Methode checkMaze überprüft, ob das Labyrinth korrekt konfiguriert ist.
* Falls bei der Prüfung die Ausnahme mazeException geworfen wurde, wird eine entsprechende Fehlermeldung ausgegeben, ansonsten wird die Länge lengthOfPathToEndField des längsten im Labyrinth auftretenden Pfades ausgegeben.
* Abschließen wird die typengebundene Methode init aufgerufen, mit der die graphische Ausgabe erzeugt wird.

#### Rekursion

Das Kernstück der Methode buildMaze und somit des gesamten Programms ist die Methode findNeighbours, die sich nach dem ersten Aufruf aus der Methode buildMaze mehrfach selber aufruft. Hierbei wird folgende Anweisungsfolge durchlaufen, sofern der Parameter field der Methode buildMazeein gültiges Feld beschreibt (field != null):
* Die Methode checkNeighbours gibt ein bislang unbegangenes Nachbarfeld neigbour des Labyrinths zurück, sofern eines gefunden werden kann. Gibt es mehrere unbegangene Nachbarfelder wird eines davon pseudozufällig ausgewählt.
* Falls es ein mögliches Nachbarfeld gibt (neighbour != null),
** wird durch den Aufruf der Methode neighbour.setPreviousField das aktuelle Feld field als der Vorgänger previousField dieses Feldes gesetzt,
** und danach wird das aktuelle Feld field auf das neu ermittelte Nachbarfeld neigbour gesetzt.
** Anschließend werden durch den Aufruf der Methode removeWalls die Mauern zwischen diesen beiden Feldern entfernt.
** Abschließend wird die aktuelle Pfadlänge currentLengthOfPath um eins erhöht (Inkrement).
* ansonsten wurde kein geeignetes Nachbarfeld gefunden (neigbour == null) und
** es wird geprüft, ob die aktuelle Pfadlänge currentLengthOfPath größer als die bislang ermittelte längste Pfadlänge lengthOfPathToEndField ist. In diesem Fall wird
*** das aktuelle Endfeld endField auf das aktuelle Feld field gesetzt
*** und die längste bislang ermittelte Pfadlänge lengthOfPathToEndField auf die die aktuelle Pfadlänge currentLengthOfPath gesetzt.
** Das aktuelle Feld field wird über den Rückgabewert der des Aufrufs der Methode field.getPreviousField auf den Vorgänger gesetzt.
** Die aktuelle Pfadlänge currentLengthOfPath wird um ein erniedrigt (Dekrement).
* In der letzten Anweisung ruft sich die Methode findNeighbours mit dem Parameter des aktuellen Feldes field selber rekursiv auf.
Wenn das aktuelle Feld field beim Durchlaufen dieses rekursiven Algorithmus irgendwann wieder beim Startfeld angekommen ist, die der Vorgänger field == null (der Konstruktor MazeField hatte das Attribut previousField von allen Labyrinth-Feldern mit dem Wert null initialisiert), und alle rekursiven Methodenaufrufe werden beendet, so dass das Programm in der Methode buildMaze fortgeführt wird.

#### Graphische Darstellung

Die öffentliche, typengebundene Methode paint muss von der typengebundenen Methode init aufgerufen werden, um ein Labyrinth als Objekt der Java-Klasse java.awt.Graphics in einen Container beziehungsweise in ein Objekt vom Datentyp Component aus dem generischen Java-package awt (Abstract Window Toolkit) zu zeichnen. Sie überschreibt die paint-Methode ihrer Superklasse Window, von der die Java-Klassen javax.swing.JFrame und somit auch MazeGraphs abgeleitet sind:
* java.awt.Component
** java.awt.Container
*** java.awt.Window
**** java.awt.Frame
***** javax.swing.JFrame
****** MazeGraphs
Mit dem folgenden Java-Programm mit der Klasse MazeGraphs können graphische Labyrinthe berechnet werden:
→ Java-Programm "MazeGraphs"

### Aufruf des Programms

Mit dem Aufruf der folgenden öffentlichen Hauptmethode main kann ein Labyrinth mit 32 Labyrinth-Feldern in der Breite und 24 Labyrinth-Feldern in der Höhe berechnet und gezeichnet werden:
In diesem Beispiel wir das mittlere Labyrinth-Feld mit der Koordinate (widthOfMaze / 2 | heightOfMaze / 2) durch den Aufruf der typengebundenen Methode excludeMazeField aus der Java-Klasse MazeGraphs vor dem Aufruf der typengebundenen Methode buildMaze der Java-Klasse MazeGraphs optional vom zu berechnenden Labyrinth-Pfad ausgeschlossen. Durch mehrfachen Aufruf dieser Methode können beliebig viele Labyrinth-Felder mit den Koordinaten (w | h) vom Labyrinth-Pfad ausgeschlossen werden. Werden zu viele zusammenhängende Felder ausgeschlossen, kann es jedoch dazu kommen, dass nicht alle begehbaren Labyrinth-Felder vom Startpunkt des Labyrinths aus erreicht werden können.
Wenn gar kein Pfad gebildet werden kann, liegt eine fehlerhafte Konfiguration des Labyrinths vor, und es kommt mit einer MazeException zu einer programmtechnischen Ausnahmebehandlung.

## Nachwort

Die hier angegebenen strukturierten Programmbeispiele können ohne große Umstände in jede andere strukturierte Programmiersprache übertragen werden. Durch die Modifikation und Ergänzung der angegebenen Algorithmen können ohne große Umstände anders gestaltete Labyrinthe berechnet werden.
Es wäre erfreulich, wenn dieses Wikibook zu einem besseren und tieferen Verständnis der strukturierten Programmierung und als Einstieg in die Technik der rekursiven Programmierung beitragen kann.
Mit dem hier vorgestellten Algorithmus erzeugte Labyrinthe mit 32 mal 32 Feldern in alternativer graphischer Repräsentation:
* Labyrinthe

## Siehe auch

* Strukturierte Programmierung
* Das Apfelmännchen
* Waldbrandsimulation

## Zusammenfassung des Projekts

„Rekursive Labyrinthe“ ist nach Einschätzung seiner Autoren zu 100 % fertig
* Zielgruppe: Informatiker, Mathematiker
* Lernziele: Erstellung rekursiv berechneter Labyrinthe mit einem Java-Programm.
* Buchpatenschaft/Ansprechperson: Benutzer:Bautsch
* Sind Co-Autoren gegenwärtig erwünscht? Ja, sehr gerne. Korrekturen von offensichtlichen Fehlern direkt im Text; Inhaltliches bitte per Diskussion.
* Richtlinien für Co-Autoren: Wikimedia-like.