righthandsolve.java

简单的迷宫生成算法、复杂的迷宫生成算法、简单的迷宫搜索算法、复杂的迷宫搜索算法

/**ver: 0.1, date 27-12-2007 by Marcel Hekman
* implemented:
*      public: initialise, isDone, tick
*      private: turnLeft, turnRight, moveForward, directionHasWall, moveToNextElement, goBackwards()
*      protected: findStart <-- should be moved to an abstract class
* ver: 0.2, date 03-01-2007 by Marcel Hekman
*  bugfix: No longer searches outside the maze (still bugs left though).
*/

package mazeAssignment;

/**
*
* @author: jeroen, jeroen, marcel en teun
*/
public class RightHandSolve implements Solve
{
       private static final int NORTH = 0;
       private static final int EAST = 1;
       private static final int SOUTH = 2;
       private static final int WEST = 3;
       
       protected Maze maze;
       private boolean finished;
       private int direction;
       private int posX, posY;
       
       
       @Override
       public void initialise(Maze m) throws SolveException
       {
               this.maze = m;
               finished = false;
               
               findStart();
       }

       @Override
       public boolean isDone()
       {
               return finished;
       }

       @Override
       public void tick() throws SolveException
       {
               if(finished)
                       throw new SolveException("tick(): Already finished.");
               
               if(move(true))
               {
                       //Mark current element as visited.
                       getCurrent().visit();
               }
               else
               {
                       //'Dead end' so go back the way we came
                       turnLeft();
                       
                       //There shouldn't be a wall here
                       assert(! directionHasWall());
                       
                       //We go all the way back we came until we find an unvisited spot in one tick().
                       goBackwards();
                       
                       //Mark current element as visited.
                       getCurrent().visit();
               }
       }
       
       /**
        * Tries three walls. The wall on the right, in front and on the left.
        * @return True if a way if found, else false.
        * @throws SolveException
        */
       private boolean move(boolean forward) throws SolveException
       {
               //Try the wall on the right.
               if(! directionHasWall())
               {
                       moveToNextElement(forward);
                       return true;
               }
               
               //Try the wall in front.
               turnLeft();
               if(! directionHasWall())
               {
                       moveToNextElement(forward);
                       return true;
               }
               
               //Try the wall on the left.
               turnLeft();
               if(! directionHasWall())
               {
                       moveToNextElement(forward);
                       return true;
               }
               
               return false;
       }
       
       
       /**
        * Returns true if the current directions is walled, else false.
        * @return True if the current directions is walled, else false.
        */
       private boolean directionHasWall()
       {
               MazeElement current = getCurrent();
               if(direction == NORTH && posY > 0)
               {
                       return current.getNorth();
               }
               else if(direction == EAST && posX + 1 < maze.getSizeX())
               {
                       return current.getEast();
               }
               else if(direction == SOUTH && posY + 1 < maze.getSizeY())
               {
                       return current.getSouth();
               }
               else if(direction == WEST && posX > 0)
               {
                       return current.getWest();
               }
               
               //If we end up here it was at the edge of the maze and therefore a wall.
               return true;
       }
       
       /**
        * Moves to the next element.
        * Assumes the outer wall is always walled.
        * @throws SolveException When the maze contains a loop.
        */
       private void moveToNextElement(boolean forward) throws SolveException
       {
               if(direction == NORTH) {
                       posY--;
               }
               else if(direction == EAST) {
                       posX++;
               }
               else if(direction == SOUTH) {
                       posY++;
               }
               else {
                       posX--;
               }
               
               //Check if we have reached the end
               if(getCurrent().getSolveState() == MazeElement.SOLVE_END)
               {
                       this.finished = true;
                       return;
               }
               else if(forward && getCurrent().isVisited())
               {
                       throw new SolveException("RightHandSolve: moveToNextElement(): Maze contains a loop! (moving forward)");
               }
               else if(!forward && getCurrent().getSolveState() == MazeElement.SOLVE_INVALID)
               {
                       throw new SolveException("RightHandSolve: moveToNextElement(): Maze contains a loop! (moving backward)");
               }
               
               //Make sure the wall on the right is checked first at the next tick().
               turnRight();
       }
       
       /**
        * Used when we end up a tunnel that turns out to be a dead end.
        * @throws SolveException
        */
       private void goBackwards() throws SolveException
       {
               MazeElement previous = getCurrent();
               
               while(getCurrent().isVisited())
               {
                       previous.markAsInvalid();
                       previous = getCurrent();
                       
                       //Move further back
                       if(! move(false))
                               throw new SolveException("RightHandSolve: goBackwards(): Unable to find an unvisited spot, maze invalid?");
               }
       }
       
       private void turnLeft()
       {
               //orientation = (orientation + 3) % 4;
               direction = (direction + 3) & 3;                        //Same operation but apparently a bit faster
       }
       
       private void turnRight()
       {
               //orientation = (orientation + 1) % 4;
               direction = (direction + 1) & 3;                        //Same operation but apparently a bit faster
       }
       
       private MazeElement getCurrent()
       {
               return maze.getElement(posX, posY);
       }
       
       /**
        * Finds the start item in the maze
        * Assumes the start point is not in the center of the maze.
        * @throws SolveException If no start element is found.
        */
       private void findStart() throws SolveException
       {
               int xSize = maze.getSizeX();
               int ySize = maze.getSizeY();
               
               //Search the entire maze
               for(int x = 0; x < xSize; x++)
               {
                       for(int y = 0; y < ySize; y++)
                       {
                               MazeElement current = maze.getElement(x, y);
                               if(current.getSolveState() == MazeElement.SOLVE_START)
                               {
                                       this.posX = x;
                                       this.posY = y;
                                       
                                       if(!current.getNorth())
                                               direction = NORTH;


                                       if(!current.getEast())
                                               direction = EAST;

                                       if(!current.getSouth())
                                               direction = SOUTH;

                                       if(!current.getWest())
                                               direction = WEST;
                                       return;
                               }
                       }
               }
               
               throw new SolveException("findStart: Unable to find start element.");
       }
}