Rekursive Labyrinthe/ Druckversion
Hauptteil[Bearbeiten]
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).
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:
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:
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).
- 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
- 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.
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
- javax.swing.JFrame
- java.awt.Frame
- java.awt.Window
- java.awt.Container
/* 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:
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]
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
-
-
Quelldateien[Bearbeiten]
MazeField[Bearbeiten]
/*
Source file: MazeField.java
Program: Maze Field
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;
/* Constructor all initialised MazeFields have four walls, but no borders */
public MazeField (int locationX, int locationY)
{
this.removeAllBorders ();
this.setAllWalls ();
this.locationX = locationX;
this.locationY = locationY;
this.previousField = null;
this.nextField = null;
}
/* If there is a border there has to be a wall */
public boolean checkBorders ()
{
boolean valid = true;
if (this.borderN && !this.wallN)
{
valid = false;
}
else if (this.borderE && !this.wallE)
{
valid = false;
}
else if (this.borderS && !this.wallS)
{
valid = false;
}
else if (this.borderW && !this.wallW)
{
valid = false;
}
return valid;
}
/* Get attribute loacationX */
public int getLocationX ()
{
return this.locationX;
}
/* Get attribute locationY */
public int getLocationY ()
{
return this.locationY;
}
/* Set attribute previousField */
public void setPreviousField (MazeField field)
{
this.previousField = field;
}
/* Get attribute previousField */
public MazeField getPreviousField ()
{
return this.previousField;
}
/* Set attribute nextField */
public void setNextField (MazeField field)
{
this.nextField = field;
}
/* Get attribute nextField */
public MazeField getNextField ()
{
return this.nextField;
}
/* Treat border attributes N, E, S and W */
public void setBorderN ()
{
this.borderN = true;
}
public void removeBorderN ()
{
this.borderN = false;
}
public boolean hasBorderN ()
{
return this.borderN;
}
public void setBorderE ()
{
this.borderE = true;
}
public void removeBorderE ()
{
this.borderE = false;
}
public boolean hasBorderE ()
{
return this.borderE;
}
public void setBorderS ()
{
this.borderS = true;
}
public void removeBorderS ()
{
this.borderS = false;
}
public boolean hasBorderS ()
{
return this.borderS;
}
public void setBorderW ()
{
this.borderW = true;
}
public void removeBorderW ()
{
this.borderW = false;
}
public boolean hasBorderW ()
{
return this.borderW;
}
public void removeAllBorders ()
{
this.removeBorderN ();
this.removeBorderE ();
this.removeBorderS ();
this.removeBorderW ();
}
public void setAllBorders ()
{
this.setBorderN ();
this.setBorderE ();
this.setBorderS ();
this.setBorderW ();
}
/* Treat wall attributes N, E, S and W */
public void setWallN ()
{
this.wallN = true;
}
public void removeWallN ()
{
this.wallN = false;
}
public boolean hasWallN ()
{
return this.wallN;
}
public void setWallE ()
{
this.wallE = true;
}
public void removeWallE ()
{
this.wallE = false;
}
public boolean hasWallE ()
{
return this.wallE;
}
public void setWallS ()
{
this.wallS = true;
}
public void removeWallS ()
{
this.wallS = false;
}
public boolean hasWallS ()
{
return this.wallS;
}
public void setWallW ()
{
this.wallW = true;
}
public void removeWallW ()
{
this.wallW = false;
}
public boolean hasWallW ()
{
return this.wallW;
}
public void setAllWalls ()
{
this.setWallN ();
this.setWallE ();
this.setWallS ();
this.setWallW ();
}
/* This method returns true only if all walls are set */
public boolean hasAllWalls ()
{
return this.hasWallN () && this.hasWallE () && this.hasWallS () && this.hasWallW ();
}
/* This method returns true only if all borders are set */
public boolean hasAllBorders ()
{
return this.hasBorderN () && this.hasBorderE () && this.hasBorderS () && this.hasBorderW ();
}
}
MazeException[Bearbeiten]
/*
Source file: MazeException.java
Program: Maze Exception
Author: Markus Bautsch
Licence: public domain
Date: 23 October 2020
Version: 1.0
Programming language: Java
*/
/*
This class implements an Exception for maze fields.
A MazeException should be thrown if there is an inconsistency within a maze field.
*/
public class MazeException extends java.lang.Exception
{
/* serialVersionUID for serialisation implemented in class java.lang.Exception */
private static final long serialVersionUID = 1L;
public MazeException (java.lang.String message)
{
super ("Maze field design error: " + message);
}
}
MazeArray[Bearbeiten]
/*
Source file: MazeArray.java
Program: Maze Array
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;
/* Constructor */
public MazeArray (int width, int height)
{
this.width = width;
this.height = height;
createMazeFields ();
}
public int getWidth ()
{
return this.width;
}
public int getHeight ()
{
return this.height;
}
/* This method creates all maze fields */
private void createMazeFields ()
{
int width = this.width;
int height = this.height;
fields = new MazeField [width][height];
int y = 0;
while (y < height)
{
int x = 0;
while (x < width)
{
fields [x][y] = new MazeField (x, y);
x++;
}
y++;
}
}
/* This method throws a MazeException if it detects formal errors within the maze */
public void checkMaze () throws MazeException
{
int width = this.width;
int height = this.height;
int y = 0;
while (y < height)
{
int x = 0;
while (x < width)
{
if (!fields [x][y].checkBorders ())
{
throw new MazeException ("Maze field design error at: x = " + x + " / y = " + y);
}
x++;
}
y++;
}
}
}
MazeGraphs[Bearbeiten]
/*
Source file: MazeGraphs.java
Program: MazeGraphs
Author: Markus Bautsch
Licence: public domain
Date: 3 October 2021
Version: 1.1
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;
/* Variables for top banner height and left offset width */
private static final int offset = 15;
private static final int yBannerHeight = 31;
/* 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;
/* Variable for choosing random directions initialised with current system time */
private static java.util.Random randomdirection = new java.util.Random (java.lang.System.currentTimeMillis ());
/* Constructor for object instances of class MazeGraphs */
public MazeGraphs (int width, int height, boolean displayMaze, boolean saveMaze) throws MazeException
{
super ("Maze " + width + " x " + height);
this.setDefaultCloseOperation (javax.swing.WindowConstants.EXIT_ON_CLOSE);
if ((width > 1) && (width <= MAZE_MAX_SIZE))
{
MAZE_GRID_WIDTH = width;
}
else
{
throw new MazeException ("Maze cannot be created with width " + width);
}
if ((height > 1) && (height <= MAZE_MAX_SIZE))
{
MAZE_GRID_HEIGHT = height;
}
else
{
throw new MazeException ("Maze cannot be created with height " + height);
}
mazeArray = new MazeArray (MAZE_GRID_WIDTH, MAZE_GRID_HEIGHT);
this.display = displayMaze;
this.save = saveMaze;
}
private static int getRectWidth (int gridWidth)
{
int rectWidth = (2 * offset) + (FIELD_WIDTH * gridWidth);
return rectWidth;
}
private static int getRectHeight (int gridHeight)
{
int rectHeight = yBannerHeight + (2 * offset) + (FIELD_HEIGHT * gridHeight);
return rectHeight;
}
private static int getLeftEdge (int x)
{
int leftEdge = offset + (x * FIELD_WIDTH);
return leftEdge;
}
private static int getUpperEdge (int y)
{
int upperEdge = yBannerHeight + offset + (y * FIELD_HEIGHT);
return upperEdge;
}
/* Draw single maze field */
private static void drawMazeField (java.awt.Graphics graphics, MazeField mazeField)
{
int x = mazeField.getLocationX ();
int y = mazeField.getLocationY ();
int leftEdge = getLeftEdge (x);
int rightEdge = leftEdge + (FIELD_WIDTH - 1);
int upperEdge = getUpperEdge (y);
int lowerEdge = upperEdge + (FIELD_HEIGHT - 1);
graphics.setColor (java.awt.Color.BLUE);
if (mazeField.hasWallN ())
{
graphics.drawLine (leftEdge, upperEdge, rightEdge, upperEdge);
}
if (mazeField.hasWallE ())
{
graphics.drawLine (rightEdge, upperEdge, rightEdge, lowerEdge);
}
if (mazeField.hasWallS ())
{
graphics.drawLine (leftEdge, lowerEdge, rightEdge, lowerEdge);
}
if (mazeField.hasWallW ())
{
graphics.drawLine (leftEdge, upperEdge, leftEdge, lowerEdge);
}
if (mazeField.hasAllBorders ())
{
graphics.setColor (java.awt.Color.lightGray);
graphics.fillRect (leftEdge + 1, upperEdge + 1, FIELD_WIDTH - 2, FIELD_HEIGHT - 2);
}
}
/* Draw mark in maze field */
private static void drawMarkInField (java.awt.Graphics graphics, MazeField mazeField, java.awt.Color colour)
{
final int width = FIELD_WIDTH / 2;
final int offsetW = (FIELD_WIDTH - width) / 2;
final int height = FIELD_HEIGHT / 2;
final int offsetH = (FIELD_HEIGHT - height) / 2;
int x = mazeField.getLocationX ();
int y = mazeField.getLocationY ();
int left = getLeftEdge (x) + offsetW;
int upper = getUpperEdge (y) + offsetH;
graphics.setColor (colour);
graphics.fillRect (left, upper, width, height);
}
/* Draw complete maze */
private static void drawMaze (java.awt.Graphics graphics, MazeArray mazeArray)
{
int width = mazeArray.getWidth ();
int height = mazeArray.getHeight ();
/* draw rectangular background frame for maze */
graphics.setColor (java.awt.Color.white);
int rectWidth = getRectWidth (width);
int rectHeight = getRectHeight (height);
graphics.fillRect (0, 0, rectWidth, rectHeight);
/* draw maze fields */
int y = 0;
while (y < height)
{
int x = 0;
while (x < width)
{
drawMazeField (graphics, mazeArray.fields [x][y]);
x++;
}
y++;
}
}
/* Method save for saving a maze to a graphical PNG file */
private void saveFile (java.awt.image.BufferedImage bufferedImage)
{
final java.lang.String fileExtension = "png";
java.util.Iterator <javax.imageio.ImageWriter> iter = javax.imageio.ImageIO.getImageWritersByFormatName (fileExtension);
javax.imageio.ImageWriter imageWriter = (javax.imageio.ImageWriter) iter.next ();
javax.imageio.ImageWriteParam imageWriteParam = imageWriter.getDefaultWriteParam ();
imageWriteParam.setCompressionMode (javax.imageio.ImageWriteParam.MODE_DISABLED);
try
{
java.lang.String fileName = "Maze_" + this.MAZE_GRID_WIDTH + "x" + this.MAZE_GRID_HEIGHT + "." + fileExtension;
javax.imageio.stream.FileImageOutputStream fileImageOutputStream = new javax.imageio.stream.FileImageOutputStream (new java.io.File (fileName));
imageWriter.setOutput (fileImageOutputStream);
javax.imageio.IIOImage iIOimg = new javax.imageio.IIOImage ((java.awt.image.RenderedImage) bufferedImage, null, null);
java.lang.System.out.println ("Save " + fileName);
imageWriter.write (null, iIOimg, imageWriteParam);
}
catch (java.lang.Exception exception)
{
exception.printStackTrace ();
}
}
/* Method init for initialisation of maze */
private void init ()
{
// Set frame size and background
int rectWidth = getRectWidth (MAZE_GRID_WIDTH);
int rectHeight = getRectHeight (MAZE_GRID_HEIGHT);
this.setSize (rectWidth, rectHeight);
this.setBackground (java.awt.Color.WHITE);
java.awt.image.BufferedImage bufferedImage = new java.awt.image.BufferedImage (rectWidth, rectHeight, java.awt.image.BufferedImage.TYPE_INT_RGB);
java.awt.Graphics2D graphics2D = bufferedImage.createGraphics ();
this.paint (graphics2D);
if (this.save)
{
this.saveFile (bufferedImage);
}
this.setVisible (this.display);
}
/* 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 ();
}
}
}
/* Remove walls between current field and previous field */
private void removeWalls (MazeField currentField)
{
MazeField previousField = currentField.getPreviousField ();
if ((currentField != null) && (previousField != null))
{
if (currentField.getLocationX () == previousField.getLocationX ())
{
if (currentField.getLocationY () > previousField.getLocationY ())
{
currentField.removeWallN ();
previousField.removeWallS ();
}
if (currentField.getLocationY () < previousField.getLocationY ())
{
currentField.removeWallS ();
previousField.removeWallN ();
}
}
else
{
if (currentField.getLocationY () == previousField.getLocationY ())
{
if (currentField.getLocationX () > previousField.getLocationX ())
{
currentField.removeWallW ();
previousField.removeWallE ();
}
if (currentField.getLocationX () < previousField.getLocationX ())
{
currentField.removeWallE ();
previousField.removeWallW ();
}
}
}
}
}
/* Check possible neighbour field to the left (west) and return it if possible */
private MazeField checkNeighbourW (MazeField field)
{
int x = field.getLocationX();
int y = field.getLocationY();
MazeField possibleNeighbour = null;
if (x > 0)
{
MazeField neighbourField = mazeArray.fields [x - 1][y];
if (neighbourField.hasAllWalls () && !field.hasBorderW () && !neighbourField.hasBorderE ())
{
possibleNeighbour = neighbourField;
}
}
return possibleNeighbour;
}
/* Check possible neighbour field to the right (east) and return it if possible */
private MazeField checkNeighbourE (MazeField field)
{
int x = field.getLocationX();
int y = field.getLocationY();
MazeField possibleNeighbour = null;
int maxX = mazeArray.getWidth () - 1;
if (x < maxX)
{
MazeField neighbourField = mazeArray.fields [x + 1][y];
if (neighbourField.hasAllWalls () && !field.hasBorderE () && !neighbourField.hasBorderW ())
{
possibleNeighbour = neighbourField;
}
}
return possibleNeighbour;
}
/* Check possible neighbour field to the top (north) and return it if possible */
private MazeField checkNeighbourN (MazeField field)
{
int x = field.getLocationX();
int y = field.getLocationY();
MazeField possibleNeighbour = null;
if (y > 0)
{
MazeField neighbourField = mazeArray.fields [x][y - 1];
if (neighbourField.hasAllWalls () && !field.hasBorderN () && !neighbourField.hasBorderS ())
{
possibleNeighbour = neighbourField;
}
}
return possibleNeighbour;
}
/* Check possible neighbour field to the bottom (south) and return it if possible */
private MazeField checkNeighbourS (MazeField field)
{
int x = field.getLocationX();
int y = field.getLocationY();
MazeField possibleNeighbour = null;
int maxY = mazeArray.getHeight () - 1;
if (y < maxY)
{
MazeField neighbourField = mazeArray.fields [x][y + 1];
if (neighbourField.hasAllWalls () && !field.hasBorderS () && !neighbourField.hasBorderN ())
{
possibleNeighbour = neighbourField;
}
}
return possibleNeighbour;
}
/* Compute and return random direction from 1 to MazeField.NumberOfDirections */
private static byte getRandomDirection ()
{
byte random = (byte) (randomdirection.nextLong () % MazeField.NumberOfDirections + 1);
return random;
}
/* This method checks whether the walls between two random maze fields next to each other can be removed.
* If possible then an appropriate neighbour else null will be returned. */
private MazeField checkNeighbours (MazeField field)
{
MazeField neighbour = null;
boolean triedN = false; // for direction north
boolean triedE = false; // for direction east
boolean triedS = false; // for direction south
boolean triedW = false; // for direction west
while ((neighbour == null) && (!triedN || !triedE || !triedS || !triedW))
{
byte direction = getRandomDirection ();
if (!triedN && (direction == MazeField.NORTH))
{
neighbour = checkNeighbourN (field);
triedN = true;
}
else if (!triedE && (direction == MazeField.EAST))
{
neighbour = checkNeighbourE (field);
triedE = true;
}
else if (!triedS && (direction == MazeField.SOUTH))
{
neighbour = checkNeighbourS (field);
triedS = true;
}
else if (!triedW && (direction == MazeField.WEST))
{
neighbour = checkNeighbourW (field);
triedW = true;
}
}
return neighbour;
}
/* This method sets all outer borders */
private void setBorders ()
{
int width = mazeArray.getWidth ();
int height = mazeArray.getHeight ();
int y = 0;
while (y < height)
{
mazeArray.fields [0][y].setBorderW ();
mazeArray.fields [width - 1][y].setBorderE ();
int x = 0;
while (x < width)
{
mazeArray.fields [x][0].setBorderN ();
mazeArray.fields [x][height - 1].setBorderS ();
x++;
}
y++;
}
}
/* This method searches for the first maze field without four borders,
* which can be used as the first current field.
*/
private MazeField findFirstField () throws MazeException
{
MazeField currentField = null;
int width = mazeArray.getWidth ();
int height = mazeArray.getHeight ();
int y = 0;
while ((currentField == null) && (y < height))
{
int x = 0;
while ((currentField == null) && (x < width))
{
if (!mazeArray.fields [x][y].hasAllBorders ())
{
currentField = mazeArray.fields [x][y];
}
x++;
}
y++;
}
if (currentField == null)
{
throw new MazeException ("start field cannot be found!");
}
return currentField;
}
/* 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
}
}
/* 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 + ".");
}
/* 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);
}
}