CODEWITHSUNDEEP
javarecursion
SChun
SChun

Reputation: 17

Finding a solution path to maze recursively

I have to write a recursive method that finds a path from position (row,col) to the goal position, marked by 'G', and returns a String composed of the characters 'U', 'R', 'D', 'L', and the final 'G', indicating the solution path.

My code works for mazes that start on corners and edges but fails for mazes such as this one

##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S    #
##########

When i test my code with a maze such as the one above i get output like this. The path will always go right until it hits the wall then stop.

Solution Path: RRRR
##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S... #
##########

I don't understand how to make so that the method knows that going right isn't the correct solution path. I read here that the recursive methods can backtrack to previous calls to know that a certain direction is wrong, but i don't understand how to make my method do that.

 public String findPathFrom(int row, int col){

    if(row > mapHeight || col > mapWidth){
        return "";
    }
    if(map[row][col] == '#' || map[row][col] == '.'){
        return "";
    }
    if(map[row][col] == 'G'){
        solved = true;
        return "G";
    }
    if(map[row][col] != 'S'){
        map[row][col] = '.';
    }
    if(map[row-1][col] == ' ' || map[row-1][col] == 'G'){
        return "U" + findPathFrom(row-1, col);
    }
    if(map[row][col+1] == ' ' || map[row][col+1] == 'G'){
        return "R" + findPathFrom(row, col+1) ;
    }
    if(map[row+1][col] == ' ' || map[row+1][col] == 'G'){
        return "D" + findPathFrom(row+1, col);
    }
    if(map[row][col-1] == ' ' || map[row][col-1] == 'G'){
        return "L" + findPathFrom(row, col-1);
    }
    else{
        map[row][col] = ' ';
        return "";
    }
}

I'm still really new to java, so sorry if I'm using terms incorrectly.

Upvotes: 1

Views: 3357

Answers (2)

Barney
Barney

Reputation: 2836

Your findPathFrom function needs to indicate to its caller whether it succeeded or not, and only return early if successful. I'd typically make this a boolean function and store the path somewhere else, but to keep close to your code you could return a string of the path for success, and a blank string for failure.

public String findPathFrom(int row, int col){

  // goal / out of bounds checks - same as existing code
  // ... "G" for success / "" for failure
  if(row > mapHeight || col > mapWidth){
    return "";
  }
  if(map[row][col] == '#' || map[row][col] == '.'){
    return "";
  }
  if(map[row][col] == 'G') {
    return "G";
  }

  // no special treatment for starting point - do that in the calling code
  map[row][col] = '.';

  // recursive path search
  String pu = findPathFrom(row-1, col);
  if (!pu.isEmpty()) {
    return "U" + pu;
  }
  String pr = findPathFrom(row, col+1);
  if (!pr.isEmpty()) {
    return "R" + pr;
  }
  String pd = findPathFrom(row+1, col);
  if (!pd.isEmpty()) {
    return "D" + pd;
  }
  String pl = findPathFrom(row, col-1);
  if (!pl.isEmpty()) {
    return "L" + pl;
  }

  // reset the current cell
  map[row][col] = ' ';
  return "";
}

The key point is that you only return early from the recursive calls if one of them finds a solution. In your code, you always return directly from a call to findPathFrom regardless of whether it succeeded or not, so as soon as one fails the next will never be tried.

See Java Recursive Maze Solver problems for a similar problem with a bit more discussion on the algorithm.

Upvotes: 1

janos
janos

Reputation: 124834

Your algorithm is missing the logic to explore different paths. It always goes in the first available direction it sees (up/right/down/left). That is, when up and right are available, it will go up, not to right. If later it turns out that up doesn't reach a solution, it just stops. Here's a simpler grid to demonstrate the problem:

###
# #
#S#
#G#
###

Your algorithm will go up and then gets stuck, there's nowhere else to go from up. Things would have been different had it started from going down. But it's impossible to know which direction is best in the long run. (The problem is not the order in which you check the available spaces.)

To solve this problem, look into breadth first search. The idea is to track all available directions at the same time in parallel, and when any of the path reaches the solution, the problem is solved.

Upvotes: 2

Related Questions