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
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.