unweightedshortestsolve.java

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

package mazeAssignment;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class UnweightedShortestSolve implements Solve
{
        private Maze maze;
        private Queue<Vertex> vertexQueue;
        private Map<Integer,Vertex> vertexMap;
        
        private boolean isSolved;
        
        
        public UnweightedShortestSolve()
        {
                maze = null;
                vertexQueue = null;
                vertexMap = null;
                isSolved = false;
        }
        
        
        @Override
        public void initialise(Maze m) throws SolveException
        {
                this.maze = m;
                this.vertexQueue = new LinkedList<Vertex>();
                this.vertexMap = new HashMap<Integer,Vertex>();
                
                generateGraphAndFindFirst();
        }

        @Override
        public void tick() throws SolveException
        {
                if(isSolved)
                        throw new SolveException("UnweightedShortest.tick(): Already solved.");
                
                
                int mazeWidth = maze.getSizeX();
                
                Vertex currentVertex = vertexQueue.poll();
                
                int xPosition = currentVertex.number % mazeWidth;
                int yPosition = currentVertex.number / mazeWidth;
                
                MazeElement current = maze.getElement(xPosition, yPosition);
                
                //Check if we are at the end
                if(current.getSolveState() == MazeElement.SOLVE_END)
                {
                        highLightValidPath(currentVertex.prev);
                        isSolved = true;
                        return;
                }
                
                //By default mark everything as invalid so
                //it is easier to mark the valid path in the end.
                current.markAsInvalid();
                
                for(Edge e : currentVertex.edges)
                {
                        Vertex connectedVertex = e.dest;
                        
                        if(connectedVertex.weight == Double.MAX_VALUE)
                        {
                                connectedVertex.weight = currentVertex.weight + 1;
                                connectedVertex.prev = currentVertex;
                                vertexQueue.add(connectedVertex);
                        }
                }
                
                if(vertexQueue.isEmpty())
                        throw new SolveException("UnweightedShortest.tick(): No exit defined.");
        }
        
        /**
         * Generates the graph for the unweighted shortest path algorithm.
         */
        private void generateGraphAndFindFirst()
        {
                int xSize = maze.getSizeX();
                int ySize = maze.getSizeY();
                
                for(int x = 0; x < xSize; x++)
                {
                        for(int y = 0; y < ySize; y++)
                        {
                                //Generate an unique vertexNumber
                                int vertexNumber = x + (y * xSize);
                                Vertex currentVertex = new Vertex(vertexNumber);

                                MazeElement current = maze.getElement(x, y);
                                
                                //If we find the begin vertex add it to the queue.
                                if(current.getSolveState() == MazeElement.SOLVE_START)
                                {
                                        currentVertex.weight = 0;
                                        vertexQueue.add( currentVertex );
                                }

                                //Connect with the vertex on the left
                                if(x != 0 && ! current.getWest())
                                {
                                        int leftNumber = (x - 1) + (y * xSize);
                                        Vertex leftVertex = vertexMap.get( leftNumber );
                                        
                                        //Connect current with left
                                        currentVertex.edges.add( new Edge(leftVertex, 1) );

                                        //Connect left with current
                                        leftVertex.edges.add( new Edge(currentVertex, 1) );
                                }
                                
                                //Connect with the vertex above
                                if(y != 0 && ! current.getNorth())
                                {
                                        int northNumber = x + ((y - 1) * xSize);
                                        Vertex northVertex = vertexMap.get( northNumber );
                                        
                                        //Connect current with north
                                        currentVertex.edges.add( new Edge(northVertex, 1) );

                                        //Connect north with current
                                        northVertex.edges.add( new Edge(currentVertex, 1) );
                                }
                                
                                //Insert vertex into the map
                                vertexMap.put(vertexNumber, currentVertex);
                        }
                }
        }
        
        /**
         * Highlights the valid path from start to end.
         */
        private void highLightValidPath(Vertex currentVertex)
        {
                while(true)
                {
                        int mazeWidth = maze.getSizeX();
                        
                        int xPosition = currentVertex.number % mazeWidth;
                        int yPosition = currentVertex.number / mazeWidth;
                        
                        MazeElement current = maze.getElement(xPosition, yPosition);
                        
                        if(current.getSolveState() == MazeElement.SOLVE_START)
                        {
                                return;
                        }
                        
                        currentVertex = currentVertex.prev;
                        
                        //Mark as the valid path.
                        current.visit();
                }
        }
        
        
        @Override
        public boolean isDone()
        {
                return isSolved;
        }
}