Java 中的迷宫寻路器

Question

我正在尝试使用递归解决迷宫问题。在下面的代码中，MazeCoord 是程序员创建的类型，用于存储坐标类型位置。格式为 MazeCoord(int x, int y)。我的程序现在编译时，到达方法的某些部分并忽略其他部分，因此在所有情况下都说 "No Path Found" 并且仅将起始位置存储在 LinkedList mazePath 中。 search() 方法中有一个注释掉的部分，这是我尝试的另一种方法，但我很确定这是错误的，而不是这样做的方法。

感谢任何帮助。

递归代码：

/** Returns穿过迷宫的路径。第一个元素是起始位置，并且最后一个元素是出口位置。如果没有路径，或者如果这被称为搜索前，return 的空列表。

@return迷宫小路 */

public LinkedList<MazeCoord> getPath() {
       return mazePath; 
}

/** 如果有的话，找到一条穿过迷宫的路径。客户端可以访问通过 getPath 方法找到的路径。 @return 是否找到路径。 */

public boolean search() {  
       currentLoc = new MazeCoord(startLoc.getRow(), startLoc.getCol());
       visitedPath = new boolean[mazeData.length][mazeData[0].length];

       mazePath=new LinkedList<MazeCoord>();

       if(hasWallAt(startLoc) || hasWallAt(endLoc)){    
       return false;
       }
       else{
           mazePath.add(currentLoc);
           return appendToSearch(currentLoc.getRow(), currentLoc.getCol());
       }

       /**
       System.out.println("try1");
       mazePath.add(new MazeCoord(startLoc.getRow(), startLoc.getCol()));
       boolean searchResult = appendToSearch(numRows()-1, numCols()-1);

       System.out.println("test: " + searchResult);
       System.out.println("test2: row, col --> " + (numRows()-1) + " , " +  (numCols()-1));
       System.out.println("test3: wallValue:" + hasWallAt(new  MazeCoord(numRows()-1,numCols()-1)));

       if(searchResult){
           System.out.println("try2");
           mazePath.add(new MazeCoord(numRows()-1, numCols()-1));
       }
       return searchResult;
       */
   }

/**将执行的 search() 方法的辅助函数获得迷宫路径的实际递归 @param row 当前位置所在的行 @param col 当前位置的列 @return 如果路径可用则为真 */

    private boolean appendToSearch(int row, int col) {


        //Check if within the maze
        if((row - 1 < 0) || (col - 1 < 0) || (row + 1 > numRows()) || (col + 1 >  numCols())){
            return false;
        }
        //Check if the position is the exit location
        if(row == endLoc.getRow() && col == endLoc.getCol()){
            mazePath.add(new MazeCoord(row, col));
            return false;
        }
        //Check for Wall
        if(hasWallAt(new MazeCoord(row, col))){
            return false;
        }
        //Check if the position has already been visited
        if(visitedPath[row][col]){
            return false;
        }
        //If all pass --> add to visitedPath
        visitedPath[row][col]=true;

        //Check to the Right
        if(appendToSearch(row, col + 1)){
           mazePath.add(new MazeCoord(row, col + 1));
           return true;
        }
        //Check Downwards
        else if(appendToSearch(row + 1, col)){
            mazePath.add(new MazeCoord(row + 1, col));
            return true;
        }
        //Check to the Left
        else if(appendToSearch(row, col - 1)){
            mazePath.add(new MazeCoord(row, col - 1));
            return true;
        }
        //Check Upwards
        else if(appendToSearch(row - 1, col)){
            mazePath.add(new MazeCoord(row - 1, col));
            return true;
        }
        return false;
    }

Answer 1

首先，我想向您推荐 this link，它解释了最常见的寻路算法之一。

可以找到您也可以遵循的简短教程 here 我认为本教程将非常符合您的要求，因为它以网格为例。

不需要使用递归函数来执行寻路算法。您可以做的是保留两个列表：一个已经 'checked' cells/tiles 和另一个还没有的列表。

您将从您想要开始路径的点开始，并检查从该点可以到达的所有 cells/tiles，例如：

void addCells(Point current) {
   // Left
   if (emptyAndNotChecked(current.x-1,current.y)) // Checking for walls here
      cellsToCheck.add(new Point(x-1,y)) // Adding this cell to the list
   // Right
   if (emptyAndNotChecked(current.x+1,current.y))
      cellsToCheck.add(new Point(x+1,y))
   // Top
   if (emptyAndNotChecked(current.x,current.y+1))
      cellsToCheck.add(new Point(x,y+1))
   // Bottom
   if (emptyAndNotChecked(current.x,current.y-1))
      cellsToCheck.add(new Point(x,y-1))
}

其中 emptyAndNotChecked() 只是检查给定位置是否不是墙并且尚未检查。当然你也可以进行对角线检查！

此时你想从你想添加更多单元格的地方找到下一个 cell/tile，你可以通过检查所有“未选中”cells/tiles 并应用到每个单元格来做到这一点“重量”功能的 a 将为您提供给定目的地的最佳 cell/tile，基本实现可能是这样的：

float weight(Point current,Point end) {
   return Math.sqrt(Math.pow(current.x-end.x,2)+Math.pow(current.y-end.y,2));
}

这个函数可以让你找到最合适的 cell/tile 来导航，一旦找到它（权重最低的那个），你就移动到这个并再次调用第一个函数来添加更多cells/tiles.

当您移动到的 cell/tile 是目的地时，或者当调用 addCells() 时您没有添加任何新的 cell/tile。

，您将停止

当然这只是一种基本的方法，还有很多可以应用的改进。希望这对您有所帮助！

Java 中的迷宫寻路器

Maze path finder in Java

java

recursion

maze

path