How I may break from this recursivity in JavaScript for a maze path finder?-CodePudding

I have been practicing some exercises, and among them I am now trying to create a code for finding a path inside a maze matrix created in js. Now, this code works, it finds the correct path, and I even p[rint it to be sure its the correct one, but I am having one issue. I am not sure what to do in case my path cannot arrive to the destination. For example, these are 2 of my samples, the correct path is marked with 1 and the "walls" with a 0:

[
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ]

But, if I cut one path, preventing my fidner to arrive to the destination, I am unable to find a way to break the recursivity.

[
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 0, 0, 2],
            [0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ]

In short, I can return the correct path, but I am not sure , in case It cannot find a way to the "exit", to return "Invalid path", or "There is no path to the destination"

Bellow is the complete code:

class mazeSolver {
    constructor() {


        this.myMaze = [
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ];


        this.traverse = function (column, row) {
            if (this.myMaze[column][row] === 2) {
                console.log("You found the exit at: "   column   "-"   row);
                console.log("Path: ")
                for (let i = 0; i < this.myMaze.length; i  ) {
                    console.log(this.myMaze[i])
                }
            }
            else if (this.myMaze[column][row] === 1) {
                this.myMaze[column][row] = 8;
                console.log("You passed by "   row   "-"   column);
                if (column < this.myMaze.length - 1) {
                    this.traverse(column   1, row);
                }
                if (row < this.myMaze[column].length - 1) {
                    this.traverse(column, row   1);
                }

                if (column > 0) {
                    this.traverse(column - 1, row);

                }
                if (row > 0) {
                    this.traverse(column, row - 1);
                }

            }
        };

    }
}

I appreciate any input. Thanks!

CodePudding user response：

Some comments on your code:

Use console.log inside the traverse method for debugging only, not for something important as reporting the path that was found. That should actually be left to the caller to do.
If the recursive call finds the target, no other recursive call should be made. Instead that success should immediately be returned to the caller, who should do the same...
The path could be collected during backtracking. This path could be the return value in case of success (and undefined otherwise).
Do not initialise a hardcoded matrix in the constructor. Instead pass the matrix as argument to the constructor.
Make traverse a prototype method, instead of defining it on the instance.
In a matrix, we usually consider the first dimension as rows, and the second dimension as columns. You did it the other way round.
It is easier to protect your traversal against out-of-range access by the use of the ?. operator.

Here is the updated code:

class MazeSolver {
    constructor(matrix) {
        this.myMaze = matrix;
    }
    traverse(column, row) {
        if (this.myMaze[row]?.[column] === 2) {
            return [[column, row]]; // Return path. Caller can extend it
        } else if (this.myMaze[row]?.[column] === 1) {
            this.myMaze[row][column] = 8;
            console.log("You passed by "   column   ","   row);
            const path = this.traverse(column   1, row)
                      ?? this.traverse(column, row   1)
                      ?? this.traverse(column - 1, row)
                      ?? this.traverse(column, row - 1);
            if (path) path.unshift([column, row]); // Extend the path found
            return path;
        }
    }
} 

// Maze without solution:
const solver = new MazeSolver([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
    [0, 1, 1, 1, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]);

const path = solver.traverse(0, 3);
if (path) {
    console.log("found a path (column, row):")
    console.log(JSON.stringify(path));
} else {
    console.log("No path found");
}

CodePudding user response：

your solution doesn't work for some cases, take this example

        this.myMaze = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
        [0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    ];

result:

    You passed by 3-0
You passed by 3-1
You passed by 4-1
You passed by 5-1
You passed by 5-2
You passed by 5-3
You passed by 6-3
You passed by 7-3
You passed by 8-3
You passed by 9-3
     maze.js:39
            if (this.myMaze[row][column] === 2) {
                                ^

TypeError: Cannot read property '3' of undefined
    at mazeSolver.traverse (maze.js:39:33)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:53:26)
    at mazeSolver.traverse (maze.js:53:26)
    at mazeSolver.traverse (maze.js:50:26)
    at mazeSolver.traverse (maze.js:50:26)

first thing I can tell about your algorithm is it's an eager algorithm, meaning that you chose the first available path.

Second thing about recursion is you must have an exit condition that will be true at some point, you don't have it your case, you are not even exiting the function at any point.

third you are switching between column and row, column is the vertical array, row is the horizontal array.

here is a code that is an eager solution, that will at least avoid the error above

class mazeSolver {
    constructor() {
        this.solution_found=false;
        this.myMaze = [
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 1, 1, 2],
            [0, 1, 1, 1, 0, 1, 0, 1, 0, 0],
            [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        ];
    this.traverse = function (row, column) {
        if (this.myMaze[row][column] === 2) {
            this.solution_found=true;
            console.log("You found the exit at: "   row   "-"   column);
            console.log("Path: ")
            for (let i = 0; i < this.myMaze.length; i  ) {
                console.log(this.myMaze[i])
            }
        }
        else if (this.myMaze[row][column] === 1) {
            this.myMaze[row][column] = 8;
            console.log("You passed by "   row   "-"   column);
            if (column < this.myMaze.length - 1) {
                if(row  1> this.myMaze.length - 1)
                    return
                this.traverse(row   1, column);

            }
            if (row < this.myMaze[row].length - 1) {
                if(column 1 > this.myMaze.length - 1)
                    return
                this.traverse(row, column   1);

            }

            if (row > 0) {
                if(row-1 < 0){
                    return
                }
                this.traverse(row - 1, column);

            }
            if (column > 0) {
                if(column-1 < 0){
                    return
                }
                this.traverse(row, column - 1);
            }

        }
    };

    }
} 
maze = new mazeSolver();
maze.traverse(3, 0)
if(!maze.solution_found){
    console.log('solution not found')
}

to develop an algorithm that will find the path 100% if the path exists, try doing some research on search algorithms, mainly path finding, e.g., A* heuristic or Dijkstra's Algorithm.