javascript - 我找不到迷宫的最短路径(广度优先搜索)

Question

我有一个以矩阵形式表示的迷宫。有一个起点和一个终点。我只能在包含零的单元格中移动。我编写了一个函数来查找所有可用路径。但该函数没有找到最短路径。请帮忙完成该功能。

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

更改背后的想法是，您记住所采取的每一个步骤的路径。当您向队列添加新点时，请添加该点的路径。

通过此路径，您可以在执行下一步时检查您是否已经访问过某个点。那么你就不必操纵矩阵/迷宫来记住访问过的点。

如果找到新点，请将新点和路径添加到队列中。如果该点包含在您的路径中，您就会遇到死胡同，并且不会将其添加到队列中。

如果您迈出一步并到达终点，请将带有终点的相应路径添加到“有效路径”列表中。如果您只对最短路径感兴趣，则第一个有效路径应该是最短路径(之一)。

如果您想要全部，请在队列为空时中断，因为最终您将访问每条路径中的每个点。

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