在 JavaScript 中实现递归回溯器？

Question

我有一个充满对象的二维数组。我想将这个数组转换成一个迷宫，其中一些对象是墙（它们有一个 isWall 属性应该标记为 true），一些对象是通道（isWall 将是 false）。

我正在尝试为此使用 Recursive Backtracking（我使用的是堆栈而不是递归），但我的迷宫显示如下

黑色方块代表墙壁，而白色方块代表通道。白色方块内的数字无关紧要（只是我用于 Djikstra 的权重）。

这是我在 JavaScript 中实现的递归回溯。

JavaScript
function isValid(r, c, grid) {
  if (r < 0 || c < 0) {
    return false;
  }
  if (r < grid.length && c < grid[r].length) {
    return true;
  }
  return false;
}

export default function recursiveBacktracker(grid, startNode, endNode) {

  // Fill Grid with walls
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[r].length; c++) {
      grid[r][c].isWall = true;
    }
  }

  let visited = new Set();
  let stack = [startNode];
  let neighbors = [
    [2, 0],
    [-2, 0],
    [0, 2],
    [0, -2]
  ];
  while (stack.length > 0) {
    let cur = stack.pop();
    let r = cur[0],
      c = cur[1];
    console.log(r, c);
    visited.add(r + "." + c);
    grid[r][c].isWall = false;
    for (let n of neighbors) {
      let rr = r + n[0];
      let cc = c + n[1];
      if (isValid(rr, cc, grid) && !visited.has(rr + "." + cc)) {
        grid[r + n[0] / 2][c + n[0] / 2].isWall = false;
        stack.push([rr, cc]);
        break;
      }
    }
  }
  return grid;
}

如果我能就我的代码哪里出了问题提供指导，我将不胜感激。谢谢！

Answer 1

我认为这个错误很可能是因为你的行

grid[r + n[0] / 2][c + n[0] / 2].isWall = false;

我觉得打错了，你想要的是

grid[r + n[0] / 2][c + n[1] / 2].isWall = false; //simply change n[0] to n[1]

现在 if 条件这里又出现了一个逻辑错误：

for (let n of neighbors) {
  let rr = r + n[0];
  let cc = c + n[1];
  if (isValid(rr, cc, grid) && !visited.has(rr + "." + cc)) {
    grid[r + n[0] / 2][c + n[0] / 2].isWall = false;
    stack.push([rr, cc]);
    break;
  }
}

递归回溯算法需要选择一个随机的可用邻居，而您所做的只是选择您找到的第一个可用邻居。如您所见，if 条件检查单元格是否可用，如果单元格可用则立即执行操作。

我尝试了运行代码，它只是变成了一条垂直线。因此，请尝试将可用坐标存储在列表中，然后从该新列表中随机选择一个坐标。这似乎修复了错误 :)

在 JavaScript 中实现递归回溯器？

Implementing a Recursive Backtracker in JavaScript?

javascript

algorithm

maze

graph-algorithm