dijkstrashortestsolve.java

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

/*
* ver: 0.1, date 03-01-2008 by Marcel Hekman
* Implemented Dijkstra solve with breadth first graph build (not working).
* ver: 0.2, date 03-01-2008 by Marcel Hekman
* Implemented depth first graph build (works)
* Some other bugfixes.
* ver: 0.3, date 04-01-2008 by Marcel Hekman
* Made the solving process more clear in te mazegraph.
* Cleaned up breadth first graph build.
* ver: 0.4, date 04-01-2008 by Marcel Hekman
* - Started moving GraphBuilding to the tick() function.
* ver: 0.5, date 05-01-2008 by Marcel Hekman
* - All known bugs solved.
* ver: 0.6, date 06-01-2008 by Marcel Hekman
* - Graph building weer breadth first gemaakt (handiger met tick() en geen stackoverflows meer)
* - Graph building tick compatible gemaakt
* - HighLight ook tick compatible gemaakt.
*/

package mazeAssignment;

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

/**
* Requires more calculation power then the breadth first search.
* Because it always scans the entire maze.
* @author jeroen, jeroen, marcel en teun
*/
public class DijkstraShortestSolve implements Solve
{
       private static enum Direction { NORTH, EAST, SOUTH, WEST };
       
       private Maze maze;
       private Queue<Vertex> graphBuildQueue;
       private Map<Integer,Vertex> vertexMap;
       private PriorityQueue<Path> pathQueue;

       private Vertex firstVertex;
       private Vertex vertexToHighLight;
       
       private boolean needGraphBuilding;
       private boolean needSolving;
       private boolean needHighLighting;
       private boolean isFinished;
       
       public DijkstraShortestSolve()
       {
               this.maze = null;
               this.graphBuildQueue = null;
               this.vertexMap = null;
               this.pathQueue = null;
               this.firstVertex = null;
               this.vertexToHighLight = null;
               
               this.needGraphBuilding = true;
               this.needSolving = true;
               this.needHighLighting = true;
               this.isFinished = false;
       }
       
       
       @Override
       public void initialise(Maze m) throws SolveException
       {
               this.maze = m;
               this.graphBuildQueue = new LinkedList<Vertex>();
               this.vertexMap = new HashMap<Integer,Vertex>();
               this.pathQueue = new PriorityQueue<Path>();
               
               this.needGraphBuilding = true;
               this.needSolving = true;
               this.needHighLighting = true;
               this.isFinished = false;
               
               this.vertexToHighLight = null;
               this.firstVertex = findStart();
               this.firstVertex.weight = 0;
               
               //For the build graph phase.
               this.graphBuildQueue.add(firstVertex);
               vertexMap.put(firstVertex.number, firstVertex);         //Add the first vertex to the map
       }
       
       @Override
       public boolean isDone()
       {
               return isFinished;
       }
       

       /**
        * Find the start position anywhere in the maze.
        * Place the start item in the vertex map and
        * enqueue the start item.
        * @return The vertex of the start position.
        */
       private Vertex findStart() throws SolveException
       {
               int xSize = maze.getSizeX();
               int ySize = maze.getSizeY();
               
               
               for(int x = 0; x < xSize; x++)
               {
                       for(int y = 0; y < ySize; y++)
                       {
                               MazeElement current = maze.getElement(x, y);
                               
                               if(current.getSolveState() == MazeElement.SOLVE_START)
                               {
                                       int vertexNumber = x + (y * xSize);
                                       Vertex startVertex = new Vertex(vertexNumber);
                                       
                                       return startVertex;
                               }
                       }
               }
               
               throw new SolveException("DijkstraShortestSolve.findStart(): Unable to find maze start.");
       }

       /**
        * Calls the underlying function depending on which phase we are currently in.
        */
       @Override
       public void tick() throws SolveException
       {
               if(isFinished)
                       throw new SolveException("DijkstraShortestSolve.tick(): Already solved.");
               
               //Graph building
               if(needGraphBuilding)
               {
                       graphBuildTick();
               }
               //Solving
               else if(needSolving)
               {
                       solveTick();
               }
               //Valid path highlighting
               else if(needHighLighting)
               {
                       highLightTick();
               }
               //Done
               else
               {
                       isFinished = true;
               }
       }
       

       /**
        * Executes one step of the graph build algorithm.
        * This algorithm uses breadth first search.
        * Breadth-first is easier to make tick-compatible.
        * @throws SolveException When called when already finished or other errors.
        */
       private void graphBuildTick() throws SolveException
       {
               if(graphBuildQueue.isEmpty())
                       throw new SolveException("DijkstraShortestSolve.graphBuildTick(): Graph already build.");
               
               
               Vertex currentVertex = graphBuildQueue.poll();
               
               //Decode vertex number to x and y
               int xSize = maze.getSizeX();
               int x = currentVertex.number % xSize;
               int y = currentVertex.number / xSize;
               
               //Check the tunnels for the first node
               checkAllDirections(x, y, currentVertex, null, 1);
               
               
               //Signal that we are finished
               if(graphBuildQueue.isEmpty())
               {
                       this.needGraphBuilding = false;
                       
                       //Wipe clean all the graph building colors.
                       maze.clearSolveState();
                       
                       //For the solve phase.
                       this.pathQueue.add( new Path(firstVertex, 0));
               }
       }
       
       /**
        * Executes the Dijkstra algorithm to determine the shortest path.
        * @throws SolveException When unable to find an exit.
        */
       private void solveTick() throws SolveException
       {
               if(pathQueue.isEmpty())
                       throw new SolveException("DijkstraShortestSolve.solveTick(): Empty path queue.");
               
               int mazeWidth = maze.getSizeX();
               
               
               Path currentPath = pathQueue.poll();
               Vertex currentVertex = currentPath.dest;
               
               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)
               {
                       //Signal that we are finished
                       this.needSolving = false;
                       
                       //Save the vertex
                       this.vertexToHighLight = currentVertex;
                       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 > currentVertex.weight + e.weight)
                       {
                               connectedVertex.weight = currentVertex.weight + e.weight;
                               connectedVertex.prev = currentVertex;
                               pathQueue.add( new Path(connectedVertex, connectedVertex.weight) );
                       }
               }
               
               if(pathQueue.isEmpty())
                       throw new SolveException("DijkstraShortestSolve.solveTick(): No exit defined.");
       }
       
       /**
        * Executes an algorithm to paint the shortest path.
        * It follows the Vertex.prev data member so it will draw the path backwards.
        * @throws SolveException When unable to find an exit.
        */
       private void highLightTick()
       {
               //Calculate the shortest distance by checking all edges.