pathbuild.java

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

/*ver 0.1 made by Jeroen S and W 
 * implemented methods of interface Build
 * ver 0.2 - 02-01-2008 - by Jeroen S
 * Minor bugfixes and other cleanup
 * ver 0.3 - 02-01-2008 - by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 *  ver: 0.4, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 * 
 *   ver:0.5 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 * 
 * 
 */



package mazeAssignment;

import java.util.ArrayList;

public class PathBuild implements Build{

        private Maze mazeGrid;
        private ArrayList<CoordinatePair> notVisited, visited;

        //returns the maze
        public Maze getMaze() {
                return mazeGrid;
                
        }
        
        //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;
        }

        //initialise the extra structures that are required for this algorithm:
        //2 arraylists: visited and not visited.
        public void initialise(Maze maze) {
                mazeGrid=maze;
                int x= mazeGrid.getSizeX();
                int y= mazeGrid.getSizeY();
                notVisited = new ArrayList<CoordinatePair>();
                visited = new ArrayList<CoordinatePair>();
                //set the coordinatepairs for the positions.
                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());
                visited.add(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)
                {
                        //take a visited element
                        int i= (int)(Math.random()*visited.size());
                        CoordinatePair firstPair= (CoordinatePair) visited.get(i);
                        
                        //find a partner (geen partner, verwijder uit visited en ga weer een nieuwe zoeken)
                        boolean foundPartner= false;
                        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
                        //if none can be found amongside the firstElement
                        //then it is time to try to find another one.
                        //there are tests for (in order:) out of bounds, same group)
                        //as soon as one is found, the wall is taken down and it is removed from notVisited
                        //and added to visited
                        //at the end firstPair is removed from visited so it will not be used again.

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

                                                foundPartner = true;
                                        } else {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                        }
                                        break;
                                //3= west
                                case 3: 
                                        doneWest = true;
                                        if(firstPair.x==0)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(elementNotVisited(firstPair.x-1, (firstPair.y)))
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(firstPair.x-1, firstPair.y).setEast(false);
                                                mazeGrid.getElement(firstPair.x, firstPair.y).setWest(false);
                                                notVisited.remove(findElement(firstPair.x-1, (firstPair.y)));
                                                visited.add(new CoordinatePair(firstPair.x-1, (firstPair.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!
                        if(numpartners > 3)
                        {
                                visited.remove(firstPair);
                                continue;
                        }
                        tickIsDone = true;
                        
                }
                //report tick is done
                return true;
        }
        
        // 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;
        }
        
}