CODEWITHSUNDEEP
javabacktrackingmaze
vkatsou
vkatsou

Reputation: 83

Maze backtracking horizontal move

In a rat in maze exercise i have a problem when the rat is moving horizontally. I've define the rat to go first down, if available, then right and then left. The problem is that when it goes to a path with a dead end and tries to find the wright path the rat confuses the right with the left. The path is stored in an array. The exit is anywhere in the bottom. The rat can move in any direction. (0,3) is the start.

0 = free to pass

1 = blocked

See the follow example:

1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 0 0 0 1 0 1
1 0 1 0 1 0 0
1 1 1 0 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
0 0 1 1 1 0 1
0 1 1 1 0 1 1

Path: (0,3) (1,3) (2,3) (3,3) (4,3) (5,3) (5,4) (5,5) (6,5) (7,5) (6,5) (5,5) (5,4) (5,5) (6,5) (7,5) (6,5) (5,5) (5,4) (5,5)...

In this example the rat at (5,4) doesn't choose to go to the left and it loops the previous path. I am really trying to find a solution to this. Anyone know?

Here's is some of my code:

public boolean solveRatMaze(int maze[][], int x, int y, int sol[][], Stack stack) {
        if ((x == maze.length-1 && isValidPlace(maze, x, y)) { //when (x,y) is the bottom right room
            sol[x][y] = 0;
            stack.push(String.valueOf(x));
            stack.push(String.valueOf(y));
            return true;
        }
        if(isValidPlace(maze, x, y) == true) {     //check whether (x,y) is valid or not
            sol[x][y] = 0; //set 0, when it is valid place
            if (solveRatMaze(maze,x+1, y, sol, stack) == true)       //when x direction is blocked, go for bottom direction
                return true;    //when x direction is blocked, go for bottom direction
            if (solveRatMaze(maze, x, y + 1, sol, stack) == true)         //find path by moving right direction
                return true;     //when x direction is blocked, go for bottom direction
            if (solveRatMaze(maze, x, y - 1, sol, stack) == true)         //find path by moving left direction
                return true;

            sol[x][y] = 0;         //if both are closed, there is no path
            return false;
        }
        return false;
    }

isValidPlace simply checks if the place is in the boundaries of the array and has the value 0 (not blocking)

sol[][] is an array to represent the final path. All values are 1 except the path values that are 0

maze[][] is the given array

Upvotes: 0

Views: 165

Answers (1)

Cippe420
Cippe420

Reputation: 11

You could implement a simple stack "visitedpaths" that stores every coordinate you already visited and you tell the rat not to go on those paths.

To do that, you need to initialize a stack and the top of the stack:

public int[] visitedpaths;    
private int top = -1 ; // that allows you to free up space to store values

and then implement a simple push(int v):

public void push( int v){ 
    top = top+1;
    top = v;
}

So every time your mouse walks it stores the tile in the stack.

then you have to make sure it does not walk in visited tiles by modifying the second "if"

Upvotes: 1

Related Questions