/*
* @(#)Board.java 1.27 02/08/13 @(#)
*
* Copyright (c) 1999-2002 Sun Microsystems, Inc. All rights reserved.
* PROPRIETARY/CONFIDENTIAL
* Use is subject to license terms.
*/
package example.pushpuzzle;
import javax.microedition.lcdui.*;
/**
* The class Board knows how the pieces move, handles undo, and
* handles reading of screens.
*/
public class Board {
private int level;
private byte[] array;
private byte[] pathmap; // used for runTo to find shortest path
private int width, height;
private int pusher; // position of the pusher at index into array
private int packets = 0; // total number of packets
private int stored = 0; // number of packets in Stores
private byte[] moves; // recorded moves
private int nmoves; // number of moves executed
private int npushes; // number of pushes executed
// Move directions
public static final int LEFT = 0;
public static final int RIGHT = 3;
public static final int UP = 1;
public static final int DOWN = 2;
public static final int MOVEPACKET = 4;
// Bit definitions for pieces of each board position
public static final byte GROUND = 0; // If nothing there
public static final byte STORE = 1; // If it is a storage place
public static final byte PACKET = 2; // If it has a packet
public static final byte WALL = 4; // If it is a wall
public static final byte PUSHER = 8; // If the pusher is there
/**
* Creates new Board initialized to a simple puzzle.
*/
public Board() {
moves = new byte[200];
screen0();
}
/**
* Create the hard coded simple game board.
*/
public void screen0() {
width = 9;
height = 7;
array = new byte[width * height];
level = 0;
nmoves = 0;
npushes = 0;
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
byte t = (x == 0 || y == 0 ||
x == width - 1 || y == height - 1) ?
WALL : GROUND;
set(x, y, t);
}
}
packets = 2;
stored = 0;
set(2, 2, PACKET);
set(4, 4, PACKET);
set(4, 2, STORE);
set(6, 4, STORE);
pusher = index(1, 1);
}
/**
* Move the pusher in the direction indicated.
* If there is a wall, don't move.
* if there is a packet in that direction, try to move it.
* @param move the direction; one of LEFT, RIGHT, UP, DOWN
* @return the direction actually moved, -1 if not moved
*/
public int move(int move) {
int obj = pusher + indexOffset(move);
// Handle the simple cases
if ((array[obj] & WALL) != 0)
return -1;
int m = movePacket(obj, move);
if (m < 0)
return -1; // If can't move packet, done!
pusher = obj; // move the pusher to the new spot
saveMove(m);
return m;
}
/**
* Move the packet in the direction indicated relative to
* the pusher. If it fits into a store position remember.
* @return -1 if can't be moved or the updated move
* including the packet flag if there was a packet to move.
*/
private int movePacket(int index, int move) {
if ((array[index] & PACKET) == 0)
return move; // no packet to move
int dest = index + indexOffset(move);
if (array[dest] > STORE)
return -1; // can't move packet into next spot.
// Remove packet from current location
array[index] &= ~PACKET;
if ((array[index] & STORE) != 0)
stored--;
// Insert packet into new location
array[dest] |= PACKET;
if ((array[dest] & STORE) != 0)
stored++;
npushes++; // count pushes done
return move + MOVEPACKET;
}
/*
* Save a move, extending the array if necessary.
*/
private void saveMove(int move) {
if (nmoves >= moves.length) {
byte[] n = new byte[moves.length + 50];
System.arraycopy(moves, 0, n, 0, moves.length);
moves = n;
}
moves[nmoves++] = (byte)move;
}
/**
* Undo the most recent move
* @return the move undone; if none -1 is returned;
* See LEFT, RIGHT, UP, DOWN, and MOVEPACKET
*/
public int undoMove() {
if (nmoves <= 0)
return -1;
int move = moves[--nmoves];
int rev = (move & 3) ^ 3; // reverse the direction
int back = pusher + indexOffset(rev);
if ((move & MOVEPACKET) != 0) {
npushes--; // "unpush"
movePacket(pusher + indexOffset(move), rev); // move packet
}
pusher = back;
return move;
}
/**
* Determine if the screen has been solved.
*/
public boolean solved() {
return packets == stored;
}
/**
* Move the player to the position (x,y), if possible. Return
* the direction it moved if successful, otherwise -1.
* The position (x,y) must be empty.
* @param x window coordinate
* @param y window coordinate
* @return the direction that it moved, -1 is not moved;
* See LEFT, RIGHT, UP, DOWN, MOVEPACKET
*/
public int runTo(int x, int y, int max) {
int target = index(x, y);
if (target < 0 || target >= array.length)
return -1;
if (target == pusher)
return -1; // already there
/* Fill the path map */
if (pathmap == null || pathmap.length != array.length) {
pathmap = new byte[array.length];
}
// Fill with unset value.
for (int i = 0; i < pathmap.length; i++)
pathmap[i] = 127;
// flood fill search to find a shortest path to the push point.
findTarget(target, (byte)0);
/*
* if we didn't make it back to the players position,
* there is no valid path to that place.
*/
if (pathmap[pusher] == 127) {
return -1;
} else {
// We made it back, so let's walk the path we just built up
// Save the final move to return
int pathlen = pathmap[pusher];
int pathmin = pathlen - max;
int dir = -1;
for (pathlen--; pathlen >= pathmin; pathlen--) {
if (pathmap[pusher - 1] == pathlen) {
dir = LEFT;
saveMove(dir);
pusher--;
} else if (pathmap[pusher + 1] == pathlen) {
dir = RIGHT;
saveMove(dir);
pusher++;
} else if (pathmap[pusher - width] == pathlen) {
dir = UP;
saveMove(dir);
pusher -= width;
} else if (pathmap[pusher + width] == pathlen) {
dir = DOWN;
saveMove(dir);
pusher += width;
} else {
/*
* if we get here, something is SERIOUSLY wrong,
* so we should abort
*/
throw new RuntimeException("runTo abort");
}
}
return dir;
}
}
/**
* Find the shortest path to the pusher via a fill search algorithm
*/
private void findTarget(int t, byte pathlen) {
if (array[t] > STORE)
return; // Either a wall or looped back to player
// Already tried here and this way is longer
if (pathmap[t] <= pathlen)
return;
pathmap[t] = pathlen++; // set path length to this location
if (t == pusher)
return;
findTarget(t - 1, pathlen); // to previous cell
findTarget(t + 1, pathlen); // to next cell
findTarget(t - width, pathlen); // to previous row
findTarget(t + width, pathlen); // to next row
}
/**
* Return the pieces at the location.
* @param x location in the board.
* @param y location in the board.
* @return flags indicating what pieces are in this board location.
* Bit flags; combinations of WALL, PUSHER, STORE, PACKET.
*/
public byte get(int x, int y) {
int offset = index(x, y);
if (offset == pusher)
return (byte)(array[offset] | PUSHER);
else
return array[offset];
}
/**
* Set the value of the location.
*/
private void set(int x, int y, byte value) {
array[index(x, y)] = value;
}
/**
* Compute the index in the array of the x, y location.
*/
private int index(int x, int y) {
if (x < 0 || x >= width ||
y < 0 || y >= height)
return -1;
return y * width + x;
}
/**
* Get the location of the pusher.
* It is returned as an int with the lower 16 bits being
* the x index and the upper 16 bits being the y index.
* @return the encoded location of the pusher.
*/
public int getPusherLocation() {
int x = pusher % width;
int y = pusher / width;
return (y << 16) + x;
}
/**
* Compute the offset in the array of the cell relative
* to the current pusher location in the direction of the move.
* Note: the walls around the edge always make a +/- guard band.
* Also, the order of evaluation should never try to get to +/- 2.
*/
private int indexOffset(int move) {
switch (move & 3) {
case LEFT:
return -1;
case RIGHT:
return +1;
case UP:
return -width;
case DOWN:
return +width;
}
return 0;
}
/**
* Read a board from a stream.
* Read it into a fixed size array and then shrink to fit.
*/
public void read(java.io.InputStream is, int l) {
final int W = 20;
final int H = 20;
byte[] b = new byte[W * H];
// Add resize code later.
int c, w = 0;
int x = 0, y = 0, xn = 0, yn = 0, npackets = 0;
try {
while ((c = is.read()) != -1) {
switch (c) {
case '\n':
if (x > w) {
w = x;
}
y++;
x = 0;
break;
case '$':
b[y * W + x++] = PACKET;
npackets++;
break;
case '#':
b[y * W + x++] = WALL;
break;
case ' ':
b[y * W + x++] = GROUND;
break;
case '.':
b[y * W + x++] = STORE;
break;
case '*':
b[y * W + x] = PACKET;
b[y * W + x++] |= STORE;
npackets++;
stored++;
break;
case '+': // player and store in same place
b[y * W + x++] = STORE;
case '@':
xn = x;
yn = y;
x++;
break;
}
}
} catch (java.io.IOException ex) {
ex.printStackTrace();
}
if (y > 0) {
array = new byte[w * y];
if (y > w) { // Switch x for y while copying
width = y;
height = w;
for (y = 0; y < width; y++) {
for (x = 0; x < w; x++) {
array[index(y, x)] = b[y * W + x];
}
}
pusher = index(yn, xn);
} else {
width = w;
height = y;
array = new byte[width * height];
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
array[index(x, y)] = b[y * W + x];
}
}
pusher = index(xn, yn);
}
stored = 0;
packets = npackets;
level = l;
nmoves = 0;
npushes = 0;
}
}
/**
* Get the width of the game board.
*/
public int getWidth() {
return width;
}
/**
* Get the height of the board.
*/
public int getHeight() {
return height;
}
/**
* Get the number of moves to get this far.
*/
public int getMoves() {
return nmoves;
}
/**
* Get the number of packets pushed around.
*/
public int getPushes() {
return npushes;
}
/**
* Get the number of packets stored.
*/
public int getStored() {
return stored;
}
/**
* Convert a left/right direction into an offset.
*/
private int dx(int dir) {
if (dir == LEFT)
return -1;
if (dir == RIGHT)
return +1;
return 0;
}
/**
* Convert a up/down direction into an offset.
*/
private int dy(int dir) {
if (dir == UP)
return -1;
if (dir == DOWN)
return +1;
return 0;
}
}
|
