Java中的迷宫寻径器

Question

我想用递归法解迷宫。在下面的代码中，MazeCord是程序员创建的类型，它存储坐标类型位置。格式为mazecord（int x，int y）。现在编译时，我的程序会到达方法的某些部分，而忽略另一部分，因此在所有情况下都会显示“未找到路径”，并且只在LinkedList mazePath中存储开始位置。search（）方法中有一个被注释掉的部分，这是我尝试的另一种方法，但我很确定它是错误的，不是这样做的。

感谢您的帮助。

递归代码：

/**返回迷宫中的路径。第一个元素是起始位置，最后一个元素是退出位置。如果没有路径，或者在搜索之前调用了路径，则返回空列表。

@返回迷宫路径*/

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

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

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（）方法的Helper函数，该函数将执行实际递归，以获取通过maze@param行的路径currentLoc@param col的行currentLoc@return true的列（如果路径可用）*/

    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

首先，我想建议你这个链接，它解释了最常见的寻路算法之一。

我认为这篇教程将非常适合你的要求，因为它以网格为例。

不需要使用递归函数来执行寻路算法。您可以保存两个列表：一个是已经“检查”的单元格/磁贴，另一个是尚未检查的单元格/磁贴。

依次从要开始路径的点开始，并检查从该点可以到达的所有单元格/分幅，如：

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（）只检查给定位置是否不是墙，并且尚未检查。当然，你也可以进行对角线检查！

此时，您想从要添加更多单元格的位置找到下一个单元格/磁贴，您可以通过检查所有“未检查”的单元格/磁贴并应用于每个“权重”函数来做到这一点，该函数将为您提供给定目的地的最佳单元格/磁贴，基本实现可能是这样的：

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

此函数将允许您找到要导航到的最合适的单元格/磁贴，一旦找到它（权重最低的单元格/磁贴），您将移动到此函数并再次调用第一个函数以添加更多单元格/磁贴。

当移动到的单元格/磁贴是目标时，或者在调用addCells（）时，如果不添加任何新的单元格/磁贴，则将停止。

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