dfsbuild.java

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

/*ver 0.1 by Jeroen S & W : implemented methods from Build interface
 * ver 0.2 - 02-01-2008 by Jeroen S
 * Implementation tick()
 * 
 * ver 0.3 02-01-2008 by Jeroen W
 * added comment to make the code readeable
 * 
 * ver 0.4 02-01-2008 by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 *  
 *  ver: 0.5, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 *  
 *    ver:0.6 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 */
package mazeAssignment;

import java.util.Stack;
import java.util.ArrayList;


public class DfsBuild implements Build{

        private Maze mazeGrid;
        private Stack<CoordinatePair> notCompleted;
        private ArrayList<CoordinatePair> notVisited;
        private CoordinatePair currentElement;
        
        //returns the maze;
        public Maze getMaze() {
                return mazeGrid;
        }

        //initialises the build and its structures: a stack and an arraylist
        public void initialise(Maze maze) {
                mazeGrid=maze;
                notCompleted = new Stack<CoordinatePair>();
                notVisited= new ArrayList<CoordinatePair>();
                int x= mazeGrid.getSizeX();
                int y= mazeGrid.getSizeY();
                for(int i=0; i<(x*y); i++)
                { 
                        CoordinatePair p = new CoordinatePair(i/y, i%y);
                        notVisited.add(p);
                }
                int i= (int)(Math.random()*notVisited.size());
                currentElement = notVisited.get(i);
                notVisited.remove(i);
                
                //set start and endpoint
                MazeElement start = mazeGrid.getElement(0, 0);
                //start.setNorth(false);
                //start.setWest(false);
                start.setSolveState(MazeElement.SOLVE_START);
                MazeElement end = mazeGrid.getElement(x-1, y-1);
                //end.setSouth(false);
                //end.setEast(false);
                end.setSolveState(MazeElement.SOLVE_END);
                
        }
        
        //returns true if notVisited is the appropiate size (0)
        public boolean isDone() {
                return (notVisited.size()<1);
        }

        //advances the algorithm by one step.
        public boolean tick() {
                if(isDone())
                {
                        return false;
                }
                
                boolean tickIsDone = false;
                
                //the tick is based on trial and error, we should repeat this until the tick was succesful
                while (!tickIsDone)
                {
                
                        //find a partner (no partner, remove from stack and go a step backward)
                        boolean foundPartner= false;
                        //int partner= (int) (Math.random()*4);
                        int numpartners = 0;
                        boolean doneNorth = false;
                        boolean doneEast = false;
                        boolean doneSouth = false;
                        boolean doneWest = false;
                        int partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                        
                        //search for a pair that is aside the firstPair, and registered in notVisited
                        //then lower walls and remove it from not visited and push it onto the
                        // notcompleted stack (so it can be handled later)
                        //the same tests are here: out of bounds, same group
                        while (!foundPartner && numpartners < 4)
                        {

                                switch (partner)
                                {
                                //0 = north
                                case 0: 
                                        doneNorth = true;
                                        if(currentElement.y==0)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(elementNotVisited(currentElement.x, currentElement.y-1))
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(currentElement.x, currentElement.y-1).setSouth(false);
                                                mazeGrid.getElement(currentElement.x, currentElement.y).setNorth(false);
                                                notVisited.remove(findElement(currentElement.x, (currentElement.y)-1));
                                                notCompleted.push(currentElement);
                                                currentElement = new CoordinatePair(currentElement.x, currentElement.y-1);
                                        } else {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                        }
                                        break;
                                //1= east
                                case 1: 
                                        doneEast = true;
                                        if(currentElement.x==mazeGrid.getSizeX()-1)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(elementNotVisited(currentElement.x+1, currentElement.y))
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(currentElement.x+1, currentElement.y).setWest(false);
                                                mazeGrid.getElement(currentElement.x, currentElement.y).setEast(false);
                                                notVisited.remove(findElement((currentElement.x)+1, currentElement.y));
                                                notCompleted.push(currentElement);
                                                currentElement = new CoordinatePair(currentElement.x+1, currentElement.y);
                                        } else {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                        }
                                        break;
                                //2= south
                                case 2: 
                                        doneSouth = true;
                                        if(currentElement.y==mazeGrid.getSizeY()-1)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(elementNotVisited(currentElement.x, (currentElement.y)+1))
                                        {
                                                mazeGrid.getElement(currentElement.x, currentElement.y+1).setNorth(false);
                                                mazeGrid.getElement(currentElement.x, currentElement.y).setSouth(false);
                                                notVisited.remove(findElement(currentElement.x, (currentElement.y)+1));
                                                notCompleted.push(currentElement);
                                                currentElement = new CoordinatePair(currentElement.x, currentElement.y+1);

                                                foundPartner = true;
                                        } else {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                        }
                                        break;
                                //3= west
                                case 3: 
                                        doneWest = true;
                                        if(currentElement.x==0)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(elementNotVisited(currentElement.x-1, (currentElement.y)))
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(currentElement.x-1, currentElement.y).setEast(false);
                                                mazeGrid.getElement(currentElement.x, currentElement.y).setWest(false);
                                                notVisited.remove(findElement(currentElement.x-1, (currentElement.y)));
                                                notCompleted.push(currentElement);
                                                currentElement = new CoordinatePair(currentElement.x-1, currentElement.y);
                                        } 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!
                        //the stack has been filled with many elements, so one has to be popped and checked
                        //if it can be handled as above(if it fails all the tests, then the next one will be popped,
                        //etc. etc., untill stack is empty (while it will be filled during the processing of new processed
                        //elements)
                        if(numpartners > 3)
                        {
                                currentElement = notCompleted.pop();
                                continue;
                        }
                        tickIsDone = true;
                        
                }
                
                return true;
        }
        
        //returns true if the element is not visited.
        private boolean elementNotVisited(int x, int y)
        {
                for(int i = 0; i < notVisited.size(); i++)
                {
                        CoordinatePair p = notVisited.get(i);
                        if(p.x == x && p.y == y)
                                return true;
                }
                return false;
        }
        
        //searches the index of the element
        private int findElement(int x, int y)
        {
                for(int i = 0; i < notVisited.size(); i++)
                {
                        CoordinatePair p = notVisited.get(i);
                        if(p.x == x && p.y == y)
                                return i;
                }
                return -1;
        }
        
        // 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;
        }
        
}