CODEWITHSUNDEEP
javascriptalgorithmrecursive-backtracking
romainberger
romainberger

Reputation: 4558

Recursive backtracking to generate mazes

I'm trying to write a maze generator using the recursive backtracking algorithm. I've taken the example code from this article and more or less translated it to javascript. But it doesn't seem to work as all the rows are identical in the generated grid.

I don't know anything about this kind of thing and I'm stuck here. Anybody can see what I'm doing wrong?

Edit: 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

Upvotes: 3

Views: 1917

Answers (2)

phyatt
phyatt

Reputation: 19102

I filled in the problematic code with the two suggestions by @musically_ut . Here's the result:

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

Upvotes: 0

musically_ut
musically_ut

Reputation: 34288

The problem is with the statement:

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

You are using the same array for each row of the grid.

To solve it, you should create a new array for each row:

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

And finally, replace all undefined in the grid with 0, if necessary.

Upvotes: 3

Related Questions