Zum Inhalt springen

Rekursive Labyrinthe/ MazeGraphs

Aus Wikibooks
/*
  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);
	}
}