package com.hatherly.Maze;
import java.util.ArrayList;
import java.util.Random;
/**
* This class generates the random maze. It uses a simple
* algorithm: First, pick a random point that doesn't have
* a wall. Now, draw a line in a random direction until you
* get to a wall. Keep going until all the points have
* walls. It has been enhanced slightly to stop the early
* walls being very long as this tends to make rather easy mazes.
* @author Adam Hatherly
*/
public class MazeGenerator {
private static final int UP = 0;
private static final int RIGHT = 1;
private static final int DOWN = 2;
private static final int LEFT = 3;
private static final int MAX_WALL_LENGTH = 3;
private int size_x = 0;
private int size_y = 0;
private ArrayList nodes = new ArrayList();
private ArrayList availableNodes = new ArrayList();
private Random generator;
/**
* Initialise the maze size and random number generator
* @param x Width in "units"
* @param y Height in "units"
*/
MazeGenerator(int x, int y) {
this.size_x = x;
this.size_y = y;
generator = new Random();
}
/**
* Controls the maze creation process
*/
public void makeMaze() {
initEmptyMaze();
int counter = 1;
while (availableNodes.size() > 0) {
int randomIndex = generator.nextInt( availableNodes.size() );
int randomKey = ((Integer)availableNodes.get(randomIndex)).intValue();
int direction = generator.nextInt( 4 );
int x = getKeyX(randomKey);
int y = getKeyY(randomKey);
int length = findWallLength(x, y, direction, 1);
if (length < MAX_WALL_LENGTH) {
makeWall(x,y,direction,counter);
counter++;
}
}
}
/**
* Recursive method that when provided a point and a
* direction will create a wall until it hits an existing wall.
* @param x X position to start from
* @param y Y position to start from
* @param direction Direction - 0=Up, 1=Right, 2=Down, 3=Left
* @param counter Number for wall - used for debugging
*/
private void makeWall(int x, int y, int direction, int counter) {
MazeNodes n, n2;
int key, key2;
boolean hadWall = false;
availableNodes.remove(new Integer(makeKey(x,y)));
switch(direction) {
case UP:
key = makeKey(x,y);
n = (MazeNodes)nodes.get(key);
n.setHasWall(true);
nodes.set(key,n);
key2 = makeKey(x,y-1);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
n2.setDown(true);
n2.setHasWall(true);
n2.setDownWallNumber(counter);
nodes.set(key2, n2);
if (!hadWall) {
makeWall(x,y-1,UP,counter);
}
break;
case DOWN:
key = makeKey(x,y);
key2 = makeKey(x,y+1);
n = (MazeNodes)nodes.get(key);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
n.setDown(true);
n.setHasWall(true);
n.setDownWallNumber(counter);
nodes.set(key, n);
if (!hadWall) {
makeWall(x,y+1,DOWN,counter);
}
break;
case LEFT:
key = makeKey(x,y);
n = (MazeNodes)nodes.get(key);
n.setHasWall(true);
nodes.set(key,n);
key2 = makeKey(x-1,y);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
n2.setRight(true);
n2.setHasWall(true);
n2.setRightWallNumber(counter);
nodes.set(key2, n2);
if (!hadWall) {
makeWall(x-1,y,LEFT,counter);
}
break;
case RIGHT:
key = makeKey(x,y);
key2 = makeKey(x+1,y);
n = (MazeNodes)nodes.get(key);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
n.setRight(true);
n.setHasWall(true);
n.setRightWallNumber(counter);
nodes.set(key, n);
if (!hadWall) {
makeWall(x+1,y,DOWN,counter);
}
break;
}
}
/**
* Recursive method to calculates how long a wall would
* have been from a given point in a given direction. This
* is used to prevent very long walls being created.
* @param x X position to start from
* @param y Y position to start from
* @param direction Direction - 0=Up, 1=Right, 2=Down, 3=Left
* @param length Length - initally 0 and incremented by each recursive call
* @return
*/
private int findWallLength(int x, int y, int direction, int length) {
MazeNodes n, n2;
int key, key2;
boolean hadWall = false;
switch(direction) {
case UP:
key = makeKey(x,y-1);
n = (MazeNodes)nodes.get(key);
hadWall = n.isHasWall();
if (!hadWall) {
length = findWallLength(x,y-1,UP,length+1);
}
break;
case DOWN:
key2 = makeKey(x,y+1);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
if (!hadWall) {
length = findWallLength(x,y+1,DOWN,length+1);
}
break;
case LEFT:
key = makeKey(x-1,y);
n = (MazeNodes)nodes.get(key);
hadWall = n.isHasWall();
if (!hadWall) {
length = findWallLength(x-1,y,LEFT,length+1);
}
break;
case RIGHT:
key2 = makeKey(x+1,y);
n2 = (MazeNodes)nodes.get(key2);
hadWall = n2.isHasWall();
if (!hadWall) {
length = findWallLength(x+1,y,DOWN,length+1);
}
break;
}
return length;
}
/**
* Getter for right wall of a given co-ordinate
* @param x X position
* @param y Y position
* @return true if wall exists
*/
public boolean getRightWall(int x, int y) {
MazeNodes n = (MazeNodes)nodes.get(makeKey(x,y));
return n.isRight();
}
/**
* Getter for wall number of right wall for given position
* @param x X position
* @param y Y position
* @return wall number
*/
public int getRightWallNumber(int x, int y) {
MazeNodes n = (MazeNodes)nodes.get(makeKey(x,y));
return n.getRightWallNumber();
}
/**
* Getter for below wall of a given co-ordinate
* @param x X position
* @param y Y position
* @return true if wall exists
*/
public boolean getDownWall(int x, int y) {
MazeNodes n = (MazeNodes)nodes.get(makeKey(x,y));
return n.isDown();
}
/**
* Getter for wall number of below wall for given position
* @param x X position
* @param y Y position
* @return wall number
*/
public int getDownWallNumber(int x, int y) {
MazeNodes n = (MazeNodes)nodes.get(makeKey(x,y));
return n.getDownWallNumber();
}
/**
* Find out if there is a wall in this position
* @param x X position
* @param y Y position
* @return true if wall exists
*/
public boolean getHasWall(int x, int y) {
MazeNodes n = (MazeNodes)nodes.get(makeKey(x,y));
return n.hasWall;
}
/**
* Initialises an empty maze with boundary walls and
* an entrance and exit.
*/
private void initEmptyMaze() {
// Put entry and exit half way down left and right sides
int maze_entrance_y = (int)((size_y-1)/2);
for (int y=0; y<size_y; y++) {
for (int x=0; x<size_x; x++) {
MazeNodes n = new MazeNodes();
// Corners
if (x==0 && y==0) {
// Top left
n.setRight(true);
n.setDown(true);
n.setHasWall(true);
}
else if (x==size_x-1 && y==0) {
// Top right
n.setDown(true);
n.setHasWall(true);
}
else if (x==size_x-1 && y==size_y-1) {
// Bottom right
n.setHasWall(true);
}
else if (x==0 && y==size_y-1) {
// Bottom left
n.setRight(true);
n.setHasWall(true);
}
else if (x==0 && y==maze_entrance_y) {
// Maze Entrance
n.setHasWall(true);
}
else if (x==size_x-1 && y==maze_entrance_y) {
// Maze Exit
n.setHasWall(true);
}
// Edges
else if (y==0) {
// Top
n.setRight(true);
n.setHasWall(true);
}
else if (y==size_y-1) {
// Bottom
n.setRight(true);
n.setHasWall(true);
}
else if (x==0) {
// Left
n.setDown(true);
n.setHasWall(true);
}
else if (x==size_x-1) {
// Right
n.setDown(true);
n.setHasWall(true);
}
else {
// Empty node
availableNodes.add(new Integer(makeKey(x,y)));
}
nodes.add(makeKey(x,y),n);
}
}
}
/**
* Returns a numeric "key" for the given co-ordinates
* @param x X position
* @param y Y position
* @return key
*/
private int makeKey(int x, int y) {
return (y*size_x) + x;
}
/**
* Returns the X position of a "key" value
* @param key Key value
* @return x position of key
*/
private int getKeyX(int key) {
return (key % size_x);
}
/**
* Returns the Y position of a "key" value
* @param key Key value
* @return y position of key
*/
private int getKeyY(int key) {
return (key / size_x);
}
}
syntax highlighted by Code2HTML, v. 0.9.1