使用递归回溯算法生成迷宫

Question

我正在尝试使用递归回溯算法编写迷宫生成器。我已经从这篇文章中获取了示例代码，并将其翻译为JavaScript。但是，生成的网格中所有行都相同，似乎并没有起作用。

我对这种事情一无所知，现在陷入了困境。有人能看出我做错了什么吗？

编辑： jsfiddle

// initialize the grid
var grid = []
  , cells = []
  // duplicate to avoid overriding
  , w = width
  , h = height
while (w--) cells.push(0)
while (h--) grid.push(cells)

var N = 1
  , S = 2
  , E = 4
  , W = 8
  , dirs = ['N', 'E', 'S', 'W']
  , dirsValue = { N: N, E: E, S: S, W: W }
  , DX = { E: 1, W: -1, N: 0, S: 0 }
  , DY = { E: 0, W: 0, N: -1, S: 1 }
  , OPPOSITE = { E: W, W: E, N: S, S: N }

function carve_passages_from(cx, cy, grid) {
  var directions = shuffle(dirs)

  directions.forEach(function(direction) {
    var nx = cx + DX[direction]
      , ny = cy + DY[direction]

    if (ny >= 0 && ny <= (grid.length - 1) && nx >= 0
      && nx <= (grid.length - 1) && grid[ny][nx] === 0) {
      grid[cy][cx] += dirsValue[direction]
      grid[ny][nx] += OPPOSITE[direction]
      carve_passages_from(nx, ny, grid)
    }
  })
}

carve_passages_from(0, 0, grid)

return grid

- romainberger

Answer 1

问题出在这个语句上：

while (h--) grid.push(cells)

您正在对grid的每一行使用同一个数组。

为解决此问题，您应该为每一行创建一个新的数组：

while (h--) grid.push(new Array(w))

最后，如果需要，请将网格中所有的undefined替换为0。

- musically_ut

Answer 2

我用@musically_ut提供的两个建议填写了有问题的代码。 这是结果：

function shuffle(o){
      for (var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
      return o;
  };

var width = 10
  , height = 10

// initialize the grid
    var grid = []
      , cells = []
      // duplicate to avoid overriding
      , w = width
      , h = height
    while (h--) grid.push(new Array(w))
    while (w--) cells.push(0)
    for(var r = 0; r < height; r++){
      for(var c = 0; c < width; c++){
        grid[r][c] = 0;
      }
    }
    
    var N = 1
      , S = 2
      , E = 4
      , W = 8
      , dirs = ['N', 'E', 'S', 'W']
      , dirsValue = { N: N, E: E, S: S, W: W }
      , DX = { E: 1, W: -1, N: 0, S: 0 }
      , DY = { E: 0, W: 0, N: -1, S: 1 }
      , OPPOSITE = { E: W, W: E, N: S, S: N }

    function carve_passages_from(cx, cy, grid) {
      var directions = shuffle(dirs)

      directions.forEach(function(direction) {
        var nx = cx + DX[direction]
          , ny = cy + DY[direction]

        if (ny >= 0 && ny <= (grid.length - 1) && nx >= 0
          && nx <= (grid.length - 1) && grid[ny][nx] === 0) {
          grid[cy][cx] += dirsValue[direction]
          grid[ny][nx] += OPPOSITE[direction]
          carve_passages_from(nx, ny, grid)
        }
      })
    }

    carve_passages_from(0, 0, grid)

    document.querySelector('div').innerHTML = grid

- phyatt