Maze search algorithm runs into a call stack size exceeded error

Question

I am trying to implement a path searching algorithm. The input is a maze, encoded as a matrix, where the value 1 represents a cell that can be traversed, and the value 2 represents the goal. The coordinates of the starting point are given.

But there is an issue with my code: it runs into a Maximum call stack size exceeded error. What is the issue?

function maze(myMaze) {
    this.find = function(col, row) {
        console.log(row, col, myMaze[row][col])
        if (myMaze[row][col] == 2){
            console.log('done')
        }
        if (myMaze[row][col] == 1) {
            console.log('we on the right way')
            if (row < myMaze.length - 1) {
                this.find(col, row + 1)
            }
            if (col < myMaze[row].length - 1) {
                this.find(col + 1, row)
            }
            if (row > 0) {
                this.find(col, row - 1)
            }
            if (col > 0) {
                this.find(col - 1, row)
            }
        }
    }
}

var myMaze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
var maze = new maze(myMaze)
maze.find(0, 3)

Answer 1

The main issue is that your algorithm runs in circles: from cell B it will visit a cell A that it has visited before and from there it will recurse deeper to get again to cell B, and this continues for ever. Eventually the call stack will run out of memory.

This can be solved by keeping track of the cells that were already visited, so they are not visited again. Although this can be done with an array, it is more efficient to use a Set for that.

Secondly, you use the same name for the maze constructor and the maze instance. This will make it impossible to solve two mazes in a row. Instead, use the common practice to name the constructor function with an initial capital letter: Maze.

Also, if you just output the fact that the algorithm found the target cell, you do not have any information about the path that was found. It is better to return the path and let the caller deal with it as they wish.

Finally, there is no reason why the find method should be created on the instance: it is better practice to define it on the prototype so that it only needs to be created once even if you create several maze instances.

I would also suggest to abandon the old-style constructor function and use the ES6 class syntax, which has been around now for several years.

Here is how you could code it:

class Maze {
    constructor(maze) {
        this.maze = maze;
        this.width = maze[0].length;
        this.height = maze.length;
    }
    // Added optional argument to indicate cells that should not be visited
    find(col, row, visited = new Set) { 
        // Create a unique reference for the current cell
        const cellId = row * this.width + col; 
        // Check that this cell lies within the grid, has a non-zero value, 
        //    and has not been visited before
        if (!this.maze[row] || !this.maze[row][col] || visited.has(cellId)) {
            return; // No success
        }
        visited.add(cellId); // Mark this cell as visited, so it is not visited a second time.
        //console.log("visiting: ", col, row); // Uncomment to see progress
        if (this.maze[row][col] == 2) { // Bingo!
            return [[col, row]]; // Return the path that will be extended during backtracking
        }
        // Loop through the 4 directions
        for (const [addcol, addrow] of [[0, 1],[1, 0],[0, -1],[-1, 0]]) {
            const found = this.find(col+addcol, row+addrow, visited);
            // If found, prepend current cell to partial solution and get out of recursion
            if (found) return [[col, row], ...found]; 
        }
    }
}

const myMaze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];


const maze = new Maze(myMaze);
const path = maze.find(0,3);
console.log(JSON.stringify(path));

Answer 2

I keep an array to keep track of the indiexes that have already been visited. Can be edited to view the path to be watched

 var myMaze = [
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
          [1, 1, 1, 0, 1, 0, 0, 1, 1, 1],
          [0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
          [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
          [0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
          [0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        ];

 var c_path=new Array();
 var path=new Array();
 var last ;
 function maze(myMaze){

       this.find = function(col,row){
       if(myMaze[row][col] == 1 ){
            path.push(new Array(row,col));
            console.log(row,col,myMaze[row][col])
       }
       if(myMaze[row][col] == 2){
            last =new Array(row,col);
            console.log('done')
       }
       if(myMaze[row][col] == 1 ){
            if(c_path.includes(row+"-"+col)){
                    return;
            }
            c_path.push(row+"-"+col);
            if(row < myMaze.length - 1){
                    this.find(col,row+1)
             }
             if(col< myMaze[row].length -1){
                this.find(col+1,row)
             }
             if(row > 0){
                this.find(col,row-1)
             }
             if(col > 0){
                this.find(col-1,row)
             }
        }
    }
    this.show =function(){

        for (var i = path.length-1 ;i>0 ;i--){
            var tmp =path[i];
            if((tmp[0] ==last[0] && Math.abs(tmp[1] - last[1]) ==1) ||  (tmp[1] ==last[1] && Math.abs(tmp[0] - last[0]) ==1)){

                last =tmp;
                myMaze[tmp[0]][tmp[1]] =3;
            }
        }
        console.log(myMaze);
    }
}

var maze= new maze(myMaze)
maze.find(0,3)
maze.show();