2 dimensional maze solver recursive function

Question

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

Answer 1

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.

• If you try Down first, it returns false, so the only option left is Right, so you end up on the "1".
• If you try Right first, you still end up on the "1".

From the "1", possible moves are Down and Left:

• If you try Down first, it returns true, which bubbles up the call stack - success!
• If you try Left first, you end up on the "7", so recurse to the previous step.

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:

1. The goal has been found.
2. All possible paths have been tried.

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:

1. You don't need to create a new Random each time - just create a global one and call nextInt each time.
2. nextInt(n) returns between 0 (inclusive) and n (exclusive), so you need nextInt(4) not nextInt(3).

Hope this all helps!

Answer 2

I'd like to do some analysis of your algorithm design before proposing a solution.

You mention that you want to use a random walk algorithm. No problem with that it's a perfectly acceptable (though not necessarily efficient) way to look for a path. However you need to be aware that it has some implications.

1. In general random walk will not tell you when there is no solution. If you just keep trying paths at random you will never exhaust the search tree.
2. If this is unacceptable (i.e. it needs to be able to halt when there is no soltuion) then you need to keep a record of paths already attempted and randomise only those not yet attempted.
3. Random walk won't necessarily find the optimal solution unless there is only one solution. In other words if there are loops / multiple paths in your maze then there's no guarantee you are finding the fastest.

I can't actually see the difference between agents and obstacles in your problem. In both cases you need to backtrack and find another path. If there is a difference then you'll need to point it out.

So assuming your maze could have zero or more successful paths and you are not looking for the optimal path (in which case you really should use A* or similar), the structure of a solution should look something like:

public List<Position> findPath(Set<Position> closedSet, Position from, Position to) {
    if (from.equals(to)) 
         return List.of(to);
    while (from.hasNeighboursNotIn(closedSet)) {
        Position pos = from.getRandomNeighbourNotIn(closedSet);
        closedSet.add(pos);
        List<Position> path = findPath(closedSet, pos, to);
        if (!path.isEmpty())
            return List.of(pos, path);
    }
    closedSet.add(from);
    return Collection.EMPTY_LIST;
}

This uses lots of pseudo-code (e.g. there is no List.of(item, list)) but you get the idea.

Answer 3

if you want to move in random, u need to know the states you've been already in them, so u will need a tree, otherwise u can keep the most left path when the rat is in multi way place.

now lets think of recursive + random. it can not be that hard. you can have a function that returns the list of points it has been in them, and get correct position as input, there is a bit of problem and the idiot rat can got back the way he already came from, so lets solve it with adding previous point as another input for our function.

every thing in place. now we wana know if the idiot rat runs into a dead path or an agent. how about making 2 exceptions for this situations and handling them in recursive function??

well, i don't think there will be any more problems on way. actually i'm temped to try it myselft. that would be fun :D

good luck with the idiot rat

Answer 4

Well, let's imagine I need to solve the same problem by the same way you are solving it. (I think the best solution for it is Path finding, as already mentioned in comments).

1. I will create

   class Point{ public int x; public int y; }

and store coordinates in it.

2. I will store all points the rat visited in List<Point> path

In this solution you do not have problems with previous point (it is the last point in list)

As for algorithm termination -- you use algorithm with randoms. So you can't be sure that your rat will solve the simplest maze like

7 1 1

1 1 1

1 1 1

it is possible that rat will move from (0,0) to (1,0) and from (1,0) to (0,0) forever.

So, let's again imagine that I need to improve your algorithm instead of using good one.

I will store number of times the rat returned back from obstacle or visited the point in path list. If this number > 4 I will command to my rat return back to the original point (point 7). And start the journey again.

If the rat need to return back, for example 10 times, the algorithm terminates.

Again, your algorithm is funny, and it should be interesting to see how the rat moves but it does not solve the problem. It will not work on big mazes.

Try to implement path finding. If you will have problems -- ask questions.

Good luck!