I can not find the shortest path from the maze(Breadth-first search)

Question

I have a labyrinth that is represented in the form of a matrix. There is a start point and an end point. I can only move around cells that contain zero. I wrote a function that finds all the available paths. But the function does not find the shortest path. Please help to finish the function.

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 = [1,1];


function findWay(position, end)
{

	var queue = [];

	var visited = [];

	matrix[position[0]][position[1]] = 1;
        visited.push(position);
   	queue.push(position);

    while(queue.length > 0){

    	var pos = queue.shift();

		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++){

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

		    if (direction[i][0] == end[0] && direction[i][1] == end[1]) return visited;
		    if (matrix[direction[i][0]][direction[i][1]] != 0) continue;

		    matrix[direction[i][0]][direction[i][1]] = 1;
		    visited.push(direction[i]);
		    queue.push(direction[i]);

    	}

    }

    return visited;

}

findWay(start, end);

Answer 1

The idea behind the changes is, that you remember the path for every step you take. When you add a new point to the queue, add the path with it.

With this path you can check if you visited a point already, when you take the next step. Then you don't have to manipulate the matrix/maze to remember visited points.

If you find a new point, add the new point and path to the queue. If the point is contained in your path, you hit a dead end and don't add it to the queue.

If you take a step and hit the end, add the corresponding path with the end point to your 'valid paths' list. If you are only interested in the shortest path, the first valid path should be (one of) the shortest ones.

If you want all, break if your queue is empty, as eventually u will have visited every point in every path.

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

   // New points, where we did not check the surroundings:
   // remember the position and how we got there
   // initially our starting point and a path containing only this point
   queue.push({pos: position, path: [position]});

    // as long as we have unchecked points
    while(queue.length > 0){

      // get next position to check viable directions
      var obj = queue.shift();
      var pos = obj.pos;
      var path = obj.path;

      // all points in each direction
      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++){

          // check if out of bounds or in a "wall"
          if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length) continue;
          if (direction[i][1] < 0 || direction[i][1] >= matrix[0].length) continue;
          if (matrix[direction[i][0]][direction[i][1]] != 0) continue;

          // check if we were at this point with this path already:
          var visited = false;
          for (var j = 0; j < path.length; j ++) {
               if ((path[j][0] == direction[i][0] && path[j][1] == direction[i][1])) {
                   visited = true;
                   break;
              }
          }
          if (visited) continue;

          // copy path
          var newpath = path.slice(0);
          // add new point
          newpath.push(direction[i]);

          // check if we are at end
          if (direction[i][0] != end[0] || direction[i][1] != end[1]) {
             // remember position and the path to it
             queue.push({pos: direction[i], path: newpath});
          } else {
            // remember this path from start to end
            validpaths.push(newpath);
            // break here if you want only one shortest path
          }

      }
    }
    return validpaths;
}

var paths = findWay(start, end);