Rekursive Labyrinthe

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Books Flat Icon Vector.svg

Dieses Buch steht im Regal Programmierung.

Druckversion Dieses Buch hat eine Druckversion.
Bildschirmaufnahme eines Java-Programms zur Erstellung von Labyrinthen.

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[Bearbeiten]

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).

Beispiel eines rekursiv berechneten Labyrinths mit 128 mal 72 Feldern. Für den längsten im gesamten Labyrinth vorhandenen Pfad ist ein Startpunkt (links oben) grün und ein Endpunkt (halb links unten) orangefarben gekennzeichnet.

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[Bearbeiten]

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

MazeField[Bearbeiten]

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).

/*
  Source file: MazeField.java
  Program: MazeField
  Author: Markus Bautsch
  Licence: public domain
  Date: 23 October 2020
  Version: 1.0
  Programming language: Java
*/

/*
  This class implements a single maze field.
  A maze field is rectangular and can have walls and borders at its edges.
  The maze has to be initialised with all walls blocked
  and some of these walls can be removed for building a maze.
  The outer rim of the maze has to be defined by borders.
  Borders are also allowed within the maze to exclude certain fields from the maze.
  Borders must have walls.
*/

public class MazeField
{
	/* Directions (constants) */
	public final static byte NumberOfDirections = 4;
	public final static byte NULL = 0; // for undefined direction
	public final static byte NORTH = 1;
	public final static byte EAST = 2;
	public final static byte SOUTH = 3;
	public final static byte WEST = 4;
	
	/* Borders (cannot be removed) */
	private boolean borderN;
	private boolean borderE;
	private boolean borderS;
	private boolean borderW;
	
	/* Walls (can be removed for designing mazes) */
	private boolean wallN;
	private boolean wallE;
	private boolean wallS;
	private boolean wallW;

	/* Location of maze field and previous field for internal reference (recursion and backtracking) */
	private int locationX;
	private int locationY;
	private MazeField previousField;
	private MazeField 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[Bearbeiten]

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[Bearbeiten]

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.

/*
  Source file: MazeArray.java
  Program: MazeArray
  Author: Markus Bautsch
  Licence: public domain
  Date: 23 October 2020
  Version: 1.0
  Programming language: Java
*/

/*
  This class implements a rectangular maze
  with width fields in horizontal direction and
  with height maze fields in vertical direction.
  A maze field is rectangular and can have walls and borders at its edges.
  The maze has to be initialised with all walls blocked
  and some of these walls can be removed for building a maze.
  The outer rim of the maze has to be defined by borders.
  Borders are also allowed within the maze to exclude certain fields from the maze.
  Borders must have walls.
  Maze fields outside the outer borders must not have walls.
*/

public class MazeArray
{
	/* Size of maze */
	private int width;
	private int height;
	
	/* Array for maze fields */
	public MazeField [][] fields;
}

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[Bearbeiten]

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.

/*
  Source file: MazeGraphs.java
  Program: MazeGraphs
  Author: Markus Bautsch
  Licence: public domain
  Date: 23 October 2020
  Version: 1.0
  Programming language: Java
 */

/*
  This class implements a graphical maze as an extension of the class javax.swing.JFrame.
  A maze will be built during initalisation by a recursive algorithm.
  The coordinates of the upper left maze field are (0 | 0).
  This class implements the drawing of a maze.
  The graphical design of walls and borders are determined by this class.
 */

public class MazeGraphs extends javax.swing.JFrame
{
	/* serialVersionUID for serialisation implemented in class javax.swing.JFrame */
	private static final long serialVersionUID = 1L;

	/* Constant for defining maximum size of the maze */
	public static final int MAZE_MAX_SIZE = 128;

	/* Constants for constructing mazes that can be displayed or saved to a file */
	public static final boolean Display = true;
	public static final boolean DontDisplay = false;
	public static final boolean Save = true;
	public static final boolean DontSave = false;

	/* Size of rectangular maze grid in fields with default initialisation */
	private int MAZE_GRID_WIDTH  = 16;
	private int MAZE_GRID_HEIGHT = 16;

	/* Start and end field of maze and path length counters */
	private MazeField startField = null;
	private MazeField endField = null;
	private static long currentLengthOfPath = 0;
	private static long lengthOfPathToEndField = 0;

