/* * * Copyright ? 2007 Sun Microsystems, Inc. All rights reserved. * 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 {    // 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    private int level;    private byte[] array;    private byte[] pathmap; // used for runTo to find shortest path    private int width;    private int 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    /**     * 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;        }        // avoiding ArrayIndexOutOfBoundException        if ((t - 1) >= 0) {            findTarget(t - 1, pathlen); // to previous cell        }        if ((t + 1) < array.length) {            findTarget(t + 1, pathlen); // to next cell        }        if ((t - width) >= 0) {            findTarget(t - width, pathlen); // to previous row        }        if ((t + width) < array.length) {            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;        // Add resize code later.        int w = 0;        int x = 0;        int y = 0;        int xn = 0;        int yn = 0;        int 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;    }}