寻路 javascript 算法无法正常工作

Question

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

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

S12
1#2
22E

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

S12
2#3
33E

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

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 link: https://jsfiddle.net/s8texvxa/2/（这不是一个完整的算法——只是它的第一部分）。

Answer 1

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

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

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

寻路 javascript 算法无法正常工作

Pathfinding javascript algorithm not working as it's supposed to

javascript

algorithm

path-finding