bookbuild.java

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

/* ver: 0.1, date 2-1-2008 by Jeroen S & W
 *  setted up a basic buildalgorithm with all the public methods that were required by the interface
 *  added an encapsulated class that has the location: it is a coordinate pair.
 *  
 *  ver: 0.2, date 2-1-2008 by Jeroen S
 *  Resolved a few warnings
 *  
 *  ver: 0.3, date 2-1-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.LinkedList;
import java.util.ArrayList;
import java.util.ListIterator;

public class BookBuild implements Build{

        private Maze mazeGrid;
        private ArrayList<LinkedList<CoordinatePair>> gridLocator;
        
        //this is the initialisation
        public void initialise(Maze maze) {
                mazeGrid= maze;
                gridLocator = new ArrayList<LinkedList<CoordinatePair>>();
                int x= mazeGrid.getSizeX();
                int y= mazeGrid.getSizeY();
                
                //set the coordinatepairs for the positions.
                for(int i=0; i<(x*y); i++)
                { 
                        CoordinatePair p = new CoordinatePair(i/y, i%y);
                        LinkedList<CoordinatePair> list = new LinkedList<CoordinatePair>();
                        list.add(p);
                        gridLocator.add(list);
                        mazeGrid.getElement(i/y, i%y).setBuildLocation(i);
                }
                
                //sets start and end 
                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 maze structure (optional)
        public Maze getMaze()
        {
                return mazeGrid;
        }


        //returns if it is done (the arraylist should have one element when that is the case:))
        public boolean isDone() {
                return (gridLocator.size() <2);
        }

        //this advances the build one step
        public boolean tick() {
                
                //test if it is done, or it will loop forever (if it is done and we try to 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)
                {
                        //pick up a random element out of the maze and call it your location
                        int i= (int)(Math.random()*gridLocator.size());
                        int j= (int)(Math.random()*gridLocator.get(i).size());
                        CoordinatePair firstPair= (CoordinatePair)gridLocator.get(i).get(j);
                        int ourLocation = mazeGrid.getElement(firstPair.x, firstPair.y).getBuildLocation();
                        
                        //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;
                        int newLocation= -1;
                        
                        //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(firstPair.y==0)
                                        {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                                break;
                                        }
                                        if(ourLocation  != mazeGrid.getElement(firstPair.x, firstPair.y-1).getBuildLocation())
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(firstPair.x, firstPair.y-1).setSouth(false);
                                                mazeGrid.getElement(firstPair.x, firstPair.y).setNorth(false);
                                                newLocation = mazeGrid.getElement(firstPair.x, firstPair.y-1).getBuildLocation();
                                        } 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(ourLocation  != mazeGrid.getElement(firstPair.x+1, firstPair.y).getBuildLocation())
                                        {
                                                foundPartner = true;
                                                mazeGrid.getElement(firstPair.x+1, firstPair.y).setWest(false);
                                                mazeGrid.getElement(firstPair.x, firstPair.y).setEast(false);
                                                newLocation = mazeGrid.getElement(firstPair.x+1, firstPair.y).getBuildLocation();
                                        } else {
                                                partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
                                                numpartners++;
                                        }