Java Recursion method

[Rivosk Hogerop]

Hi,

I have a question about a small pathfinding problem.
I got a 2D table which symbolize a labyrinth.
The table only contains a ' '(white space), a 'B', a 'E' and a 'W'
B: begin position
E: end position
W: wall

I need to write out all the pads from B to E.
(a) I may not cross a wall
(b) I may not move to a position I have already been before. (in the same pad)

for example I have the following labyrinth: (ignore the [])
[M][ ][ ][ ][ ]
[B][ ][M][ ][E]
[M][ ][ ][ ][ ]

My java program needs to print out ALL the possible pads from B to E:
rurrrd
rurrdr
rurrddru
rdrrru
rdrrur
rdrruurd

I have written this little program.
It's an excercice from the exam from last year and I should be able to solve it with recursion.
But my program only print out 1 possible pad instead of ALL pads.
If someone can point me where and what I'm doing wrong I would be verry gratefull. (I'm practicing for my upcomming exam)
(excuse me for my bad english)

class Labyrinth{
  public static void main(String [] args){
    char [][] labyrinth = {{'W',' ',' ',' ',' '},{'B',' ','W',' ','E'},{'W',' ',' ',' ',' '}};
    pads(labyrinth);
  }
  
  
  static void pads(char [][] labyrinth){
    char [][] help = new char[labyrinth.length][labyrinth[0].length];
    int row = startingposition(labyrinth , true); 
    
    int column = startingposition(labyrinth, false); 
    
    String way= "";
    findpad(labyrinth, help, row , column, way);
  }
  
  static int startingposition(char[][] labyrinth,boolean row){
    int i,j;
    boolean found = false;
    int startingposition = 0;
    for(i=0; i <labyrinth.length && found == false; i++){
      for(j=0; j < labyrinth[i].length && found==false; j++){
        if(labyrinth[i][j]=='B'){
          found = true;
          if(row==true)
            return i;
          else
            return j;
        }
      }
    }
    return -1;
  }

  static void findpad(char [][] labyrinth, char [][] help, int row, int column, String way){
    int i,j;
    
    if(labyrinth[row][column]=='E'){
      System.out.println(way);
    }
  
    help[row][column]='X'; 
 
    
    if(labyrinth[row][column]!='E'){
      for(i=-1; i<=1; i++){
        for(j=-1; j<=1; j++){
          
          if(i!=j && (i==0 || j==0) && row+i>0 && column+j>0 && row+i<labyrinth.length && column+j<labyrinth[0].length && help[row+i][column+j]!='X' && labyrinth[row+i][column+j]!='W'){
            if(i>0)
              way+="u";
            else if(i<0){
              way+="d"; 
            }
            else if(j>0){
              way+="r"; 
            }
            else if(j<0){
              way+="l"; 
            }

            
            findpad(labyrinth,help,row+i,column+j,way);
            
          }
        }
      }
      
   
    }
    
    
  }
  
}

[dennis deems]

Are you sure that an Array is the best data structure to model your labyrinth? I might suggest exploring what you can do with a tree structure. I think a tree is better suited to your problem because the relationship of parent and child nodes is inherently suited to representing a path.

[Randall Twede]

i am not sure recursion is the best answer. i wrote an old homework that is similar to this. it only had to find one path though. i used an array and a stack of points. the code is here

[Rivosk Hogerop]

