骑士游历问题：如何在BFS实现中回溯返回最短路径数组

作业背景与要求 #

我正在学习The Odin Project课程，遇到了Knight Travails作业，它类似LeetCode的“Minimum Knight Moves”但要求更多。作业要求：

• 编写脚本创建棋盘和骑士；
• 将骑士的所有合法移动视为树的子节点，不允许移出棋盘；
• 选择合适的搜索算法（提示：某算法可能产生无限序列）；
• 用所选算法找到起点到终点的最短路径并输出完整路径，示例如下：

> knightMoves([3,3],[4,3])
=> You made it in 3 moves!  Here's your path:
  [3,3]
  [4,5]
  [2,4]
  [4,3]

当前实现代码 #

以下是我当前的解决方案，虽未完全符合要求但已接近：

'use strict'
class Traversal {
  constructor (x, y) {
    this.x = x
    this.y = y
    this.xDir = [-1, 1, -1, 1, -2, -2, 2, 2] // LEFT-RIGHT
    this.yDir = [2, 2, -2, -2, 1, -1, 1, -1] // UP-DOWN
  }

  calculateMoves (targetX = 0, targetY = 0) {
    const viableMoves = [] // coords of the locations the knight can reach from his current position
    let queue = [[this.x, this.y]]
    const visited = new Set()
    let steps = 0 // holds the minimal amount of moves to reach the target
    for (let i = 0; i < this.xDir.length && i < this.yDir.length; i++) {
      viableMoves.push([(this.x + this.xDir[i]), (this.y + this.yDir[i])]) // this will correctly calculate viable moves I think? sure seems to work in the console
    }
    queue = [...viableMoves] // populate the queue with moves the knight can make at this moment

    while (queue.length) {
      const next = []
      while (queue.length) {
        const current = queue.shift()
        const currentX = current[0] // extract current position from the queue
        const currentY = current[1] // extract current position from the queue
        if (currentX === targetX && currentY === targetY) { // we've found our goal if this is truthy
          return steps
        }
        for (const d of viableMoves) { 
          const nextX = currentX + d[0]
          const nextY = currentY + d[1]

          if (!visited.has(`${nextX},${nextY}`)) { // this entire part might have to be rewritten, I barely understand wtf this is
            visited.add(`${nextX},${nextY}`)
            next.push([nextX, nextY])
          }
        }
      }
      steps++
      queue = next
    }
  }
}

待解决问题 #

该代码可正常运行：实例化Traversal对象后调用calculateMoves方法传入目标位置，会返回到达目标所需的最少步数。但我仍需实现检测到目标的实际路径并将其以数组形式返回的功能，对此我有些困惑，仅能想到用另一个数组存储接近目标的坐标，但不确定具体该存储什么。另外，当前实现假设棋盘是无限的，坐标可为负值，不确定这是否会对可行解决方案产生重大影响，必要时我可以重写整个代码。

内容的提问来源于stack exchange，提问作者Lucas