Find the shortest path from the maze(Breadth-first search)

Question

Good evening. I have a labyrinth that is represented in the form of a matrix. There is a start point and an endpoint. I wrote a function that adds to the array all the cells that can be accessed. The function also deletes all cells that do not have descendants (deadlock). But the function does not delete cells that lead to a dead end. Please help to finish the function.

//maze
matrix = [
  [0, 1, 0, 1, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 0, 1, 0]
];

var start = [4, 0];
var end = [3, 4];

function findWay(position, end) {

  var queue = [];

 //an array that contains the cells that have already visited
  var visited = []; 

 //An array that contains cells that can not be entered for this position
  var invalidCells = [];

 //mark the current cell with a unit so as not to visit it anymore.    
  matrix[position[0]][position[1]] = 1;

 //add the current position to the queue
  queue.push(position);

 //until the queue is empty    
  while (queue.length > 0) {

 //get the first element of the queue    
    var pos = queue.shift(); 


   //we clear the array, because for each new position we will have our own array    
    invalidCells.length = 0; 


   //an array of motion directions
    var direction = [
      [pos[0] + 1, pos[1]],
      [pos[0], pos[1] + 1],
      [pos[0] - 1, pos[1]],
      [pos[0], pos[1] - 1]
    ];                      

    for (var i = 0; i < direction.length; i++) {

//do a check for each direction
//if at least one cell does at least one of the conditions, the cell is 
  placed in an array of invalid cells 
//then run a new iteration of the loop

      if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length || direction[i][1] < 0 || direction[i][1] >= matrix[0].length || matrix[direction[i][0]][direction[i][1]] != 0) { 

        invalidCells.push(direction[i]);
        continue;
      }

     //If this direction turned out to be an end cell
     //return the array of visited cells
      if (direction[i][0] == end[0] && direction[i][1] == end[1]) return visited;

     //if none of the conditions are met, mark this direction with one and add it to the end of the queue
      matrix[direction[i][0]][direction[i][1]] = 1;
      queue.push(direction[i]);
    }

    //add the current position to the array of visited cells
    visited.push(pos);

    //If no iteration of the loop returns anything, then this cell is a dead end
     if (invalidCells.length == 4) {

     //remove the deadlock from the array
      visited.pop();
    }
  }
}

findWay(start, end);

Answer 1

It seems unnecessary to keep track of visited and invalidCells:

• visited contains all the visited cells (in all directions). Although you try to remove cells from it once you reach a dead end, there is no easy way to backtrack and remove from it other cells, which lead to this dead end, and which are not involved in other paths that could still be successful.

• invalidCells is only used to detect dead ends, but because of the previous point, I would drop its use.

I assume your goal is to arrive at a visited array that represents the shortest path to the end cell, with all possible variant detours removed from it. The way you can achieve that with BFS is to use your queue not only to store positions, but the shortest paths that led to those positions. Then when you hit the end cell, you can return that single path, ignoring all the other paths that might still be in the queue.

Note that there is a problem with your example: the end cell is marked as 1, and your code will not detect such a cell as end cell, but will walk around it, and never find it. Either make sure an end cell is always marked 0, or perform the end-cell-test before doing any other check.

Here are the changes to make to your code -- see where the comments are.

var matrix = [
  [0, 1, 0, 1, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 0, 1, 0]
];

var start = [4, 0];
var end = [3, 4];

function findWay(position, end) {
  var queue = [];

  matrix[position[0]][position[1]] = 1;
  queue.push([position]); // store a path, not just a position

  while (queue.length > 0) {
    var path = queue.shift(); // get the path out of the queue
    var pos = path[path.length-1]; // ... and then the last position from it
    var direction = [
      [pos[0] + 1, pos[1]],
      [pos[0], pos[1] + 1],
      [pos[0] - 1, pos[1]],
      [pos[0], pos[1] - 1]
    ];

    for (var i = 0; i < direction.length; i++) {
      // Perform this check first:
      if (direction[i][0] == end[0] && direction[i][1] == end[1]) {
        // return the path that led to the find
        return path.concat([end]); 
      }
      
      if (direction[i][0] < 0 || direction[i][0] >= matrix.length 
          || direction[i][1] < 0 || direction[i][1] >= matrix[0].length 
          || matrix[direction[i][0]][direction[i][1]] != 0) { 
        continue;
      }

      matrix[direction[i][0]][direction[i][1]] = 1;
      // extend and push the path on the queue
      queue.push(path.concat([direction[i]])); 
    }
  }
}

var path = findWay(start, end);
console.log(JSON.stringify(path));