My Maze code algorithm not solve - javascript

Question

I am new developer

I have problem in this code, and don't know what the problem

My maze code working but is not solve the maze

can someone help me to understand what is the issue or there is a different ways to solve it ?

    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]
        ];
        
        
        
        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 maze= new maze(myMaze)
        maze.find(0,3)

What is not working? What are you expecting to happen? What is the output of this code ? — sagi, Sep 02 '18 at 13:42
Look at the output: the algorithm keeps checking the same cells; you need to keep track of which cells you've already visited. — m69's been on strike for years, Sep 02 '18 at 14:35
Why would you not go till 0 and myMaze.length-1? you need to have row >= 0 and col >= 0 and col <= myMaze.length - 1, row <= myMaze.length - 1. And ofcourse don't visit cells that you already visted. — SomeDude, Sep 02 '18 at 14:40
@SomeDude `if(row > 0) this.find(col,row-1)` is visiting row 0. — m69's been on strike for years, Sep 02 '18 at 14:45
check out [Backtracking in A star](https://stackoverflow.com/a/28317199/2521214) and [How to speed up A* algorithm at large spatial scales?](https://stackoverflow.com/a/23779490/2521214) — Spektre, Sep 03 '18 at 07:08

trincot · Accepted Answer · 2018-09-03T12:30:35.897

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));

score 0 · Answer 2 · answered Sep 02 '18 at 16:03

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();

My Maze code algorithm not solve - javascript

2 Answers2