	/* Constants for defining size and look of maze fields */
	private static final int FIELD_WIDTH  = 24;
	private static final int FIELD_HEIGHT = 24;
	private static final int BORDER_THICKNESS = 2;

	// Instance variables
	private boolean display; /* is true, if maze shall be display on the screen */
	private boolean save; /* is true, if maze shall be saved to a PNG-file */

	/* The constructor will initialise a mazeArray with width and height */
	private MazeArray mazeArray;
}

Ausschluss von bestimmten Labyrinth-Feldern vom Labyrinth-Pfad[Bearbeiten]

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

	/* This method sets all borders of a maze field and therefore excludes it from maze path */
	public void excludeMazeField (int x, int y)
	{
		int width = mazeArray.getWidth ();
		int height = mazeArray.getHeight ();

		if ((x >= 0) && (x < width) && (y >= 0) && (y < height))
		{
			mazeArray.fields [x][y].setAllBorders ();
			if (y > 0)
			{
				mazeArray.fields [x][y - 1].setBorderS ();
			}
			if (x < (width - 1))
			{
				mazeArray.fields [x + 1][y].setBorderW ();
			}
			if (y < (height - 1))
			{
				mazeArray.fields [x][y + 1].setBorderN ();
			}
			if (x > 0)
			{
				mazeArray.fields [x - 1][y].setBorderE ();
			}
		}
	}

Berechnung des Labyrinths[Bearbeiten]

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.
	/* Method buildMaze for building the maze */
	public void buildMaze () throws MazeException
	{
		setBorders ();
		startField = findFirstField ();
		endField = startField;
		findNeighbours (startField);
		mazeArray.checkMaze ();
		this.init ();
		System.out.println ("Maze is built, path length from start to end is " + lengthOfPathToEndField + ".");
	}

Rekursion[Bearbeiten]

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.
	/* If a neighbour of the current maze field has four walls
	 * it will become open for a maze path as the new current field.
	 * The new maze field will become current field,
	 * the walls between the two fields will be removed
	 * and the method will call itself recursively until all maze fields are processed.
	 */
	private void findNeighbours (MazeField field)
	{
		if (field != null)
		{
			MazeField neighbour = checkNeighbours (field);
			if (neighbour != null)
			{
				neighbour.setPreviousField (field);
				field = neighbour;
				removeWalls (field);
				currentLengthOfPath++;
			}
			else
			{
				if (currentLengthOfPath > lengthOfPathToEndField)
				{
					endField = field;
					lengthOfPathToEndField = currentLengthOfPath;
				}
				field = field.getPreviousField ();
				currentLengthOfPath--;
			}
			findNeighbours (field); // recursive call
		}
	}

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.

Animation mit dem Prinzip der rekursiven Definition eines rechteckigen Labyrinths beginnend mit dem linken unteren Feld als Startfeld. Das jeweils aktuelle Labyrinth-Feld ist rot und die bereits gebildeten Labyrinth-Pfade sind weiß dargestellt.

Graphische Darstellung[Bearbeiten]

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
	/* Overwritten method "paint" of super class java.awt.Window -> java.awt.Frame -> javax.swing.JFrame */
	public void paint (java.awt.Graphics graphics)
	{
		drawMaze (graphics, mazeArray);
		drawMarkInField (graphics, this.startField, java.awt.Color.GREEN);
		drawMarkInField (graphics, this.endField, java.awt.Color.ORANGE);
	}

Mit dem folgenden Java-Programm mit der Klasse MazeGraphs können graphische Labyrinthe berechnet werden:

→ Java-Programm "MazeGraphs"

Aufruf des Programms[Bearbeiten]

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:

	public static void main (java.lang.String [] arguments)
	{
		int widthOfMaze  = 32;
		int heightOfMaze = 24;
		try
		{
			MazeGraphs maze = new MazeGraphs (widthOfMaze, heightOfMaze, MazeGraphs.Display, MazeGraphs.DontSave);
			maze.excludeMazeField (widthOfMaze / 2, heightOfMaze / 2);
			maze.buildMaze (); 
		}
		catch (MazeException mazeException)
		{
			System.out.println (mazeException.toString ());
		}
	}

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[Bearbeiten]

Mit dem hier vorgestellten Algorithmus mit alternativer graphischer Repräsentation erzeugtes Labyrinth mit 32 mal 32 Feldern.

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.


Siehe auch[Bearbeiten]

Zusammenfassung des Projekts[Bearbeiten]

100% fertig „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.