2015-09-27 84 views
2

所以我正在编写一个程序,生成并解决迷宫。除了这个小东西外,我已经做好了一切工作。迷宫中的标记将完成迷宫的第二步到最后一步,然后停下来,然后移动到不同的方向。我一直在为此工作了大约2个小时,跟踪我的代码,似乎无法找到最后一步走向哪里或为何变得古怪。迷宫程序无法完成

迷宫的规则是X是墙壁,不能移动,O是可以移动的区域,.是起点。 -是我已经转移到的路径。标记可以以任何顺序或主要方向(北,东北等)移动。

我有两个矩阵,一个叫mat,向用户显示XO-'s。我还有另一个叫做visited的矩阵,其大小与mat相同,并且是跟踪我可以或不可以移动到的坐标的幕后矩阵。它为墙壁存储W,我已经访问过的坐标为Y,我可以访问的坐标为N

我解决迷宫的方法是检查可能的移动从北部开始,逆时针绕指南针移动,直到找到可能的移动。标记不能移动以发现它已经移动。

如果遇到有多个可能移动的分割路径,我将该位置的坐标放在两个堆栈中,分别称为splitx,列为splity,然后我可以稍后再回来。如果我遇到了每个方格都是墙壁或已经访问过的死角,我会回溯到分割路径堆栈中的最后一个坐标,关闭刚刚移动到的路径,并弹出堆栈的最高值。

我还有另一个堆栈,名为visitStack,它存储我为北方的每个移动N,东北的NE,等等。这让我回顾我的动作,并转到我遇到的最后一条分割路径。这里是代码和它下面的一些选择输出。如果您对代码或输出有任何疑问或者只是一般性的澄清,请离开。

import java.util.*; 

public class MazeLab 
{ 
    public static void main(String args[]) 
    { 
     Scanner input = new Scanner(System.in); 
     System.out.print("Enter random starting seed ===>> "); 
     int seed = input.nextInt(); 

     Maze maze = new Maze(seed); 
     maze.displayMaze(); 
     maze.solveMaze(); 
    } 
} 

class Maze 
{ 

    private char mat[][];    // 2d character array that stores the maze display 
    private char visited[][];   // 2d character array that works behind to scenes to let me know where I can or can't move 
    private Stack<String> visitStack;   // stack that stores every move I make as N, NE, E, SE, etc 
    private int nowR, nowC;      // coordinates for current position in the matrix 
    private int startRow, startCol;    // coordinates for the starting position 
    private boolean done = false;    // not that important 
    private Stack<Integer> splitx = new Stack<Integer>(); // row coord for split paths 
    private Stack<Integer> splity = new Stack<Integer>(); // col coord for split paths 
    Random random = new Random(); 

    public Maze(int seed) 
    // constructor which generates the random maze, random starting location 
    // and initializes Maze class values. If the random value equals 0 the maze 
    // store an 'X' otherwise it store an 'O' in the maze. 
    { 
     Random randomize = new Random(seed); 
     mat = new char[12][12]; 
     visited = new char[12][12]; 
     for (int r = 0; r < 12; r++) 
      for (int c = 0; c < 12; c++) 
      { 
       if (r == 0 || c == 0 || r == 11 || c == 11) 
        mat[r][c] = 'X'; 
       else 
       { 
        int rndInt = randomize.nextInt(2); 
        if (rndInt == 0) 
         mat[r][c] = 'X'; 
        else 
         mat[r][c] = 'O'; 
       } 
      } 
     mat[0][0] = 'O'; 
     startRow = randomize.nextInt(12); 
     startCol = 11; 
     nowR = startRow; 
     nowC = startCol; 
     mat[startRow][startCol] = '.'; 
     visitStack = new Stack<String>(); 

     for(int i = 0; i < mat.length; i++) 
      for(int k = 0; k < mat[i].length; k++) 
       if(mat[i][k] == 'X') 
        visited[i][k] = 'W'; 
       else 
        visited[i][k] = 'N'; 
//          Avoid going back to the starting point 
     visited[nowR][nowC] = 'Y'; 
    } 


    void displayMaze() 
    // displays the current maze configuration 
    { 
     for (int r = 0; r < 12; r++) 
     { 
      for (int c = 0; c < 12; c++) 
       System.out.print(mat[r][c] + " "); 
      System.out.println(); 
     } 
     System.out.println(); 

     if(done == false) 
      pause(); 
    } 


    public void solveMaze() 
    { 
    // for testing purposes, this is not the real method 
     for(int i = 0; i < 15; i++) 
     { 
      getMove(); 
      displayMaze(); 
     } 
    } 

    private int numMoves() 
    // This method determines if a position has a valid move or not  
    { 
     int moves = 0; 
     if(nowR != 0 && visited[nowR-1][nowC] == 'N') 
      moves++; 
     if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N') 
      moves++; 
     if(nowC != 11 && visited[nowR][nowC+1] == 'N') 
      moves++; 
     if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N') 
      moves++; 
     if(nowR != 11 && visited[nowR+1][nowC] == 'N') 
      moves++; 
     if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N') 
      moves++; 
     if(nowC != 0 && visited[nowR][nowC-1] == 'N') 
      moves++; 
     if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N') 
      moves++; 
     return moves; 
    } 

