Maze solving algorithm Java (Recursive)

Question

I've got completely stuck on a homework assignment that is due by the end of the week.

For some stupid reason my recursive traverser is not stopping when it hits the end of my maze ('E'), but keeps on going.

Here is the reader:

public class mainProg {


    public static void main(String[] args) {
        // The name of the file to open.

        Scanner reader = new Scanner(System.in);  // Reading from System.in
        System.out.println("Enter the name of textfile to be read ( add .txt): ");
        String fileName = reader.next();
        char temp;
        // This will reference one line at a time
        String line = null;
        int count = 1;
        int heightCounter = 0;
        try {
            // FileReader reads text files in the default encoding.
            FileReader fileReader = 
                new FileReader(fileName);

            // Always wrap FileReader in BufferedReader.
            BufferedReader bufferedReader = 
                new BufferedReader(fileReader);
            int height = 0, width = 0, startx = 0, starty = 0, endx = 0, endy= 0;
            char [][] maze = null;
            while((line = bufferedReader.readLine()) != null) {
                System.out.println(line);
                switch (count) {
                case (1):
                    height = Integer.parseInt(line.substring(0, line.indexOf(' ')));
                    width = Integer.parseInt((line.substring(line.indexOf(' ')+1)));
                    maze = new char [height][width];
                    break;
                case (2):
                    temp = line.charAt(0);
                    starty = Character.getNumericValue(temp);
                    temp = line.charAt(2);
                    startx = Character.getNumericValue(temp);
                    break;
                case (3):
                    endy = Integer.parseInt(line.substring(0, line.indexOf(' ')));
                    endx = Integer.parseInt((line.substring(line.indexOf(' ')+1)));
                    break;
                default:
                    int counter = 0;
                    for (int iterator = 0; iterator < line.length(); iterator++){
                        if(line.charAt(iterator) != ' '){
                            maze[heightCounter][counter] = line.charAt(iterator);
                            counter++;
                        }
                    }
                    heightCounter++;
                    break;
                }

                count++;
            }  
            maze[starty][startx] = 'S';
            maze[endy][endx] = 'E';
            mazeCreator ma = new mazeCreator(maze);
            ma.start(starty, startx);
            System.out.println(ma.result);
            // Always close files.
            bufferedReader.close();    
            System.out.println("Height: " + height + " Width: " + width);
            System.out.println("Starty: " + starty + " Startx: " + startx);
            System.out.println("Endy: " + endy + " Endx: " + endx);
            System.out.println(ma.result);
        }
        catch(FileNotFoundException ex) {
            System.out.println(
                "Unable to open file '" + 
                fileName + "'");                
        }
        catch(IOException ex) {
            System.out.println(
                "Error reading file '" 
                + fileName + "'");                  
            // Or we could just do this: 
            // ex.printStackTrace();
        }
    }

}

And here is my maze class:

package com.todai.first.project.testMaze;

public class mazeCreator {

        char [][] maze;
        char PATH = 'x';
        char VISITED = 'y';
        String result = "";
        int starty, startx;

        public mazeCreator (char[][] maze){
            this.maze = maze;
        }

        public void start (int starty, int startx) {
            this.starty = starty;
            this.startx = startx;
            traverse(starty, startx);
        }
        private boolean isValid (int row, int col){
            boolean valid = false;

             if (row >= 0 && row < maze.length &&
                      col >= 0 && col < maze[row].length){
                 if (maze[row][col] == '0' || maze[row][col] == 'E' || maze[row][col] == PATH) {
                     valid = true;
                 }
             }
             return valid;
        }
        private boolean traverse (int row, int col) {
            System.out.println("I'm here: \t" + row +","+ col + "\t :: " + maze[row][col]);
            if (maze[row][col] == 'E'){
                System.out.println("I WON!");
                result = mazeToString();
                return true;
            }
            else{
            if (maze[row][col] == PATH){
                maze[row][col] = VISITED;
            } else {
                maze[row][col] = PATH;
            }

            if (isValid(row+1, col)){
                traverse(row+1, col);
            }

            if (isValid(row-1, col)){
                traverse(row-1, col);
            }

            if (isValid(row, col+1)){
                traverse(row, col+1);

            }
            if (isValid(row-1, col-1)){
                traverse(row, col-1);
            }
            return false;
            }
        }

        private String mazeToString(){

                  StringBuilder sb = new StringBuilder();
                  for (int i=0; i< this.maze.length; i++) {
                    for (int j=0; j < this.maze[i].length; j++) {
                        if (maze[i][j] == '1') {
                            maze[i][j] = '#';
                        }
                      sb.append(maze[i][j]);
                    }
                    sb.append("\n");
                  }
                  maze[starty][startx] = 'S';
                  return sb.toString();

        }
}

Here is the output I get from the console (eclipse):

Enter the name of textfile to be read ( add .txt): 
small.txt
6 5
1 1
4 3
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 1
1 1 1 1 1
I'm here:   1,1  :: S
I'm here:   2,1  :: 0
I'm here:   3,1  :: 0
I'm here:   4,1  :: 0
I'm here:   3,1  :: x
I'm here:   4,1  :: x
I'm here:   2,1  :: x
I'm here:   1,1  :: x
I'm here:   1,2  :: 0
I'm here:   1,3  :: 0
I'm here:   2,3  :: 0
I'm here:   3,3  :: 0
I'm here:   4,3  :: E
I WON!
I'm here:   2,3  :: x
I'm here:   3,3  :: x
I'm here:   4,3  :: E
I WON!
I'm here:   1,3  :: x
I'm here:   2,2  :: #
I'm here:   1,2  :: x
I'm here:   2,2  :: x
#####
#Sxx#
#y#y#
#y#y#
#y#E#
#####

Height: 6 Width: 5
Starty: 1 Startx: 1
Endy: 4 Endx: 3
#####
#Sxx#
#y#y#
#y#y#
#y#E#
#####

As you guys can clearly see it keeps on recursively calling iteself after having found 'E'.

Any clues?

Andreas · Accepted Answer · 2016-01-27 17:12:55Z

5

After you print I WON!, you return true, but non of the recursive calls check the return value, so of course they don't stop. Change the calls to check return value:

if (isValid(row+1, col)) {
    if (traverse(row+1, col))
        return true;
}

answered Jan 27, 2016 at 17:12

Andreas

160k13 gold badges164 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Todai Over a year ago

Tried that by having a boolean variable initialized to false at start of the method and setting the value to true at 'E' and by having that boolean checked in an if-clause surrounding the recursive calls. I'm on my phone, but pseudo would be something like: Bool false, if ('E') then Bool true else run recursive and return Bool variable at end of method.

Collectives™ on Stack Overflow

Maze solving algorithm Java (Recursive)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related