dijkstrashortestsolve.java

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

               int maxDepth = Integer.MAX_VALUE;
               for(Edge e : this.vertexToHighLight.edges)
               {
                       if(e.dest == this.vertexToHighLight.prev && e.weight < maxDepth)
                       {
                               maxDepth = (int)e.weight;
                       }
               }
               
               int width = maze.getSizeX();
               int x = this.vertexToHighLight.number % width;
               int y = this.vertexToHighLight.number / width;
               
               if(directionIsAccessible(x, y, Direction.NORTH))
                       highLightPathIfValid(x, y-1, Direction.SOUTH, this.vertexToHighLight.prev, maxDepth);
               
               if(directionIsAccessible(x, y, Direction.EAST))
                       highLightPathIfValid(x+1, y, Direction.WEST, this.vertexToHighLight.prev, maxDepth);
               
               if(directionIsAccessible(x, y, Direction.SOUTH))
                       highLightPathIfValid(x, y+1, Direction.NORTH, this.vertexToHighLight.prev, maxDepth);
               
               if(directionIsAccessible(x, y, Direction.WEST))
                       highLightPathIfValid(x-1, y, Direction.EAST, this.vertexToHighLight.prev, maxDepth);
               
               maze.getElement(x, y).visit();
               this.vertexToHighLight = this.vertexToHighLight.prev;
               
               //If weight == 0 we re back at the beginning.
               if(this.vertexToHighLight.weight == 0)
               {
                       this.vertexToHighLight = this.vertexToHighLight.prev;
                       this.needHighLighting = false;
               }
       }
       
       /**
        * Check all direction
        * @param x Coordinate.
        * @param y Coordinate.
        * @param previous Previous vertex, used to setup edges in a different function.
        * @param origin The direction which should be skipped (ignored if null).
        * @param weight Current weight of the path.
        */
       private void checkAllDirections(int x, int y, Vertex previous, Direction origin, int weight)
       {
               if((origin == null || Direction.NORTH != origin) &&
               directionIsAccessible(x, y, Direction.NORTH))
               {
                       findNewNode(x, y-1, Direction.SOUTH, previous, weight);
               }
               if((origin == null || Direction.EAST != origin) &&
               directionIsAccessible(x, y, Direction.EAST))
               {
                       findNewNode(x+1, y, Direction.WEST, previous, weight);
               }
               if((origin == null || Direction.SOUTH != origin) &&
               directionIsAccessible(x, y, Direction.SOUTH))
               {
                       findNewNode(x, y+1, Direction.NORTH, previous, weight);
               }
               if((origin == null || Direction.WEST != origin) &&
               directionIsAccessible(x, y, Direction.WEST))
               {
                       findNewNode(x-1, y, Direction.EAST, previous, weight);
               }
       }
       
       /**
        * Used to find a new node. Is used to skip parts that only have to accessible directions.
        * And only considers 'intersections' and SOLVE_END as nodes.
        * @param x Coordinate.
        * @param y Coordinate.
        * @param origin The direction which should be skipped, because we came from this direction.
        * @param previous The previous vertex used to set up edges.
        * @param weight The weight of the path.
        */
       private void findNewNode(int x, int y, Direction origin, Vertex previous, int weight)
       {
               MazeElement current = maze.getElement(x, y);
               int walls = countWalls(current);
               
               //A new weighted node
               if(walls < 2 || current.getSolveState() == MazeElement.SOLVE_END)
               {
                       current.visit();
                       processNode(x, y, previous, origin, weight);
               }
               //2 nodes, find the end we didn't come from
               else if(walls == 2)
               {
                       checkAllDirections(x, y, previous, origin, weight+1);
               }
       }
       
       /**
        * Used to generate a new vertex at the current location and setup edges between vertexes.
        * And add the vertex to the Queue.
        * @param x Coordinate.
        * @param y Coordinate.
        * @param previous Previous vertex used to setup edges.
        * @param origin The direction we came from, so we don't keep going in circles.
        * @param pathWeight The weight of the current path.
        */
       private void processNode(int x, int y, Vertex previous, Direction origin, int pathWeight)
       {
               int vertexNumber = x + (y * maze.getSizeX());
               Vertex current;
               
               //Vertex already present in the vertex map, check edges.
               if(vertexMap.containsKey(vertexNumber))
               {
                       current = vertexMap.get(vertexNumber);
                       
                       //Check every edge if it is already connected to this one
                       for(Edge e : current.edges)
                       {
                               if(e.dest == previous)
                               {
                                       //No need to add edges or to further examine the node.
                                       return;
                               }
                       }
                       
                       //Add the missing edges
                       current.edges.add(new Edge(previous, pathWeight));
                       previous.edges.add(new Edge(current, pathWeight));
                       
                       //No need to further examine the node.
                       return;
               }
               //A new vertex, add it and setup edges.
               else
               {
                       current = new Vertex(vertexNumber);
                       vertexMap.put(vertexNumber, current);
                       
                       current.edges.add(new Edge(previous, pathWeight));
                       previous.edges.add(new Edge(current, pathWeight));
                       
                       //Add it to the graph build queue.
                       this.graphBuildQueue.add( current );
               }
       }
       
       /**
        * Returns true if a direction is accessible (not outside the maze and no wall).
        * @param x Coordinate of the current location.

        * @param y Coordinate of the current location.
        * @param d Direction to check.
        * @return True if a direction is accessible.
        */
       private boolean directionIsAccessible(int x, int y, Direction d)
       {
               int xSize = maze.getSizeX();
               int ySize = maze.getSizeY();
               
               MazeElement current = maze.getElement(x, y);
               
               if(d == Direction.NORTH && y > 0 && ! current.getNorth())
                       return true;
               else if(d == Direction.EAST && x < (xSize-1) && ! current.getEast())
                       return true;
               else if(d == Direction.SOUTH && y < (ySize-1) && ! current.getSouth())
                       return true;
               else if(d == Direction.WEST && x > 0 && ! current.getWest())
                       return true;
               
               return false;
       }
       
       /**
        * Count the surrounding walls.
        * @param element
        * @return The number of walls.
        */
       private int countWalls(MazeElement element)
       {
               int walls = 0;
               
               if(element.getNorth())
                       walls++;
               
               if(element.getEast())
                       walls++;
               
               if(element.getSouth())
                       walls++;
               
               if(element.getWest())
                       walls++;
               
               return walls;
       }
       
       /**
        * Find the end of the path and paints it if it's the one we're looking for.
        * @param current
        */
       private boolean highLightPathIfValid(int x, int y, Direction origin, Vertex target, int maxDepth)
       {
               if(maxDepth < 1)
               {
                       return false;
               }
               
               MazeElement current = maze.getElement(x, y);
               
               //Found a node
               if(countWalls(current) < 2 || current.getSolveState() == MazeElement.SOLVE_START)
               {
                       int vertexNumber = x + (y * maze.getSizeX());
                       Vertex found = vertexMap.get(vertexNumber);
                       
                       if(found == target)
                       {
                               current.visit();
                               return true;
                       }
                       else
                               return false;
               }
               
               //Keep searching for a node
               boolean paint = false;
               if(origin != Direction.NORTH && directionIsAccessible(x, y, Direction.NORTH))
                       paint = highLightPathIfValid(x, y-1, Direction.SOUTH, target, maxDepth-1);
               
               else if(origin != Direction.EAST && directionIsAccessible(x, y, Direction.EAST))
                       paint = highLightPathIfValid(x+1, y, Direction.WEST, target, maxDepth-1);
               
               else if(origin != Direction.SOUTH && directionIsAccessible(x, y, Direction.SOUTH))
                       paint = highLightPathIfValid(x, y+1, Direction.NORTH, target, maxDepth-1);
               
               else if(origin != Direction.WEST && directionIsAccessible(x, y, Direction.WEST))
                       paint = highLightPathIfValid(x-1, y, Direction.EAST, target, maxDepth-1);
               
               //Paint the element if it's the right path.
               if(paint)
               {
                       current.visit();
                       return true;
               }
                       
               
               //Dead end
               return false;
       }
}