deadendfillsolve.java

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

/* ver: 0.1, date 04-01-2008 by Marcel Hekman
 * - Initial implementation
 *              - Implemented initialise, isDone, tick, fillOneGap and tryElement
 * ver: 0.2, date 05-01-2008 by Marcel Hekman
 * - Now using posX for a less 'jumpy' algorithm.
 */

package mazeAssignment;

public class DeadendFillSolve implements Solve
{
        private Maze maze;
        private boolean isFinished;
        private int posX, posY;
        
        @Override
        public void initialise(Maze m) throws SolveException
        {
                this.maze = m;
                this.isFinished = false;
                this.posX = 0;
                this.posY = 0;
        }

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

        @Override
        public void tick() throws SolveException
        {
                if(isFinished)
                        throw new SolveException("DeadendFillSolve.tick(): Already finished!");
                
                boolean hasChangedAField = fillOneGap();
                
                //We're at the end of the maze start from the beginning.
                if(!hasChangedAField)
                {
                        //Reset the current row number.
                        posX = 0;
                        posY = 0;
                        hasChangedAField = fillOneGap();
                        
                        //A full run changed nothing, so we're finished.
                        if(!hasChangedAField)
                        {
                                isFinished = true;
                                return;
                        }
                }
        }
        
        /**
         * Searches the entire maze for a dead-end element.
         * Saves and resumes from a previously saved row.
         * And start from the beginning if we reach the end. (only start from the beginning once)
         * @return True if a gap was filled.
         * If not the algorithm is finished because it cannot fill anymore gaps.
         */
        private boolean fillOneGap()
        {
                int xSize = maze.getSizeX();
                int ySize = maze.getSizeY();
                
                //Continue from the last position
                for(int y = posY; y < ySize; y++)
                {
                        for(int x = posX; x < xSize; x++)
                        {
                                if(tryElement(x, y))
                                {
                                        //Save the current row number.
                                        posX = x;
                                        posY = y;
                                        return true;
                                }
                        }
                        //Reset the x position so it won't make a curve shape during solve.
                        posX = 0;
                }
                
                return false;
        }
        
        /**
         * Checks if a node is a is a dead end.
         * @param x Coordinate.
         * @param y Coordinate.
         * @return True if the element is a dead-end and marked. Else false.
         */
        private boolean tryElement(int x, int y)
        {
                MazeElement current = maze.getElement(x, y);
                
                //SOLVE_START and SOLVE_END are obviously not a dead end.
                //Skip SOLVE_INVALID too because it is already marked.
                if(current.getSolveState() == MazeElement.SOLVE_START
                || current.getSolveState() == MazeElement.SOLVE_END
                || current.getSolveState() == MazeElement.SOLVE_INVALID)
                {
                        return false;
                }
                
                int xSize = maze.getSizeX();
                int ySize = maze.getSizeY();
                
                //Count all accessible directions.
                int blockedDirections = 0;
                
                //North
                if(y == 0 || current.getNorth()
                || maze.getElement(x, y-1).getSolveState() == MazeElement.SOLVE_INVALID)
                {
                        blockedDirections++;
                }
                
                //East
                if(x+1 == xSize || current.getEast()
                || maze.getElement(x+1, y).getSolveState() == MazeElement.SOLVE_INVALID)
                {
                        blockedDirections++;
                }
                
                //South
                if(y+1 == ySize || current.getSouth()
                || maze.getElement(x, y+1).getSolveState() == MazeElement.SOLVE_INVALID)
                {
                        blockedDirections++;
                }
                
                //West
                if(x-1 == xSize || current.getWest()
                || maze.getElement(x-1, y).getSolveState() == MazeElement.SOLVE_INVALID)
                {
                        blockedDirections++;
                }
                
                //A dead end
                if(blockedDirections > 2)
                {
                        current.markAsInvalid();
                        return true;
                }
                else
                {
                        return false;
                }
        }
}