|
import java.util.Collections;
|
import java.util.Arrays;
|
|
/*
|
* recursive backtracking algorithm
|
* shamelessly borrowed from the ruby at
|
* http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
|
*/
|
public class Maze
|
{
|
public interface Parse
|
{
|
void Tile(int i, int j, boolean north, boolean east, boolean south, boolean west);
|
};
|
|
private int dimx;
|
private int dimy;
|
private byte[][] maze;
|
|
public Maze(int x, int y)
|
{
|
this.dimx = x;
|
this.dimy = y;
|
maze = new byte[this.dimx][this.dimy];
|
generateMaze(0, 0);
|
}
|
|
public void Display(Parse p)
|
{
|
for (int j = 0; j < dimy; j++)
|
{
|
for (int i = 0; i < dimx; i++)
|
{
|
boolean n = (maze[i][j] & 1) == 0;
|
boolean e = true;
|
if (i < dimx-1)
|
e = (maze[i+1][j] & 8) == 0;
|
boolean w = (maze[i][j] & 8) == 0;
|
boolean s = true;
|
if (j < dimy-1)
|
s = (maze[i][j+1] & 1) == 0;
|
p.Tile(i, j, n, e, s, w);
|
}
|
}
|
}
|
|
public void display()
|
{
|
for (int j = 0; j < dimy; j++)
|
{
|
// draw the north edge
|
for (int i = 0; i < dimx; i++)
|
{
|
System.out.print((maze[i][j] & 1) == 0 ? "+---" : "+ ");
|
}
|
System.out.println("+");
|
// draw the west edge
|
for (int i = 0; i < dimx; i++)
|
{
|
System.out.print((maze[i][j] & 8) == 0 ? "| " : " ");
|
}
|
System.out.println("|");
|
}
|
|
// draw the bottom line
|
for (int j = 0; j < dimx; j++)
|
{
|
System.out.print("+---");
|
}
|
System.out.println("+");
|
}
|
|
private void generateMaze(int cx, int cy)
|
{
|
DIR[] dirs = DIR.values();
|
Collections.shuffle(Arrays.asList(dirs)); // Works because of elementData = collection.toArray() in ArrayList constructor.
|
for (DIR dir : dirs)
|
{
|
int nx = cx + dir.dx;
|
int ny = cy + dir.dy;
|
if (between(nx, dimx) && between(ny, dimy) && (maze[nx][ny] == 0))
|
{
|
maze[cx][cy] |= dir.bit;
|
maze[nx][ny] |= dir.opposite.bit;
|
generateMaze(nx, ny);
|
}
|
}
|
}
|
|
private static boolean between(int v, int upper)
|
{
|
return (v >= 0) && (v < upper);
|
}
|
|
private enum DIR
|
{
|
N(1, 0, -1), E(2, 1, 0), S(4, 0, 1), W(8, -1, 0);
|
|
private final int bit;
|
private final int dx;
|
private final int dy;
|
private DIR opposite;
|
|
// use the static initializer to resolve forward references
|
static
|
{
|
N.opposite = S;
|
S.opposite = N;
|
E.opposite = W;
|
W.opposite = E;
|
}
|
|
private DIR(int bit, int dx, int dy)
|
{
|
this.bit = bit;
|
this.dx = dx;
|
this.dy = dy;
|
}
|
};
|
|
public static void main(String[] args)
|
{
|
int x = args.length >= 1 ? (Integer.parseInt(args[0])) : 3;
|
int y = args.length == 2 ? (Integer.parseInt(args[1])) : 3;
|
Maze maze = new Maze(x, y);
|
maze.display();
|
}
|
}
|