Hi thanks for your reactions.
It's not that i'm looking for the best way to solve this problem.
It's an exercise and we need to solve it with recursion. (on the exam I will have no other choice then recursion.)
(P.s.:we haven't seen any OOP)

[dennis deems]

I would create a node object which contains: the attribute of the room ('','B','E' or 'W'), a set of child nodes (the adjoining rooms), and a marker to tell whether or not it has been visited.

I would build out the tree from the labyrinth you have laid out in the arrays. We also need some indicator of how we are getting from room to room -- the path (u,d,l,r), and that will be the most difficult part of the problem.

But assuming you have that sorted, the pathfinding algorithm would be:

path = ""
for each child of [root]:
   if child attribute is 'E', return path
   else if child attribute is 'W', skip
   else if child was visited, skip
   if no child nodes left, return
   else store path
      path = path + move required to reach child
      recursive path search from child as new root

It is probably better, now I think of it, to wait until E is reached and then collect the path as we come out of the recursion, but you get the idea.

[Mori Gad]

The code itself, with very minor adjustments, does work. Not saying anything about recursion being the best option or arrays being worse.


Think about possible problems and ways of testing them.

You need to keep track of where you visited for the current path without blocking off the path for other solutions.

The large if statement could use some white space to make it more readable, for easier testing.

[Campbell Ritchie]

Welcome to the Ranch Curly Stoge.

[Stephan van Hulst]

Hi Rivosk. Problems like this become much easier when you first create some basic data structures to work with, which provide a few handy operations.

For instance, let's make a basic Labyrinth data type which provides methods to look at different directions, and to move into a new direction:

package com.example;

import java.util.*;
import static com.example.Labyrinth.Cell.*;
import static com.example.Labyrinth.Direction.*;

/**
 * Basic labyrinth data structure.
 * A labyrinth consists of cells, which are either walls, empty rooms or exits.
 * There is a current position in the labyrinth, that of the last room visited.
 */
public final class Labyrinth {

  public static enum Cell {
    EMPTY, WALL, EXIT, VISITED;
  }

  public static enum Direction {
    NORTH, EAST, SOUTH, WEST;
  }

  private final Cell[][] cells;
  private final int x, y;

  /**
   * Constructs a new Labyrinth from a map.
   * In the map, 'W' represents a wall, 'E' represents an exit, 'B' represents
   * a starting position, and any other character represents an empty room.
   */
  public Labyrinth(char[][] map) {
    int startX = -1;
    int startY = -1;

    int height = map.length;
    cells = new Cell[height][];

    for (int y = 0; y < height; y++) {
      int width = map[y].length;
      cells[y] = new Cell[width];

      for (int x = 0; x < width; x++) {
        switch (Character.toUpperCase(map[y][x])) {
          case 'B': startX = x; startY = y;
                    cells[y][x] = VISITED; break;
          case 'W': cells[y][x] = WALL;    break;
          case 'E': cells[y][x] = EXIT;    break;
          default : cells[y][x] = EMPTY;   break;
        }
      }
    }

    if (startX == -1 || startY == -1)
      throw new IllegalArgumentException("Labyrinth has no starting point");

    this.x = startX;
    this.y = startY;
  }

  /**
   * Constructs a new Labyrinth from an old one, and visits the room in the given direction.
   */
  private Labyrinth(Labyrinth labyrinth, Direction direction) {
    int[] coords = labyrinth.getCoords(direction);
    int x = coords[0];
    int y = coords[1];

    cells = Arrays.copyOf(labyrinth.cells, labyrinth.cells.length);
    cells[y] = Arrays.copyOf(cells[y], cells[y].length);
    cells[y][x] = VISITED;

    this.x = x;
    this.y = y;
  }

  /**
   * Returns the {x,y} coordinates of the cell in the given direction.
   * This method returns null if the cell does not exist.
   */
  private int[] getCoords(Direction direction) {
    int x = this.x;
    int y = this.y;

    switch (direction) {
      case NORTH: y--; break;
      case EAST : x++; break;
      case SOUTH: y++; break;
      case WEST : x--; break;
    }

    if (y < 0 || y >= cells.length || x < 0 || x >= cells[y].length)
      return null;

    return new int[] {x,y};
  }

  /**
   * Returns the type of cell in the given direction.
   * This method returns null if the cell does not exist.
   */
  public Cell look(Direction direction) {
    int[] coords = getCoords(direction);

    if (coords == null)
      return null;

    int x = coords[0];
    int y = coords[1];
    return cells[y][x];
  }

  /**
   * Visit the cell in the given direction. This method will return a new
   * Labyrinth with a different position. The cell at that position will be
   * visited.
   */
  public Labyrinth move(Direction direction) {
    Cell cell = look(direction);
    if (cell != EMPTY && cell != VISITED)
      throw new IllegalArgumentException("Can't move in the given direction");

    return new Labyrinth(this, direction);
  }

  public static void main(String... args) {
    char[][] map = new char[][] {
      {'W',' ',' ',' ',' '},
      {'B',' ','W',' ','E'},
      {'W',' ',' ',' ',' '}
    };

    Labyrinth labyrinth = new Labyrinth(map);
    // do stuff with labyrinth.
  }
}

You now have a simple Labyrinth that has look(Direction) and move(Direction) methods. This should be plenty to implement some recursive method that finds all the paths to an exit.

Note that the trick here is that the move() method returns a new Labyrinth. You can call this method without worrying that your old labyrinth will be modified. In fact, the entire Labyrinth class here is immutable. This makes it very easy to work with.

As already has been mentioned, a tree is a good structure to represent paths with. If you don't want to use a tree, you can also use something like:List<List<Direction>>.

[dennis deems]

Honestly, without a tree I don't know how you will be able to be sure that you have found every possible path. As Curly observed, your code works, but how can it be adapted to find more than one solution, let alone to exhaust all possibilities? With a tree you know definitively whether or not a branch has been explored.

[Stephan van Hulst]

The algorithm to find all the paths doesn't need to inspect a tree to figure out whether it exhausted all possibilities. Recursion takes care of this automatically.

You can write a simple recursive method getPathsToExit() that returns a list of paths, without ever using a tree.

[Randall Twede]

sure seems a lot harder than the homework i had
recursion is great, it is just hard for most of us mortals to figure out
glad you got some great help with it. i think i might have had a hard time with this one.

[Stephan van Hulst]

Some pseudo code:

paths-to-exit:
     list result = new list

     for each direction d:
        room r = room at d

        if r is not a wall and hasn't been visited yet:
           path p = new path
           add d to p
        
           if r is an exit:
              add p to result
        
           if r is not an exit:
              labyrinth m = visit d
          
              for each path e in paths-to-exit m:
                 concatenate p and e and add to result

     return result