Reputation: 240
Maze Program Can't Finish
So I'm writing a program that generates and then solves a maze. I have everything working except for this one little thing. The marker in the maze will get to the second to last step of completing the maze and then stop on and then move to a different direction. I've been working on this for about 2 hours now, tracing my code and can't seem to locate where or why it goes wacky at the last move.
The rules for the maze are that X are walls and CAN'T be moved through, O are possible areas that CAN be moved through, and the . is the starting point. The - are paths that I have already moved to. The marker can move in any ordinal or cardinal direction (North, Northeast, etc).
I have two matrices, one called mat which is displayed to the user with X's and O's and -'s. I also have another matrix called visited which is the same size as mat and is kind of the behind the scenes matrix which keeps track of what coordinates I can or can't move to. It stores W for walls, Y for coordinates I've already visited, and N for coordinates I can visit.
The way I solve the maze is by checking for possible moves starting from North and moving counterclockwise around the compass until I find a possible move. The marker cannot move to spot it has already moved.
If I come across a split path with more than one possible move, I place the coordinates of that position in two stacks called splitx for row and splity for column so I can come back to it later. If I hit a dead end where every square is either a wall or already visited, I backtrack to the last coordinates in my split path stacks, close off the path I just moved to, and pop the top values of the stack.
I also have another stack called visitStack which stores every move I make as N for North, NE for Northeast, on and on. This lets me retrace my moves and go to the last split path I encountered. Here is the code and below it, some chosen output. If you have any questions about the code or output or just clarification in general, ask away.
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();
}
}
Here is the maze before the marker moves through it.
Here is the maze at the end. Notice how when the marker should move northwest to finish the maze, it stays in the same spot the next turn and then moves south the turn after that.
Upvotes: 2
Views: 394
Answers (1)
Reputation: 159086
So, you're in position (1,1) and find two moves: NW and S.
if(numMoves() > 1) fires and pushes both on the stack.
if(numMoves() > 0) fires and applies NW move, leaving you at (0,0).
if(numMoves() == 0) fires and starts backtracking because there are no moves from (0,0).
2 issues:
- Where is the code that detects that you found the exit?
if(numMoves() == 0)is callingnumMoves()using the new coordinates. Change it toelse.
Upvotes: 3
Related Questions
- Maze 2D Recursive Algorithm Dead End Issue
- Maze Recursion Code Finishes Maze but Returns Errors
- Java maze solving issue
- java:Maze Solver using Backtracking stuck in Loop
- Maze solver looping issue java
- Maze solver gets stuck in a loop at a dead-end
- Maze solving algorithm gets stuck between two places
- Algorithmic error in java maze generator
- Why won't my Java maze work?
- Problem with Maze Algorithm