Итак, я пишу программу, которая генерирует, а затем решает лабиринт. У меня есть все, кроме этой маленькой вещи. Маркер в лабиринте дойдет до второго до последнего шага завершения лабиринта, а затем остановится, а затем переместится в другое направление. Я работаю над этим около 2 часов, отслеживая свой код и, похоже, не могу найти, где и почему он становится неакренным при последнем ходу.Программа лабиринта не может закончиться
Правило лабиринта в том, что X
являются стенами и не могут быть перемещены через, O
возможные области, которые могут быть перемещены через и .
является отправной точкой. -
- это пути, к которым я уже переехал. Маркер может перемещаться в любом порядковом или кардинальном направлении (север, северо-восток и т. Д.).
У меня есть две матрицы, одна называется mat
, который отображается пользователю с X
х и O
х и -
-х гг. У меня также есть другая матрица под названием 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();
}
}
Это лабиринт, перед тем как маркер перемещается по нему.
Это лабиринт в конце. Обратите внимание, что, когда маркер должен двигаться на северо-запад, чтобы закончить лабиринт, он остается в том же месте на следующем повороте, а затем движется на юг по очереди.
Вы пробовали отладить его, перейдя через код, чтобы узнать, что происходит? – Andreas
Да, я проследил его несколько раз и не понимаю, почему он не перемещается на северо-запад на последнем шаге. Я попытался разместить инструкцию 'System.out.println' для всякий раз, когда маркер перемещается на северо-запад и печатается, когда он должен был двигаться на последнем шаге, но место оставалось« O » –
@ Andreas http: //i.imgur .com/4fkKYM7.png –