rushhour
Class RushHourGameBoard

java.lang.Object
  extended by rushhour.RushHourGameBoard

public class RushHourGameBoard
extends java.lang.Object

A game gameBoard for the game Rush Hour. Vehicles, known as cars and trucks, can be placed on the game gameBoard and shifted until the red car is able to exit through the edge at (3, 6).

Vehicles (cars or trucks) can be added to the game gameBoard at specified locations on the gameBoard. When a vehicle is added to the gameBoard, the (x, y) coordinates given are assumed to be from (1, 1) being in the upper-left corner of the gameBoard, and the coordinate given is assumed to be the top-most, left-most position of the vehicle.

It's important to realize that coordinates may change frequently in the way they are displayed depending on whether a location on the gameBoard (where (1, 1) is the upper-left corner) or an index (where (0, 0) is the upper-left corner) is displayed. For errors specifically, indeces are used for tracking errors within the actual array, but when information regarding the position is output to the user normally, it should be in a location where (1, 1) is the upper-left corner.

Once a game baord is constructed, the vehicles on the gameBoard can be moved around in valid directions. The solve() method can be called to find the minimum number of moves required to solve the given game gameBoard. If the solve() method cannot find a solution, false is returned and the game gameBoard is deemed unsolvable.


Field Summary
 int boardHeight
          The boardHeight of the game gameBoard.
 int boardWidth
          The boardWidth of the game gameBoard.
 
Constructor Summary
RushHourGameBoard()
          Construct the game gameBoard.
 
Method Summary
 RushHourVehicle addCar(java.lang.String color, java.lang.String orientation, int x, int y)
          Add a car to the game gameBoard at location (x, y).
 RushHourVehicle addTruck(java.lang.String color, java.lang.String orientation, int x, int y)
          Add a truck to the game gameBoard at location (x, y).
 RushHourVehicle addVehicle(java.lang.String type, java.lang.String color, java.lang.String orientation, int x, int y)
          Add a vehicle to the game gameBoard at location (x, y).
 boolean boardEqual(RushHourGameBoard otherBoard)
          Checks the current game board against a passed in game board, comparing the states of each car.
 boolean canMoveDown(RushHourVehicle vehicle, int num)
          Checks to see if the specified vehicle can move num space(s) down.
 boolean canMoveLeft(RushHourVehicle vehicle, int num)
          Checks to see if the specified vehicle can move num space(s) left.
 boolean canMoveRight(RushHourVehicle vehicle, int num)
          Checks to see if the specified vehicle can move num space(s) right.
 boolean canMoveUp(RushHourVehicle vehicle, int num)
          Checks to see if the specified vehicle can move num space(s) up.
 RushHourGameBoard getBoardFromHash(java.lang.String hash)
          Constructs a game gameBoard object tempBoard of a given hash state.
 java.util.HashMap<java.lang.String,java.lang.String> getDirections()
          Retrieve the hash map that contains the directions for reaching each valid move.
 RushHourVehicle[][] getGameBoard()
          Retrieve current game gameBoard.
 java.lang.String getHash()
          Retrieve the hash representation of the current state of the game gameBoard.
 java.lang.String getInitialState()
          Retrieve the hash representation of the initial state of the gameBoard.
 int getNumVehicles()
          Retrieve the number of vehicles on the gameBoard.
 java.util.HashMap<java.lang.String,java.lang.String> getValidMoves()
          Retrieve the hash map that contains the solutions each move in the move table.
 RushHourVehicle getVehicleAtIndex(int i)
          Retrieve the vehicle at index i from the array of vehicles known to be on the gameBoard.
 RushHourVehicle getVehicleAtLocation(int x, int y)
          Check for a vehicle at location (x, y) on the game gameBoard.
 RushHourVehicle getVehicleByColor(java.lang.String color)
          Retrieves the vehicle of the specified color on the gameBoard.
 java.util.Vector<RushHourVehicle> getVehiclesList()
          Retrieve the list of vehicles known to be on the gameBoard.
 java.lang.String getWinningState()
          Retrieve the hash representation of the state of the gameBoard when the red car reaches the exit.
 void initGameBoard()
          Resets the game board to an empty state.
 boolean isSolved()
          Check to see if the red car is in a position that implies the game gameBoard is solved.
 void moveDown(RushHourVehicle vehicle, int num)
          Move the specified vehicle down num space(s).
 void moveLeft(RushHourVehicle vehicle, int num)
          Move the specified vehicle left num space(s).
 boolean moveRight(RushHourVehicle vehicle, int num)
          Move the specified vehicle right num space(s).
 void moveUp(RushHourVehicle vehicle, int num)
          Move the specified vehicle up num space(s).
 void removeCar(RushHourVehicle car)
          Remove the specified car from the game gameBoard.
 void removeTruck(RushHourVehicle truck)
          Remove the specified truck from the game gameBoard.
 void removeVehicle(RushHourVehicle vehicle)
          Remove the vehicle of the specified color from the game gameBoard and from the list of vehicles.
 void setBoardFromHash(java.lang.String hash)
          Sets the current game board (represented as an array of vehicles) to the game board represented from the passed in hash state.
 void setBoardHeight(int height)
          Set the gameBoard boardHeight.
 void setBoardObject(RushHourGameBoard newGameBoard)
          Resets the game board and starts it at the state given by the passed in game board.
 void setBoardWidth(int width)
          Set the gameBoard boardWidth.
 void setGameBoard(RushHourVehicle[][] gameBoard)
          Set the game board to the passed in game board.
 boolean solve()
          Solve the game gameBoard in the least number of moves possible using a hash map.
 boolean solveFast()
          Solves the game board through string parsing of the hash representation of each board state instead of creating a new game board object at each individual state (since the overhead cost of that is great).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

boardWidth

public int boardWidth
The boardWidth of the game gameBoard.


boardHeight

public int boardHeight
The boardHeight of the game gameBoard.

Constructor Detail

RushHourGameBoard

public RushHourGameBoard()
Construct the game gameBoard.

Method Detail

initGameBoard

public void initGameBoard()
Resets the game board to an empty state.


solve

public boolean solve()
Solve the game gameBoard in the least number of moves possible using a hash map.

The algorithm solved the Rush Hour game puzzle in optimal time. It implements a triply nested loop. The first layer iterates through all possible permutations the game gameBoard can appear in before it is solved. The second layer of the loops through each car on the game gameBoard at the given gameBoard state from the first loop. The third loop attempts to move the given car from the second loop as many spaces as possible in each given direction, adding those further moves as new states to evaluate in the first loop.

Since this algorithm creates a new game board object at each state of the board, the overhead cost of this object creation may cause the algorithm to run slow. If speed is imperative, use the solveFast() method, which implements the same algorithm but parses the hash map differently and can solve more quickly.

This method manipulates the actual game board object. The game board will represent the winning state upon completion of the solve() method. If a solve is desired by the actual game board object should not be manipulated, use the solveFast() method.

Returns:
True if the gameBoard was solved, false if it was unsolvable.

solveFast

public boolean solveFast()
Solves the game board through string parsing of the hash representation of each board state instead of creating a new game board object at each individual state (since the overhead cost of that is great). Use if the solve time is consistently longer than expected (which, ideally, should never ben more than a few seconds). This method is most necessarily used from the applet.

Unlike the solve() method, this method does NOT manipulate the actual game board. If the game board should represent the winning state, a new game board object will have to be created from the final board hash state.

The winning state will still be stored in winningState, so the game board can be set to the winning state using setBoardFromHash() and passing the method the return value of getWinningState().

Returns:
True if the gameBoard was solved, false if it was unsolvable.

setBoardHeight

public void setBoardHeight(int height)
Set the gameBoard boardHeight.

Parameters:
height - The new gameBoard boardHeight.

setBoardWidth

public void setBoardWidth(int width)
Set the gameBoard boardWidth.

Parameters:
width - The new gameBoard boardWidth.

getValidMoves

public java.util.HashMap<java.lang.String,java.lang.String> getValidMoves()
Retrieve the hash map that contains the solutions each move in the move table. This should not be called before the solve() method has been called.

Returns:
The valid moves hash map.

getDirections

public java.util.HashMap<java.lang.String,java.lang.String> getDirections()
Retrieve the hash map that contains the directions for reaching each valid move. This should not be called before the solve() method has been called.

Returns:
The directions for valid moves hash map table.

getInitialState

public java.lang.String getInitialState()
Retrieve the hash representation of the initial state of the gameBoard. This should not be called before the solve() method has been called.

Returns:
The hash representation of the initial state of the gameBoard.

getWinningState

public java.lang.String getWinningState()
Retrieve the hash representation of the state of the gameBoard when the red car reaches the exit. This should not be called before the solve() method has been called.

Returns:
The hash representation of the state of the gameBoard when the red car reaches the exit.

getHash

public java.lang.String getHash()
Retrieve the hash representation of the current state of the game gameBoard.

Returns:
The current state of the gameBoard in its hash representation.

getBoardFromHash

public RushHourGameBoard getBoardFromHash(java.lang.String hash)
Constructs a game gameBoard object tempBoard of a given hash state.

Parameters:
hash - The given hash state to construct into a gameBoard object.
Returns:
An object of the game gameBoard represented in the hash state.

setBoardFromHash

public void setBoardFromHash(java.lang.String hash)
Sets the current game board (represented as an array of vehicles) to the game board represented from the passed in hash state. This is used if you want to force the game board to a specific state, but you want to keep all other states of the game board object the same (for instance, the variables for solution directions).

Parameters:
hash - The given hash state to construct into the game board array.

setBoardObject

public void setBoardObject(RushHourGameBoard newGameBoard)
Resets the game board and starts it at the state given by the passed in game board.

Parameters:
newGameBoard - The new game board to replace the old one.

isSolved

public boolean isSolved()
Check to see if the red car is in a position that implies the game gameBoard is solved.

Returns:
True if the gameBoard is in a solved state, false otherwise.

boardEqual

public boolean boardEqual(RushHourGameBoard otherBoard)
Checks the current game board against a passed in game board, comparing the states of each car.

Parameters:
otherBoard - The game board to be compared to.
Returns:
True if the game boards are not equivalent, false otherwise.

canMoveLeft

public boolean canMoveLeft(RushHourVehicle vehicle,
                           int num)
Checks to see if the specified vehicle can move num space(s) left.

Parameters:
vehicle - The vehicle to check if it can be moved.
num - The number of spaces to move the vehicle.
Returns:
True if the vehicle can be moved, false otherwise.

moveLeft

public void moveLeft(RushHourVehicle vehicle,
                     int num)
              throws IllegalBoardMoveException
Move the specified vehicle left num space(s).

Parameters:
vehicle - The vehicle to be moved down.
num - The number of spaces to move the vehicle.
Throws:
IllegalBoardMoveException - The specified vehicle can is not able to move in this direction due to the end of the gameBoard or another vehicle being in the way.

canMoveRight

public boolean canMoveRight(RushHourVehicle vehicle,
                            int num)
Checks to see if the specified vehicle can move num space(s) right.

Parameters:
vehicle - The vehicle to check if it can be moved.
num - The number of spaces to move the vehicle.
Returns:
True if the vehicle can be moved, false otherwise.

moveRight

public boolean moveRight(RushHourVehicle vehicle,
                         int num)
                  throws IllegalBoardMoveException
Move the specified vehicle right num space(s).

Parameters:
vehicle - The vehicle to be moved down.
num - The number of spaces to move the vehicle.
Returns:
True if the car moved to the right is the red car and has reached the right side of the gameBoard, false otherwise.
Throws:
IllegalBoardMoveException - The specified vehicle can is not able to move in this direction due to the end of the gameBoard or another vehicle being in the way.

canMoveUp

public boolean canMoveUp(RushHourVehicle vehicle,
                         int num)
Checks to see if the specified vehicle can move num space(s) up.

Parameters:
vehicle - The vehicle to check if it can be moved.
num - The number of spaces to move the vehicle.
Returns:
True if the vehicle can be moved, false otherwise.

moveUp

public void moveUp(RushHourVehicle vehicle,
                   int num)
            throws IllegalBoardMoveException
Move the specified vehicle up num space(s).

Parameters:
vehicle - The vehicle to be moved down.
num - The number of spaces to move the vehicle.
Throws:
IllegalBoardMoveException - The specified vehicle can is not able to move in this direction due to the end of the gameBoard or another vehicle being in the way.

canMoveDown

public boolean canMoveDown(RushHourVehicle vehicle,
                           int num)
Checks to see if the specified vehicle can move num space(s) down.

Parameters:
vehicle - The vehicle to check if it can be moved.
num - The number of spaces to move the vehicle.
Returns:
True if the vehicle can be moved, false otherwise.

moveDown

public void moveDown(RushHourVehicle vehicle,
                     int num)
              throws IllegalBoardMoveException
Move the specified vehicle down num space(s).

Parameters:
vehicle - The vehicle to be moved down.
num - The number of spaces to move the vehicle.
Throws:
IllegalBoardMoveException - The specified vehicle can is not able to move in this direction due to the end of the gameBoard or another vehicle being in the way.

getGameBoard

public RushHourVehicle[][] getGameBoard()
Retrieve current game gameBoard.

Returns:
The game gameBoard.

setGameBoard

public void setGameBoard(RushHourVehicle[][] gameBoard)
Set the game board to the passed in game board. This can be highgly dangerous.

Parameters:
gameBoard - The new game board.

getVehicleAtLocation

public RushHourVehicle getVehicleAtLocation(int x,
                                            int y)
                                     throws OffGameBoardException
Check for a vehicle at location (x, y) on the game gameBoard.

Parameters:
x - The x-coordinate to check for a vehicle.
y - The y-coordinate to check for a vehicle.
Returns:
The vehicle found (if any) at location (x, y) on the game gameBoard.
Throws:
OffGameBoardException - The given coordinates are not on the game gameBoard.

getVehicleAtIndex

public RushHourVehicle getVehicleAtIndex(int i)
                                  throws VehicleDoesNotExistException
Retrieve the vehicle at index i from the array of vehicles known to be on the gameBoard.

Parameters:
i - The index of the vehicle in the vehicle array.
Returns:
The vehicle found at index in in the vehicle array.
Throws:
VehicleDoesNotExistException - No vehicle exists at the specified index.

getVehicleByColor

public RushHourVehicle getVehicleByColor(java.lang.String color)
Retrieves the vehicle of the specified color on the gameBoard.

Parameters:
color - The color of the vehicle to be searched for.
Returns:
The vehicle object if that color vehicle is found, else null.

getVehiclesList

public java.util.Vector<RushHourVehicle> getVehiclesList()
Retrieve the list of vehicles known to be on the gameBoard.

Returns:
The array of vehicles known to be on the gameBoard.

getNumVehicles

public int getNumVehicles()
Retrieve the number of vehicles on the gameBoard.

Returns:
The number of vehicles on the gameBoard.

addVehicle

public RushHourVehicle addVehicle(java.lang.String type,
                                  java.lang.String color,
                                  java.lang.String orientation,
                                  int x,
                                  int y)
                           throws InvalidFirstVehicleException,
                                  RedCarException,
                                  InvalidVehicleColorException,
                                  OffGameBoardException,
                                  VehicleOverlapException,
                                  InvalidVehicleException
Add a vehicle to the game gameBoard at location (x, y).

Parameters:
type - The type of vehicle being added.
color - The color of the vehicle being added.
orientation - The orientation of the vehicle being added.
x - The x-coordinate of the vehicle being added.
y - The y-coordinate of the vehicle being added.
Returns:
The added vehicle.
Throws:
InvalidFirstVehicleException - The first vehicle must be red.
RedCarException - The red car must be in the third row so it can exit.
InvalidVehicleColorException - That given color is already in use by another vehicle.
OffGameBoardException - The given coordinates are not on the game gameBoard.
VehicleOverlapException - The vehicle cannot be added at the specified coordinates because it overlaps an already existing vehicle.
InvalidVehicleException - The vehicle must be of type "car" or "truck."

addCar

public RushHourVehicle addCar(java.lang.String color,
                              java.lang.String orientation,
                              int x,
                              int y)
                       throws InvalidFirstVehicleException,
                              InvalidVehicleColorException,
                              OffGameBoardException,
                              VehicleOverlapException,
                              RedCarException
Add a car to the game gameBoard at location (x, y).

Parameters:
color - The color of the car being added.
orientation - The orientation of the car being added.
x - The x-coordinate of the car being added.
y - The y-coordinate of the car being added.
Returns:
The added car object.
Throws:
InvalidFirstVehicleException - The first vehicle must be red.
RedCarException - The red car must be in the third row so it can exit.
InvalidVehicleColorException - That given color is already in use by another vehicle.
OffGameBoardException - The given coordinates are not on the game gameBoard.
VehicleOverlapException - The vehicle cannot be added at the specified coordinates because it overlaps an already existing vehicle.

addTruck

public RushHourVehicle addTruck(java.lang.String color,
                                java.lang.String orientation,
                                int x,
                                int y)
                         throws InvalidFirstVehicleException,
                                InvalidVehicleColorException,
                                OffGameBoardException,
                                VehicleOverlapException
Add a truck to the game gameBoard at location (x, y).

Parameters:
color - The color of the car being added.
orientation - The orientation of the car being added.
x - The x-coordinate of the car being added.
y - The y-coordinate of the car being added.
Returns:
The added car object.
Throws:
InvalidFirstVehicleException - The first vehicle must be red.
InvalidVehicleColorException - That given color is already in use by another vehicle.
OffGameBoardException - The given coordinates are not on the game gameBoard.
VehicleOverlapException - The vehicle cannot be added at the specified coordinates because it overlaps an already existing vehicle.

removeVehicle

public void removeVehicle(RushHourVehicle vehicle)
                   throws VehicleDoesNotExistException
Remove the vehicle of the specified color from the game gameBoard and from the list of vehicles.

Parameters:
vehicle - The vehicle to be removed.
Throws:
VehicleDoesNotExistException

removeCar

public void removeCar(RushHourVehicle car)
Remove the specified car from the game gameBoard.

Parameters:
car - The car to be removed.

removeTruck

public void removeTruck(RushHourVehicle truck)
Remove the specified truck from the game gameBoard.

Parameters:
truck - The truck to be removed.