javascript - 寻路 javascript 算法无法正常工作

Question

我正在编写寻路算法，但我被困在一件事上。算法获取起始单元格并将其添加到队列中，将其标记为已访问并在屏幕上的单元格中打印数字(数字显示当前单元格与起始单元格的距离)。然后对于队列的第一个元素，它检查它的邻居。如果邻居不是墙或尚未访问过，则将他添加到队列中。然后从队列中删除第一个元素并重复整个函数，直到队列长度等于 0。

我无法让一件事正常工作，当用单元格填充队列并为单元格提供距离编号时，结果应该是这样的:

S12
1#2
22E

其中 # 是墙，S 是起点，E 是终点。但是，当算法运行时，它会产生以下结果:

S12
2#3
33E

似乎有些单元格的距离数增加了不止一次，这是不应该发生的。在代码中，我添加了额外的 bool 标志，无论单元格距离数是否已经增加，以及仅当它到目前为止还没有增加时才增加距离数的附加条件。帮助指出我出错的地方将不胜感激。寻路功能:

function findPath(startCell, goalCell) {
  var queue = [];

  queue.push({
    cell: startCell,
    hasBeenIncremented: true,
    hasBeenSearched: false,
    searchDistance: undefined
  });
  queue[0].searchDistance = 0;

  fillPath();

  function fillPath() {
    queue[0].cell.hasBeenSearched = true;
    pointColor(queue[0].cell.x, queue[0].cell.y, 'darkred');
    setInnerHTML(queue[0].cell.x, queue[0].cell.y, queue[0].searchDistance);

    for (var i = -1; i <= 1; i++) {
      if (queue[0].cell.x + i < 0 || queue[0].cell.x + i > boardHeight - 1) {
        continue;
      }
      for (var j = -1; j <= 1; j++) {
        if (queue[0].cell.y + j < 0 || queue[0].cell.y + j > boardWidth - 1) {
          continue;
        }
        if (i == 0 && j == 0) {
          continue;
        }
        if (getCell(queue[0].cell.x + i, queue[0].cell.y + j).hasWall == true || getCell(queue[0].cell.x + i, queue[0].cell.y + j).hasBeenSearched == true) {
          continue;
        }
        if (queue[0].cell.x == goalCell.x && queue[0].cell.y == goalCell.y) {
          pointColor(goalCell.x, goalCell.y, 'darkred');
          setInnerHTML(goalCell.x, goalCell.y, '*');
          return 'path completed';
        }

        queue.push({
          cell: getCell(queue[0].cell.x + i, queue[0].cell.y + j),
          hasBeenSearched: false,
          searchDistance: undefined,
          hasBeenIncremented: false
        });
        if(queue[queue.length - 1].hasBeenIncremented != true) {
          queue[queue.length - 1].searchDistance = queue[0].searchDistance + 1;
          queue[queue.length - 1].hasBeenIncremented = true;
        }

      }
    }
    queue.shift();
    if (queue.length > 0) {
      setTimeout(fillPath, 1000);
    }
  }

}

JS fiddle 链接:https://jsfiddle.net/s8texvxa/2/ (这不是一个完整的算法 - 只是它的第一部分)。

Answer 1

您在排队之前执行检查，但它可能通过其他路径在队列中但尚未检查，因此仍被视为未访问。

请注意，如果可以通过多条路径到达单元格，则必须确保使用最短的距离。

看起来您正在使用广度优先算法，因此在排队时将单元格标记为已访问就足够了，这样它就不会被再次添加。