路径查找javascript算法无法正常工作'他应该这样做

Pathfinding javascript algorithm not working as it's supposed to

本文关键字:这样做 工作 算法 javascript 查找 常工作 路径      更新时间:2023-09-26

我正在编写寻路算法,但有一件事我被卡住了。算法获取起始单元格并将其添加到队列中,将其标记为已访问,并在屏幕上打印单元格中的数字(数字显示当前单元格与起始单元格的距离)。然后,对于队列的第一个元素,它检查它的邻居。若邻居不是墙或还并没有被拜访,他会被添加到队列中。然后从队列中移除第一个元素,并重复整个函数,直到队列长度等于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链接:https://jsfiddle.net/s8texvxa/2/(这不是一个完整的算法,只是它的第一部分)。

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

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

看起来你使用的是广度优先算法,所以在排队时将单元格标记为已访问就足够了,这样它就不会再次被添加。

相关文章: