Class  Tree  Index 
Amazing Mazes
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD

Class Mouse

java.lang.Object
  |
  +--Mouse
Direct Known Subclasses:
ScatterBrained, Smarty
public abstract class Mouse
extends java.lang.Object

This is the Mouse class definition. A Mouse object has the ability to traverse a maze puzzle, creating a solution path.

Mouse is an abstract base class that provides both low level utilitarian functionality, as well as the foundational interface from which to solve a maze puzzle.

Mouse objects are instantiated with no state (i.e. using a default constructor). Therefore they can be re-used in solving many mazes.

To solve a maze, simply invoke the solveMaze() method. This is supplied a MazeAdapter object which provides an abstract interface to the actual maze. Because an adapter is used, the mouse can traverse different types of mazes (as long as a MazeAdapter has been developed for the maze type).

This Mouse class is abstract in the sense that the makeAMove() method must be defined by concrete derivations. The makeAMove() method is invoked for each successive move that is made in solving the maze puzzle. It simply decides which direction it wants to move, based on the mouse's current position, and the walls around it. Derivations of this base class may alter the way in which the Mouse traverses the maze, by specifying different rules for which the open passageways are traversed. In Computer Science, these are called heuristics. Different heuristics will provide varying degrees of efficiency (i.e. minimize the number of retreats that have to be issued).

Several utilitarian methods exist in this base class, namely: 

 protected boolean passagewayOpenAt(Direction direction)
     return an indicator as to whether the passageway is open, in
     the supplied direction, relative to current mouse cell
     location.

 protected double distanceToGoal(Direction direction)
     return the distance to the maze solution, from the cell
     based on the current cell projected in the supplied direction.

 public static int randomInt(int n)
     a static method that returns a random integer, bounded by the
     supplied integer parameter.

 public int solveMaze(MazeAdapter mazeAdapter)
     this is the primary entry point into the system.
 
 private void advance(Direction direction) throws InvalidMove
     advance the mouse from it's current maze cell position to an
     adjacent cell based on the supplied direction.  NOTE: This
     should not be directly used, as it is invoked via solveMaze().

 private void retreat() throws NoSolutionFound
     retreat the mouse from it's current maze cell position to the
     prior cell from which it was entered from.  NOTE: This should
     not be directly used, as it is invoked via solveMaze().

Version:
1.0 08/31/2000
Author:
Kevin Bridges ... Copyright (c) 2001

Field Summary
(package private)  Position curPosition_
          Current position.
(package private)  MazeAdapter mazeAdapter_
          The maze which we are to solve.
(package private)  java.util.Stack stack_
          Stack (of Position objects) identifying our current traversal path.
 
Constructor Summary
Mouse()
          Construct a default Mouse instance.
 
Method Summary
protected  void advance(Direction direction)
          This method will advance the mouse (self) from it's current maze cell position to an adjacent cell based on the supplied direction.
protected  double distanceToGoal(Direction direction)
          This method will return the distance to the maze solution, from the cell based on the current cell projected in the supplied direction.
protected abstract  Direction makeAMove()
          The makeAMove() method is invoked for each successive move that is made in solving the maze puzzle.
protected  boolean passagewayOpenAt(Direction direction)
          This method will return an indicator as to whether the passageway is open, in the supplied direction, relative to current mouse cell location.
static int randomInt(int n)
          This static method will return a random integer, bounded by the supplied integer parameter.
protected  void retreat()
          This method will retreat the mouse (self) from it's current maze cell position to the prior cell from which it was entered from.
 int solveMaze(MazeAdapter mazeAdapter)
          The solveMaze() method is the primary entry point into the system.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

mazeAdapter_

MazeAdapter mazeAdapter_
The maze which we are to solve.

stack_

java.util.Stack stack_
Stack (of Position objects) identifying our current traversal path.

curPosition_

Position curPosition_
Current position. This is a convenience variable, containing the top-most entry of our stack_.
Constructor Detail

Mouse

public Mouse()
Construct a default Mouse instance.
Method Detail

makeAMove

protected abstract Direction makeAMove()
The makeAMove() method is invoked for each successive move that is made in solving the maze puzzle.

This method should decide which direction it wants to move, based on the current position of the mouse (self) and the walls around it within the maze (see passagewayOpenAt() method). This direction could be an actual direction (such as North/South/East/West) or a Retreat directive (if we have exhausted all passageways ... i.e. hit a dead-end).

Derivations of this base class may alter the way in which the Mouse traverses the maze, by specifying different rules for which the open passageways are traversed. In Computer Science, these are called heuristics. Different heuristics will provide varying degrees of efficiency (i.e. minimize the number of retreats that have to be issued).

Returns:
the direction that should be traversed, as a result of this move. This could be an actual direction (such as North/South/East/West) or a Retreat directive (if we have hit a dead-end).

solveMaze

public int solveMaze(MazeAdapter mazeAdapter)
The solveMaze() method is the primary entry point into the system. To solve a maze, simply invoke the solveMaze() method, supplying it a MazeAdapter object. This MazeAdapter object provides an abstract interface to the actual maze. Because an adapter is used, the mouse can traverse different types of mazes (as long as a MazeAdapter has been developed for the maze type).

This solveMaze() method will itteratively traverse the maze (by invoking self's makeAMove() method), until a solution is found. It maintains a "solution" traversal stack, and reports the number of moves that were made in finding the solution.

 Logic Flow:
   1. Retain the maze parameter in self.
   2. Create a new traversal stack, retaining the maze's initial
      starting position.
   3. Iteratively traverse the maze until a solution is found.
       3A. Instruct self to "Make A Move", calculating a direction to go.
       3B. Based on the directive of the calculated direction,
           either advance into a new passageway, or retreat back to our
           previous cell.
       3C. Keep track of the number of moves made in this solution.
   4. If solution exists, report it along with the number of analysis 
      moves it required.
   Processing End (solveMaze)
Parameters:
mazeAdapter - the maze which we are to traverse and solve.
Returns:
the number of moves to the solution.

randomInt

public static int randomInt(int n)
This static method will return a random integer, bounded by the supplied integer parameter.
Parameters:
n - the maximin value (uper range) for the random integer.
Returns:
return a random integer, between 1 and the supplied parameter n.

distanceToGoal

protected double distanceToGoal(Direction direction)
This method will return the distance to the maze solution, from the cell based on the current cell projected in the supplied direction. 

 Logic Flow:
   1. Define the new cell coordinates, by advancing the current position
      in the supplied direction.
   2. Define the target coordinate.
   3. Calculate the height and width of the given distance.
   4. Compute the distance.
      distance**2 = height**2 _ width**2
   Processing End (distanceToGoal)
Parameters:
direction - the direction to project the current cell location.
Returns:
return the distance to the maze solution, from the cell based on the current cell projected in the supplied direction.

passagewayOpenAt

protected boolean passagewayOpenAt(Direction direction)
This method will return an indicator as to whether the passageway is open, in the supplied direction, relative to current mouse cell location.
Parameters:
direction - the direction to check, relative to the current mouse cell location.
Returns:
true if the passageway in supplied direction is open, false otherwise.

advance

protected void advance(Direction direction)
                throws InvalidMove
This method will advance the mouse (self) from it's current maze cell position to an adjacent cell based on the supplied direction. Validation is performed, our traversal stack is maintained, and the mazes visual affects are updated.

NOTE: This method is private to prevent it from being invoked by Mouse derivations. It is ivoked from within solveMaze(). 

 Logic Flow:
   1. Validate that this is a valid move (i.e. insure there are no
      walls in the supplied direction).
   2. Define the new cell coordinates, by advancing the current position
      in the supplied direction.
   3. Validate that we are not attempting to advance to the cell we
      just came from.
   4. Push the new position onto our traversal stack.
   5. Visualize this move within our maze.
   Processing End (advance)
Parameters:
direction - the direction to advance.
Throws:
InvalidMove - the specified direction constitutes an invalid move. Either a wall exists in this direction, or it is a cell we just came from in our currenent traversal path (this requires usage of the retreat() method).

retreat

protected void retreat()
                throws NoSolutionFound
This method will retreat the mouse (self) from it's current maze cell position to the prior cell from which it was entered from. The mazes visual affects are updated. This method should be invoked once all passageways have been exhausted (i.e. a dead end is detected).

NOTE: This method is private to prevent it from being invoked by Mouse derivations. It is ivoked from within solveMaze(). 

 Logic Flow:
   1. Hold on to our prior position.
   2. Pop the exhausted cell off our traversal stack, and retain the 
      previously visited current position.
      NOTE: If we ever attemp to pop off the starting cell, this means
            that there is no solution to the maze ... reflected by a
            NoSolutionFound exception.
   3. Close the wall that we just traversed, to prevent advancment
      back where we came from.
   4. Visualize this move within our maze.
   Processing End (retreat)
Throws:
NoSolutionFound - either there is no solution to this maze, or we have a programming bug :-(
 Class  Tree  Index 
Author: Andrew Bridges
Copyright © 2001
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES
SUMMARY:  INNER | FIELD | CONSTR | METHOD DETAIL:  FIELD | CONSTR | METHOD