1. 首页
  2. 问答
  3. Java中的迷宫求解器问题

Java中的迷宫求解器问题

2014-03-06 110 views
0

现在我已经知道它停止无限重复，但它只是一遍又一遍地尝试相同的错误路径。有谁知道有办法让它尝试不同的路径吗？Java中的迷宫求解器问题

关键的数字： 0是开放 1是一堵墙 2是路径的一部分 3是迷宫结束

public class Maze{ 
    public static void main(String[] args){ 
    int[][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 
     {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1}, 
     {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1}, 
     {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1}, 
     {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1}, 
     {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1}, 
     {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1}, 
     {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1}, 
     {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1}, 
     {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1}, 
     {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, 
     {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1}, 
     {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1}, 
     {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1}, 
     {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1}, 
     {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1}, 
     {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1}, 
     {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1}, 
     {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1}, 
     {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1}, 
     {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}}; 
    boolean[][] posCheck = new boolean[maze.length][maze[0].length]; 
    int r = 0; 
    int c = 0; 
    for(int row = 0; row < maze.length; row++){ 
     for(int col = 0; col < maze[row].length; col++){ 
     if(maze[row][col]==0){ 
      r = row; 
      c = col; 
     } 
     } 
    } 
    maze[r][c] = 3; 
    mazeSolver(1, 0, maze, posCheck); 
    } 

    public static boolean mazeSolver(int r, int c, int[][]maze, boolean[][] posCheck){ 
    posCheck[r][c] = true; 
    maze[r][c] = 2; 

    if(maze[r][c] == 3){ 
     print(maze); 
     return true; 
    } 

    if((c+1 < maze.length) && maze[r][c+1]==0 && !posCheck[r][c+1] && (mazeSolver(r, c + 1, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && (mazeSolver(r - 1, c, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && (mazeSolver(r, c - 1, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && (mazeSolver(r + 1, c, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    print(maze); 
    return false; 
    } 

    public static void print(int[][] maze){ 
    for(int row = 0; row<maze.length; row++){ 
     for(int col = 0; col<maze[row].length; col++) 
     System.out.print(maze[row][col]); 
     System.out.println(); 
    } 
    } 
}

来源

2014-03-06 user3390133

+1

数字0,1,2和3是什么意思 – stakSmashr

+4

也许你应该从一个较小的迷宫开始，让自己工作？这样你可以更容易地发现错误。 – Keppil

+0

即使有一天你得到这个有限的递归，我预见你会在栈上传递一个数组，每次递归调用时都会有一个数组。 –

回答

1

您需要跟踪它的定位你有已经访问过。一个简单的方法是创建一个与你的迷宫大小相同的2d布尔数组，并且当你的递归方法首次击中它时标记一个位置为真。除了您的墙检查外，您还需要添加wasVisited检查。

来源

2014-03-06 21:41:24

3

我已将调试输出添加到您的mazeSolver函数的每个分支。正如你所看到的，任何分支都不会被调用，因为第三个if块中的递归调用从未完成评估。因此它是一个无限递归，这是StackOverflowError的原因。它也表明它只是在两种不同的价值之间来回反弹，这可能是一个问题。

您需要确定您的mazeSolver实际上在做什么 - 为什么无限递归永远不会展开，并对其进行更改以满足其他条件之一。

换句话说，您需要修复您的“递归终止符”，并找出为什么除了[1,1]和[0,1]之外没有其他值被传递。

public static boolean mazeSolver(int r, int c, int[][] maze){ 
System.out.println("mazeSolver(" + r + ", " + c + ", maze)"); 

    if(maze[r][c] == 3) { 
System.out.println(" Equals 3 -- return true"); 
     return true; 
    } else if((c+1 < maze.length) && maze[r][c+1]==0 && (mazeSolver(r, c + 1, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (a) -- return true"); 
     return true; 
    } else if((r-1 >= 0) && maze[r-1][c]==0 && (mazeSolver(r - 1, c, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (b) -- return true"); 
     return true; 
    } 

System.out.println(" Between first and second if-block"); 


    if((c-1 >= 0 && maze[r][c-1]==0) && (mazeSolver(r, c - 1, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (c) -- return true"); 
     return true; 
    } 

System.out.println(" Between second and third if-block"); 

    if((r+1 < maze.length) && maze[r+1][c]==0 && (mazeSolver(r + 1, c, maze))){ 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (d) -- return true"); 
     return true; 
    } 

System.out.println(" return false"); 
    return false; 
}

}

输出：

[R:\jeffy\programming\sandbox\xbnjava]java Maze 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block

...等等等等...

mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
Exception in thread "main" java.lang.StackOverflowError 
     at sun.nio.cs.SingleByte.withResult(Unknown Source) 
     at sun.nio.cs.SingleByte.access$000(Unknown Source) 
     at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source) 
     at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source) 
     at java.nio.charset.CharsetEncoder.encode(Unknown Source) 
     at sun.nio.cs.StreamEncoder.implWrite(Unknown Source) 
     at sun.nio.cs.StreamEncoder.write(Unknown Source) 
     at java.io.OutputStreamWriter.write(Unknown Source) 
     at java.io.BufferedWriter.flushBuffer(Unknown Source) 
     at java.io.PrintStream.write(Unknown Source) 
     at java.io.PrintStream.print(Unknown Source) 
     at java.io.PrintStream.println(Unknown Source) 
     at Maze.mazeSolver(Maze.java:64) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
    at Maze.mazeSolver(Maze.java:82)

...等等等等...

来源

2014-03-06 21:55:14 aliteralmind

+0

我已经修复了无限递归，但现在它只是一直经历同样的错误路径 – user3390133

+0

所以做一些事情不同。添加一些更相关的调试来帮助你。添加一些*条件*调试，例如'if（someConditionIsTrue）{System.out.println（“some related information”）; }'所以你不会被输出压倒。你也可以说'java maze> temp.txt'，这样你就可以在文本编辑器中分析输出。试一试！ – aliteralmind

1

http://www.astrolog.org/labyrnth/algrithm.htm http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap

我最近一直在编写一个迷宫应用程序，发现上述网站在理解这些概念方面非常有用。我创建了类来代表Maze，Cell &边缘的图形作为Cells（节点）&边缘的集合。有一次，我还遇到了一个问题，没有完成搜索路径&需要更好地管理哪些单元已被访问过。我反复回到死胡同，因为我的算法没有跟踪Cell已经被访问过。这听起来和你的问题非常相似。

来源

2014-03-06 23:01:39 onesixtyfourth

相关问题

 相关问题