    private void getMove() 
    { 
     if(numMoves() > 1) 
     { 
//          checks for split paths 
//          north 
      if(nowR != 0 && visited[nowR-1][nowC] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          northwest 
      if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          west 
      if(nowC != 0 && visited[nowR][nowC-1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          southwest 
      if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          south 
      if(nowR != 11 && visited[nowR+1][nowC] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          southeast 
      if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          east 
      if(nowC != 11 && visited[nowR][nowC+1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
//          northeast 
      if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N') 
      { 
       splitx.push(nowR); 
       splity.push(nowC); 
      } 
     } 
     if(numMoves() > 0) 
     { 
//          moves the marker, oriented to the right 
//          north 
      if(nowR != 0 && visited[nowR-1][nowC] == 'N') 
      { 
       nowR--; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("N"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON NORTH"); 
      } 
//          northwest 
      else if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N') 
      { 
       nowR--; 
       nowC--; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("NW"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON NORTHWEST"); 
      } 
//          west 
      else if(nowC != 0 && visited[nowR][nowC-1] == 'N') 
      { 
       nowC--; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("W"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON WEST"); 
      } 
//          southwest 
      else if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N') 
      { 
       nowR++; 
       nowC--; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("SW"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON SOUTHWEST"); 
      } 
//          south 
      else if(nowR != 11 && visited[nowR+1][nowC] == 'N') 
      { 
       nowR++; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("S"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON SOUTH"); 
      } 
//          southeast 
      else if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N') 
      { 
       nowR++; 
       nowC++; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("SE"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON SOUTHEAST"); 
      } 
//          east 
      else if(nowC != 11 && visited[nowR][nowC+1] == 'N') 
      { 
       nowC++; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("E"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON EAST"); 
      } 
//          northeast 
      else if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N') 
      { 
       nowR--; 
       nowC++; 
       visited[nowR][nowC] = 'Y'; 
       visitStack.push("NE"); 
       mat[nowR][nowC] = '-'; 
//    System.out.println("PUSHING ON NORTHEAST"); 
      } 
     } 
     if(numMoves() == 0) 
     { 
      while(nowR != splitx.peek() && nowC != splity.peek()) 
      { 
       switch(visitStack.pop()) 
       { 
//         have to backtrack the opposite direction i previously went 
        case "N": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR++; 
           break; 
        case "NE": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR++; 
           nowC--; 
           break; 
        case "E": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowC--; 
           break; 
        case "SE": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR--; 
           nowC--; 
           break; 
        case "S": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR--; 
           break; 
        case "SW": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR--; 
           nowC++; 
           break; 
        case "W": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowC++; 
           break; 
        case "NW": visited[nowR][nowC] = 'N'; 
           mat[nowR][nowC] = 'O'; 
           nowR++; 
           nowC++; 
           break; 
        default: System.out.println("SOMETHING WENT WRONG WITH BACKTRACKING"); 
       } 
      } 
//          blocks off dead ends 
//          north 
      if(nowR != 0 && visited[nowR-1][nowC] == 'N') 
       visited[nowR-1][nowC] = 'Y'; 
//          northwest 
      else if(nowR != 0 && nowC != 0 && visited[nowR-1][nowC-1] == 'N') 
       visited[nowR-1][nowC-1] = 'Y'; 
//          west 
      else if(nowC != 0 && visited[nowR][nowC-1] == 'N') 
       visited[nowR][nowC-1] = 'Y'; 
//          southwest 
      else if(nowR != 11 && nowC != 0 && visited[nowR+1][nowC-1] == 'N') 
       visited[nowR+1][nowC-1] = 'Y'; 
//          south 
      else if(nowR != 11 && visited[nowR+1][nowC] == 'N') 
       visited[nowR+1][nowC] = 'Y'; 
//          southeast 
      else if(nowR != 11 && nowC != 11 && visited[nowR+1][nowC+1] == 'N') 
       visited[nowR+1][nowC+1] = 'Y'; 
//          east 
      else if(nowC != 11 && visited[nowR][nowC+1] == 'N') 
       visited[nowR][nowC+1] = 'Y'; 
//          northeast 
      else if(nowR != 0 && nowC != 11 && visited[nowR-1][nowC+1] == 'N') 
       visited[nowR-1][nowC+1] = 'Y'; 

      splitx.pop(); 
      splity.pop(); 
     } 
    } 

    private void pause() 
    { 
     Scanner input = new Scanner(System.in); 
     String dummy; 
     System.out.print("\nPress <Enter> to continue ===>> ");      
     dummy = input.nextLine();        
    } 
} 

这是标记移动通过它之前的迷宫。 enter image description here

这是最后的迷宫。注意当标记应该向西北移动完成迷宫时,它会在下一个回合中停留在同一个地方,然后在回合之后向南移动。

enter image description here

+0

您是否尝试过调试它,单步执行代码以查看发生了什么? – Andreas

+0

是的,我追踪了好几遍,不明白为什么它不会在最后一步向西北方向移动。我试着在标记向西北方向移动时放置一个'System.out.println'语句,并在最后一步移动时打印它,但该点仍然是'O' –

+0

@Andreas http://i.imgur .com/4fkKYM7.png –

回答

3

所以,你在位置(1,1),并找到两个动作:NW和S.

if(numMoves() > 1)火灾和堆栈上推

if(numMoves() > 0)火灾和适用NW移动,让你在(0,0)。

if(numMoves() == 0)由于没有从(0,0)移动,所以发生并开始回溯。

2个问题:

  • 如果是检测你找到了退出的代码?
  • if(numMoves() == 0)正在呼叫numMoves()使用新的坐标。将其更改为else
+0

试图回答+1 –

+0

哇,这让我感到无聊,只需要改变这些if语句的顺序。 –

+0

而且我仍然在处理退出条件的代码/没有解决方案,我无法继续处理这个错误。 –