/*
* Maze
* Copyright (C) 2000 Paul Davis, pdavis@lpccomp.bc.ca
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/**
* A maze.
* Holds the maze layout, the finish location and the current player location.
* The maze is three dimensions, but acts like a two dimensional maze if
* the Z dimension has a size of 1.
* Each cell contains a bitmap representing which exits are available
* from that cell. The exits are known as XPL,XMI,YPL,YMI,ZPL,ZMI
* representing a plus and minus direction exit in each of the 3 dimensions.
* The maze is created such that adjoining cells share openings so that
* the "doorway" is two directional. There are no exits around the outside
* of the maze. The finish is just a designated cell.
*/
public class Maze implements MazeModel {
private int xdim,ydim,zdim,max;
//private static int[] bias = { 0, 5, 2, 3, 1, 1, 1 };
private static int[] bias = { 0, 100, 100, 100, 100, 1, 1 };
private byte[] maze;
private Coordinate3D finish,current;
private Vector mazeListeners;
/**
* Contruct a new maze with the given dimensions.
* @param xdim The x dimension of the maze.
* @param ydim The y dimension of the maze.
* @param zdim The z dimension of the maze. Use 1 for a 2D maze.
*/
public Maze(int xdim, int ydim, int zdim) {
this.xdim = xdim;
this.ydim = ydim;
this.zdim = zdim;
max = xdim*ydim*zdim;
maze = new byte[max];
finish = null;
current = null;
mazeListeners = new Vector();
create();
}
/**
* Contruct a new maze with the given dimensions.
* @param size The 3D size of the maze.
*/
public Maze(Coordinate3D size) {
this(size.x, size.y, size.z);
}
/**
* Get the size of this maze.
* @return The 3D size of the maze.
*/
public Coordinate3D getSize() {
return new Coordinate3D(xdim,ydim,zdim);
}
/**
* Put or remove a "I've been here" marker in a cell.
* @param position The cell position.
* @param mark True to place a mark, False to remove a mark.
*/
public void setMark(Coordinate3D position, boolean mark) {
if ( mark )
put(position,MazeModel.MARK);
else
maze[position.z*ydim*xdim + position.y*xdim + position.x] &= ~MazeModel.MARK;
}
/**
* Clear the maze layout.
* Fills in all the walls.
*/
private void clearGrid() {
for ( int i=0 ; i<max ; i++ )
maze[i] = MazeModel.WALLS;
}
/**
* Get the given cell walls and status.
* @param x The x co-ordinate.
* @param y The y co-ordinate.
* @param z The z co-ordinate.
* @return The cell status, MARK if an invalid cell co-ordinate.
*/
public byte grid(int x, int y, int z) {
if ( x>=xdim || x<0 || y>=ydim || y<0 || z>=zdim || z<0 )
return(MazeModel.MARK);
return maze[z*ydim*xdim + y*xdim + x];
}
/**
* Get the given cell walls and status.
* @param c The 3D co-ordinate of the desired cell.
* @return The cell status, MARK if an invalid cell co-ordinate.
*/
public byte grid(Coordinate3D c) {
return grid(c.x, c.y, c.z);
}
/**
* Set where the finish cell is.
* @param finish The 3D co-ordinate of the end of the maze.
*/
public void setFinish(Coordinate3D finish) {
this.finish = finish;
fireChange();
}
/**
* Make a random finish location.
*/
public void setRandomFinish() {
Random random = new Random();
finish = new Coordinate3D(
Math.abs(random.nextInt()%xdim),
Math.abs(random.nextInt()%ydim),
Math.abs(random.nextInt()%zdim));
fireChange();
}
/**
* Get the maze finish cell location.
* May be null if one hasn't been set.
*/
public Coordinate3D getFinish() {
return finish;
}
/**
* Get the current player co-ordinate.
* @return The 3D co-ordinate of the player in the maze.
*/
public Coordinate3D getCurrent() {
return current;
}
/**
* Set the current player co-ordinate.
* @param current The 3D co-ordinate of the player in the maze.
*/
public void setCurrent(Coordinate3D current) {
setMark(current,true);
this.current = current;
fireChange();
}
/**
* Check if the given cell has an "I've been here" marker.
* @param position The 3D co-ordinate of the cell to check.
* @return True if a marker has been placed.
*/
public boolean isMarked(Coordinate3D position) {
return ( (grid(position) & MazeModel.MARK) != 0 );
}
/**
* Get a String representation of the given direction.
* @param direction One of MazeModel.XMI,XPL,YMI,YPL,ZMI,ZPL.
* @return A String representation of one of the above.
*/
public static String directionString(byte direction) {
if ( (direction&MazeModel.XMI) != 0 )
return "XMI";
if ( (direction&MazeModel.XPL) != 0 )
return "XPL";
if ( (direction&MazeModel.YMI) != 0 )
return "YMI";
if ( (direction&MazeModel.YPL) != 0 )
return "YPL";
if ( (direction&MazeModel.ZMI) != 0 )
return "ZMI";
if ( (direction&MazeModel.ZPL) != 0 )
return "ZPL";
return "???";
}
/**
* Get a representation of the walls of the current cell.
* @param x The x co-ordinate.
* @param y The x co-ordinate.
* @param z The x co-ordinate.
* @return A String made up of X+,X-,Y+,Y- etc.
*/
private String gridString(int x, int y, int z) {
byte val = grid(x,y,z);
StringBuffer out = new StringBuffer();
if ( (val & MazeModel.XMI) != 0 )
out.append("X-");
if ( (val & MazeModel.XPL) != 0 )
out.append("X+");
if ( (val & MazeModel.YMI) != 0 )
out.append("Y-");
if ( (val & MazeModel.YPL) != 0 )
out.append("Y+");
if ( (val & MazeModel.ZMI) != 0 )
out.append("Z-");
if ( (val & MazeModel.ZPL) != 0 )
out.append("Z+");
if ( (val & MazeModel.MARK) != 0 )
out.append("MARK");
return out.toString();
}
/**
* Store the value (MazeModel.XPL etc.) into the cell.
* @param x The x co-ordinate.
* @param y The x co-ordinate.
* @param z The x co-ordinate.
* @param value The bitmap value: XPL, MARK, etc.
*/
private final void put(int x,int y,int z,byte value) {
maze[z*ydim*xdim + y*xdim + x] |= value;
}
/**
* Store the value (XPL etc.) into the cell.
* @param pos The 3D co-ordinate.
* @param value The bitmap value: XPL, MARK, etc.
*/
private final void put(Coordinate3D pos,byte value) {
maze[pos.z*ydim*xdim + pos.y*xdim + pos.x] |= value;
}
/**
* Count how many open walls there are in the cell value.
* @param val The internal value representing the cell.
* @return The number of open walls (0 thru 6).
*/
public static final int count(int val) {
int cnt;
cnt = 0;
val &= 077;
cnt += val&1;
cnt += (val>>=1)&1;
cnt += (val>>=1)&1;
cnt += (val>>=1)&1;
cnt += (val>>=1)&1;
cnt += (val>>=1)&1;
//System.out.println("count: val " +
// String.valueOf(val) +
// "=" + String.valueOf(cnt));
return cnt;
}
/**
* Create a random maze.
*/
public void create() {
int[] listx,listy,listz;
int cells = 1;
int top = 0;
int x,y,z;
int tmp,pickcount,cnt,choice;
int[] pick = new int[6];
Random random = new Random();
listx = new int[max];
listy = new int[max];
listz = new int[max];
listx[0] = (xdim-1)/2;
listy[0] = (ydim-1)/2;
listz[0] = (zdim-1)/2;
clearGrid();
while ( top >= 0 ) {
x = listx[top];
y = listy[top];
z = listz[top];
//System.out.println("Create at " +
// String.valueOf(x) +
// "," + String.valueOf(y) +
// "," + String.valueOf(z) +
// " level " + String.valueOf(top) +
// " grid " + gridString(x,y,z));
if ( grid(x,y,z) != 0 ) {
top--;
continue;
}
if ( cells > 1 ) {
pickcount = cnt = 0;
if ( (tmp = bias[count(grid(x+1,y,z))]) != 0)
cnt++;
pick[0] = (pickcount += tmp);
if ( (tmp = bias[count(grid(x-1,y,z))]) != 0)
cnt++;
pick[1] = (pickcount += tmp);
if ( (tmp = bias[count(grid(x,y+1,z))]) != 0)
cnt++;
pick[2] = (pickcount += tmp);
if ( (tmp = bias[count(grid(x,y-1,z))]) != 0)
cnt++;
pick[3] = (pickcount += tmp);
if ( (tmp = bias[count(grid(x,y,z+1))]) != 0)
cnt++;
pick[4] = (pickcount += tmp);
if ( (tmp = bias[count(grid(x,y,z-1))]) != 0)
cnt++;
pick[5] = (pickcount += tmp);
}
else {
for ( int i=0 ; i<4 ; i++ )
pick[i] = i+1;
pickcount = cnt = 4;
}
if ( cnt == 0 ) {
top--;
continue;
}
choice = Math.abs(random.nextInt()%pickcount);
//System.out.println("choice=" + String.valueOf(choice));
//System.out.println("pick 0=" + String.valueOf(pick[0]) +
// " 1=" + String.valueOf(pick[1]) +
// " 2=" + String.valueOf(pick[2]) +
// " 3=" + String.valueOf(pick[3]) +
// " 4=" + String.valueOf(pick[4]) +
// " 5=" + String.valueOf(pick[5]));
if ( pick[0] > choice ) {
put(x,y,z,MazeModel.XPL);
put(x+1,y,z,MazeModel.XMI);
}
else if ( pick[1] > choice ) {
put(x,y,z,MazeModel.XMI);
put(x-1,y,z,MazeModel.XPL);
}
else if ( pick[2] > choice ) {
put(x,y,z,MazeModel.YPL);
put(x,y+1,z,MazeModel.YMI);
}
else if ( pick[3] > choice ) {
put(x,y,z,MazeModel.YMI);
put(x,y-1,z,MazeModel.YPL);
}
else if ( pick[4] > choice ) {
put(x,y,z,MazeModel.ZPL);
put(x,y,z+1,MazeModel.ZMI);
}
else if ( pick[5] > choice ) {
put(x,y,z,MazeModel.ZMI);
put(x,y,z-1,MazeModel.ZPL);
}
/*
printf("new val %o\n",grid(x,y,z));
*/
if ( grid(x-1,y,z) == MazeModel.WALLS ) {
listx[top] = x-1; listy[top] = y; listz[top] = z;
top++;
}
if ( grid(x+1,y,z) == MazeModel.WALLS ) {
listx[top] = x+1; listy[top] = y; listz[top] = z;
top++;
}
if ( grid(x,y-1,z) == MazeModel.WALLS ) {
listx[top] = x; listy[top] = y-1; listz[top] = z;
top++;
}
if ( grid(x,y+1,z) == MazeModel.WALLS ) {
listx[top] = x; listy[top] = y+1; listz[top] = z;
top++;
}
if ( grid(x,y,z-1) == MazeModel.WALLS ) {
listx[top] = x; listy[top] = y; listz[top] = z-1;
top++;
}
if ( grid(x,y,z+1) == MazeModel.WALLS ) {
listx[top] = x; listy[top] = y; listz[top] = z+1;
top++;
}
//System.out.println("top=" + String.valueOf(top));
top--;
cells++;
}
fireChange();
}
/**
* Return the opposite direction.
* @param value One of XPL,XMI,YPL,YMI,ZPL,ZMI.
* @return One of XMI,XPL,YMI,YPL,ZMI,ZPL.
*/
public static byte invert(byte value) {
switch (value) {
case MazeModel.XPL: return(MazeModel.XMI);
case MazeModel.XMI: return(MazeModel.XPL);
case MazeModel.YPL: return(MazeModel.YMI);
case MazeModel.YMI: return(MazeModel.YPL);
case MazeModel.ZPL: return(MazeModel.ZMI);
case MazeModel.ZMI: return(MazeModel.ZPL);
}
return 0;
}
/**
* Move between cells in a maze.
* Does not check for walls or maze edges.
* @param c The 3D co-ordinate to start from.
* @param direction The direction to go, one of XPL,XMI etc.
* @return The ending 3D co-ordinate.
*/
public static Coordinate3D forward(Coordinate3D c, byte direction) {
switch (direction) {
case MazeModel.XPL: c.x++; break;
case MazeModel.XMI: c.x--; break;
case MazeModel.YPL: c.y++; break;
case MazeModel.YMI: c.y--; break;
case MazeModel.ZPL: c.z++; break;
case MazeModel.ZMI: c.z--; break;
}
return c;
}
/**
* Check and see if movement is possible.
* @param current The 3D co-ordinate to start from.
* @param direction The direction to go, one of XPL,XMI etc.
* @return True if movement possible, false if blocked by a wall.
*/
public boolean isOpen(Coordinate3D current,byte direction) {
return (grid(current) & direction) != 0;
}
/**
* Solve the maze from a given start position.
* @param start The 3D co-ordinate to start from.
* @return A Stack of 3D co-ordinates giving the path from
* the given start to the known finish.
*/
public Stack solve(Coordinate3D start) {
Stack stack = new Stack();
Coordinate3D current = start;
solveCell(stack,current,(byte)0);
for ( int i=0 ; i<stack.size() ; i++ ) {
current = (Coordinate3D)stack.elementAt(i);
System.out.println(String.valueOf(i) + " " +
current.toString());
}
return stack;
}
/**
* A recursive routine to find the finish.
* @param stack The current Stack of moves from the start.
* @param position The current cell position in the search.
* @param dir The direction we used to move into the cell
* to prevent overlapping the path.
* @return True if a path to the finish was found.
*/
private boolean solveCell(Stack stack,Coordinate3D position,byte dir) {
System.out.println("searching " + position.toString() +
" " + directionString(dir));
stack.push(position);
setMark(position,true);
if ( position == finish )
return true;
byte from = invert(dir);
if ( isOpen(position,MazeModel.XPL) && from != MazeModel.XPL )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.XPL),MazeModel.XPL) )
return true;
if ( isOpen(position,MazeModel.XMI) && from != MazeModel.XMI )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.XPL),MazeModel.XMI) )
return true;
if ( isOpen(position,MazeModel.YPL) && from != MazeModel.YPL )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.YPL),MazeModel.YPL) )
return true;
if ( isOpen(position,MazeModel.YMI) && from != MazeModel.YMI )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.YMI),MazeModel.YMI) )
return true;
if ( isOpen(position,MazeModel.ZPL) && from != MazeModel.XPL )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.ZPL),MazeModel.ZPL) )
return true;
if ( isOpen(position,MazeModel.ZMI) && from != MazeModel.ZMI )
if ( solveCell(stack,forward(new Coordinate3D(position),MazeModel.ZMI),MazeModel.ZMI) )
return true;
stack.pop();
setMark(position,false);
return false;
}
/**
* Add a MazeListener.
* An event is fired when the maze is created or when the
* finish or current positions change.
* @param l A MazeListener to listen for maze changes.
*/
public void addMazeListener(MazeListener l) {
mazeListeners.addElement(l);
}
/**
* Remove a MazeListener.
* @param l The MazeListener to remove.
*/
public void removeMazeListener(MazeListener l) {
mazeListeners.removeElement(l);
}
/**
* Fire a change in the maze.
*/
protected void fireChange() {
for ( int i=mazeListeners.size()-1 ; i>=0 ; i-- ) {
MazeListener l = (MazeListener)mazeListeners.elementAt(i);
l.mazeChanged(new EventObject(this));
}
}
}