intermediarystep.java

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

/** ver 0.1 - date 04-01-2008 - by Jeroen S
* First implementation version
*/

package mazeAssignment;

class IntermediaryStep {

       private Maze gridmaze;
       
       // Maximum number of times we try to knock down
       static final int MAX_TRY_KNOCKDOWN = 20;
       
       public IntermediaryStep(Maze maze)
       {
               this.gridmaze = maze;
       }
       
       public boolean updateMaze(boolean doRandomExit, int wallsToKnock)
       {
               int xsize = gridmaze.getSizeX();
               int ysize = gridmaze.getSizeY();
               
               resetSolvestate(MazeElement.SOLVE_START);
               resetSolvestate(MazeElement.SOLVE_END);
               
               if(doRandomExit)
               {
                       //sets start and end randomly
                       MazeElement start = gridmaze.getElement(getRandNum(xsize), getRandNum(ysize));
                       //start.setNorth(false);
                       //start.setWest(false);
                       start.setSolveState(MazeElement.SOLVE_START);
                       MazeElement end = gridmaze.getElement(getRandNum(xsize), getRandNum(ysize));
                       //end.setSouth(false);
                       //end.setEast(false);
                       end.setSolveState(MazeElement.SOLVE_END);
               } else {
                       //sets start and end
                       MazeElement start = gridmaze.getElement(0, 0);
                       //start.setNorth(false);
                       //start.setWest(false);
                       start.setSolveState(MazeElement.SOLVE_START);
                       MazeElement end = gridmaze.getElement(xsize-1, ysize-1);
                       //end.setSouth(false);
                       //end.setEast(false);
                       end.setSolveState(MazeElement.SOLVE_END);
               }
               
               // Knock down a number of walls
               for(int i = 0; i < wallsToKnock; i++)
               {
                       // Skip over elements without walls
                       boolean foundElement = false;
                       // Place a limit on the times we check.
                       int numtries = 0;
                       while(!foundElement && numtries < MAX_TRY_KNOCKDOWN)
                       {
                               numtries++;
                               
                               int xpos = getRandNum(xsize);
                               int ypos = getRandNum(ysize);
                               MazeElement element = gridmaze.getElement(xpos, ypos);
                               
                               //prepare other variables for the search of the partner (start somewhere randomly
                               boolean foundPartner= false;
                               boolean doneNorth = false;
                               boolean doneEast = false;
                               boolean doneSouth = false;
                               boolean doneWest = false;
                               int partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                               int numpartners = 0;
                               
                               //search for a location that is aside the ourlocation, but that has not been added to the group
                               //(list) where "ourlocation" belongs to. if all 4 walls have been searched for and none prevail,
                               //then it is time to try to find another one.
                               //there are tests for (in order:) out of bounds, same group)
                               while (!foundPartner && numpartners < 4)
                               {
                                       
                                       switch (partner)
                                       {
                                       //0 = north
                                       case 0:
                                               doneNorth = true;
                                               if(ypos==0)
                                               {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                                       break;
                                               }
                                               if(element.getNorth())
                                               {
                                                       foundPartner = true;
                                                       foundElement = true;
                                                       element.setNorth(false);
                                                       gridmaze.getElement(xpos, ypos-1).setSouth(false);
                                               } else {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                               }
                                               break;
                                       //1= east
                                       case 1:
                                               doneEast = true;
                                               if(xpos==gridmaze.getSizeX()-1)
                                               {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                                       break;
                                               }
                                               if(element.getEast())
                                               {
                                                       foundPartner = true;
                                                       foundElement = true;
                                                       gridmaze.getElement(xpos+1, ypos).setWest(false);
                                                       element.setEast(false);
                                               } else {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                               }
                                               break;
                                       //2= south
                                       case 2:
                                               doneSouth = true;
                                               if(ypos==gridmaze.getSizeY()-1)
                                               {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                                       break;
                                               }
                                               if (element.getSouth())
                                               {
                                                       gridmaze.getElement(xpos, ypos+1).setNorth(false);
                                                       element.setSouth(false);
                                                       foundPartner = true;
                                               } else {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                               }
                                               break;
                                       //3= west
                                       case 3:
                                               doneWest = true;
                                               if(xpos==0)
                                               {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                                       break;
                                               }
                                               if(element.getWest())
                                               {
                                                       foundPartner = true;
                                                       gridmaze.getElement(xpos-1, ypos).setEast(false);
                                                       element.setWest(false);
                                               } else {
                                                       partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                       numpartners++;
                                               }
                                               break;
                                       case -1:
                                               numpartners = 4;
                                               break;
                                       }
                                       
                               }
                               //if all walls have been searched, then it is time for a new element to checkup!
                               if(numpartners > 3)
                               {
                                       continue;
                               }
                       }
                       
               }
               
               return true;
       }
       
       /*
        * Creates a random number between 0 and max ([0, max>)
        */
       private int getRandNum(int max)
       {
               return (int)(Math.random() * max);
       }
       
       // Selects a random partner, based on the available choices.
       private int selectPartner(boolean doneNorth, boolean doneEast, boolean doneSouth, boolean doneWest)
       {
               int numchoices = 0;
               
               // No partners left to do?
               if(doneNorth && doneEast && doneSouth && doneWest)
                       return -1;
               
               // Add a choice for each still unchecked partner.
               if(!doneNorth)
                       numchoices++;
               if(!doneEast)
                       numchoices++;
               if(!doneSouth)
                       numchoices++;
               if(!doneWest)
                       numchoices++;
               
               // Choose
               int choice = (int) (Math.random() * numchoices);
               
               // If a partner is available, it was added to the choices
               if(!doneNorth)
               {
                       // This is our choice
                       if(choice == 0)
                               return 0;
                       // Prepare for the next
                       else
                               choice--;
               }
               if(!doneEast)
               {
                       if(choice == 0)
                               return 1;
                       else
                               choice--;
               }
               if(!doneSouth)
               {
                       if(choice == 0)
                               return 2;
                       else
                               choice--;
               }
               if(!doneWest)
               {
                       if(choice == 0)
                               return 3;
                       else
                               choice--;
               }
               /*!NOTREACHED*/
               return -1;
       }
       
       /**
        * Find the first element with the solve state and returns it
        * in xpos and ypos
        */
       private boolean resetSolvestate(int solvestate)
       {
               int xSize = gridmaze.getSizeX();
               int ySize = gridmaze.getSizeY();
               
               for(int x = 0; x < xSize; x++)
               {
                       for(int y = 0; y < ySize; y++)
                       {
                               MazeElement current = gridmaze.getElement(x, y);
                               
                               if(current.getSolveState() == solvestate)
                               {
                                       current.setSolveState(MazeElement.SOLVE_UNVISITED);
                               }
                       }
               }
               
               return true;
       }
}