I am trying to implement a 2 dimensional matrix as a maze. There is a starting point, an ending point (randomly chosen). And to make it little complicated, there are obstacles and agents. If the rat runs into an obstacle, it should backtrack and find the correct path. If it runs into an agent, it gets destroyed. Here's a sample 4x4 matrix
1 7 1 1
2 1 1 0
1 0 1 0
1 1 1 9
Key: 0 is an obstacle, 2 is an agent, 7 is the starting point, 9 is the goal/ending point. 1 means that is is safe to move there.
The correct solution for this matrix would be:
0 1 1 0
0 0 1 0
0 0 1 0
0 0 1 1
But the rat is not intelligent (at least for this program) , so I am implementing a brute force algorithm, with random moves.
I have tried to implement this using a recursive function called mazeUtil().
Below is the function:
maze[][] is the randomized initial matrix that the rat moves through.
solution[][] is the solution matrix that will keep track of the moves.
(x, y) is the current position in the grid
n is the size of the matrix (it is a square matrix).
public static void mazeUtil(int maze[][], int solution[][], int x, int y, int n)
{
if(x == goal[0] && y == goal[1])
{
solution[x][y] = 1;
return;
}
int check = moveCheck(maze, x, y, n);
//moveCheck() return 0 for Obstacle, 1 for safe path, 2 for agent, 7 for starting point (also safe path), 9 for goal (safe path)
if (check == 2){
solution[x][y] = 1;
out.println("Oops! Ran into an agent!");
return;
}
else if(check == 0)
{
//What should I put here?
}
else if(check == 1 || check == 7 || check == 9)
{
solution[x][y] = 1;
Random newRandom = new Random();
int temp = newRandom.nextInt(3);
if(temp == 0){ //move up if possible? x--
if(x > 0)
mazeUtil(maze, solution, x-1, y, n);
else
mazeUtil(maze, solution, x+1, y, n);
}
else if (temp == 1){
if (x < n-1)
mazeUtil(maze, solution, x+1, y, n);
else
mazeUtil(maze, solution, x-1, y, n);
}
else if(temp == 2){
if (y < n-1)
mazeUtil(maze, solution, x, y+1, n);
else
mazeUtil(maze, solution, x,y-1, n);
}
else if (temp == 3){
if (y > 0)
mazeUtil(maze, solution, x, y-1, n);
else
mazeUtil(maze, solution, x, y+1, n);
}
}
}
I have to randomize the moves and that's why i have used random function. My function works quite well if it runs into an agent (2). I have also prevented the rat from going out of boundary. And it doesn't have any problem going through the safe path (1). But the problem is when it hits an obstacle. I'm thinking about backtracking. How do I add that into my function? Like save the last step, and do the reverse? And it is quite possible that there is no solution in the maze like this one
7 0 0 9
2 0 1 1
0 1 0 0
1 2 0 1
It would hit an obstacle if it goes right, and hit an agent if it goes down. It cannot move diagonally. That brings me to my second question, how would I terminate my recursive function in that case. At this point the only time it terminates is when it reaches the goal or hits an agent.
Any help would be appreciated. Thanks in advance
A quick point on style, to save some typing later: maze[][], solution[][] and n are all effectively global, and do not change between recursive calls (maze and solution are just passed as references to the same arrays, and n never changes). This is purely style, but you can write this as:
private static int[][] maze;
private static int[][] solution;
private static int n;
public static void mazeUtil(int x, int y) {
...
}
So on to your solution: the first point is I don't see how you know when you've reached the goal; your mazeUtil function does not return anything. For this kind of recursion, a general approach is for your solver function to return a boolean: true if the goal has been reached and false if not. Once you get a true, you just pass it back all the way up the call stack. Each time you get a false, you backtrack to the next solution.
So I'd suggest:
public static boolean mazeUtil(int x, int y) {
// return true if goal found, false otherwise
...
}
Next, I'm not sure what the practical difference between an agent and an obstacle is: running in to either causes you to backtrack. So I'd think that bit of code would be:
if (check == 2) {
out.println("Oops! Ran into an agent!");
return false;
}
if (check == 0)
out.println("Oops! Ran into an obstacle!");
return false;
}
Then the recursive bit: one point here is you do not ever reset the solution to 0 for failed attempts (actually, as the final algorithm will never backtrack more than a single step this is not actually that important, but it's good to illustrate the general approach). Given what we have so far, this should now be something like:
if (check == 9) {
out.println("Found the goal!");
return true;
}
if (check == 1 || check == 7) {
// add current position to solution
solution[x][y] = 1;
// generate random move within bounds
int nextX = ...
int nextY = ...
if (mazeUtil(nextX, nextY)) {
// we've found the solution, so just return up the call stack
return true;
}
// this attempt failed, so reset the solution array before returning
solution[x][y] = 0;
return false;
}
// shouldn't ever get here...
throw new IllegalStateException("moveCheck returned unexpected value: " + check);
Right, so far so good, but there's still a problem. As soon as one of the mazeUtil calls returns a value (either true or false) it will return that all the way up the calls stack. So if you happen to find the exit before an agent or an obstacle, all good, but that's quite unlikely. So instead of trying a single move when recursing, you need to try all possible moves.
WIth a supporting class Point, containing a simple x and y pair:
if (check == 1 || check == 7) {
// add current position to solution
solution[x][y] = 1;
// generate an array of all up/down/left/right points that are within bounds
// - for a random path need to randomise the order of the points
Point[] points = ...
for (Point next : points) {
if (mazeUtil(next.x, next.y)) {
// we've found the solution, so just return up the call stack
return true;
}
}
// this attempt failed, so reset the solution array before returning
solution[x][y] = 0;
return false;
}
And I think that's about as far as you can go with a totally ignorant rat! To see how this works, consider the following maze:
7 1
0 9
Starting at "7", possible moves are Down and Right.
From the "1", possible moves are Down and Left:
And that's all that can ever happen. So using * for a return-false-backtrack, and ! for a success, any of the following are possible:
R-D!
R-L-D*-R-D!
R-L-R-L-R-L-R-L (keep going for a long, long time....) R-L-R-D!
So for a solvable maze, and a truly random generator, this will eventually solve the maze, although it could take a very long time. Something to note with this though, is it does not really backtrack that much: only ever a single step from a 2 or 0 node.
However, there's still the problem of the unsolveable maze, and I don't think that is possible given a totally ignorant rat. The reason for this is that for a brute force recursion like this, there are only two possible termination conditions:
And with a totally ignorant rat, there is no way to detect the second!
Consider the following maze:
7 1 1 1
0 0 0 0
0 0 0 0
1 1 1 9
The totally ignorant rat will just wander left and right across the top row forever, and so the program will never terminate!
The solution to this is that the rat must be at least a bit intelligent, and remember where it has been (which will also make the solveable maze run quicker in most cases and backtrack along entire paths instead of only for single nodes). However, this answer is getting a bit too long already, so if you're interested in that I'll refer you to my other maze-solving answer here: Java Recursive Maze Solver problems
Oh, just two final points on Random:
Hope this all helps!