javascript - Maze (recursive division) algorithm design

Question

I am currently developing a random maze generator that stores the maze in a 2-dimensional array called grid. This will then be used later on to generate a real 3D maze that the user can then walk through.

After doing some research, I attempted to create this maze generator using the recursive division algorithm, however due to the nature of the format of the maze, this isn't really working for me.

From what I understand, the recursive division method does not treat walls as cells.

For instance, my grid would look like this:

  a b c d e f g h
1 - - - - - - - -
2 |   |   | |   |
3 |       |     |
4 | -   - |   - |
5 |     |     | |
6 |   - |   -   |
7 x             |
8 - - - - - - - -

The point that I'm trying to get across here is that the grid I am trying to create will be represented something like this:

w w w w w w w w
w   w   w w   w
w       w     w
w w   w w   w w
w     w     w w
w   w w   w   w
g             w
w w w w w w w w

Where 'w' is a wall and 'g' is the entrance/exit. So walls are placed into the grid, e.g. grid[1][2] == 'w'

The problem with the recursive division algorithm is that walls are not treated as members of the cell. All of the 'cells' would essentially contain whitespace and the walls would be placed around them.

So when I tried to implement this algorithm in my situation, I ended up with a result like this: (the black squares are walls, the white squares are empty, and the red square is the entrance)

My JSFiddle is located here.

Essentially the user will start at the red square and have to go through the maze and find keys that will open the door (which is the red square) to escape, so all of the whitespace in the maze would have to be accessible.

Does anyone have any ideas on how I can rewrite this algorithm to make sure that there is always a path from the red square to any other space in the maze? Ideally, the path would never be more than one square wide.

Code:

var grid;

function generate(dimensions, numDoors) {
    //numDoors is unused right now

    grid = new Array();
    for (var i = 0; i < dimensions; i++) {
        grid[i] = new Array();

        for (var j = 0; j < dimensions; j++) {
            grid[i][j] = "";
        }
    }

    addOuterWalls();
    var ent = addEntrance();
    addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}

function addOuterWalls() {
    for (var i = 0; i < grid.length; i++) {
        if (i == 0 || i == (grid.length - 1)) {
            for (var j = 0; j < grid.length; j++) {
                grid[i][j] = "w";
            }
        } else {
            grid[i][0] = "w";
            grid[i][grid.length - 1] = "w";
        }
    }
}

function addEntrance() {
    var x = randomNumber(1, grid.length - 1);
    grid[grid.length - 1][x] = "g";
    return x;
}

function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
    if (h) {

        if (maxX - minX < 2) {
            return;
        }

        var y = randomNumber(minY, maxY);
        addHWall(minX, maxX, y);

        addInnerWalls(!h, minX, maxX, minY, y-1, gate);
        addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
    } else {
        if (maxY - minY < 2) {
            return;
        }

        var x = randomNumber(minX, maxX);
        addVWall(minY, maxY, x);

        addInnerWalls(!h, minX, x-1, minY, maxY, gate);
        addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
    }
}

function addHWall(minX, maxX, y) {
    var hole = randomNumber(minX, maxX);

    for (var i = minX; i <= maxX; i++) {
        if (i == hole) grid[y][i] = "";
        else grid[y][i] = "w";
    }
}

function addVWall(minY, maxY, x) {
    var hole = randomNumber(minY, maxY);

    for (var i = minY; i <= maxY; i++) {
        if (i == hole) grid[i][x] = "";
        else grid[i][x] = "w";
    }
}

function randomNumber(min, max) {
    return Math.floor(Math.random() * (max - min + 1) + min);
}

function display() {
    document.getElementById("cnt").innerHTML = "";

    for (var i = 0; i < grid.length; i++) {
        var output = "<div>";
        for (var j = 0; j < grid.length; j++) {
            output += "<b " + grid[i][j] + "></b>";
        }
        output += "</div>";
        document.getElementById("cnt").innerHTML += output;
    }
}
generate(30, 1, 1);
display();

Answer 1

Put walls only in even cells, and doors in odd cells, and make "dimensions" odd. http://jsfiddle.net/tPm3s/1/

Code:
var grid;

function generate(dimensions, numDoors) {
    grid = new Array();
    for (var i = 0; i < dimensions; i++) {
        grid[i] = new Array();

        for (var j = 0; j < dimensions; j++) {
            grid[i][j] = "";
        }
    }

    addOuterWalls();
    var ent = addEntrance();
    addInnerWalls(true, 1, grid.length - 2, 1, grid.length - 2, ent);
}

function addOuterWalls() {
    for (var i = 0; i < grid.length; i++) {
        if (i == 0 || i == (grid.length - 1)) {
            for (var j = 0; j < grid.length; j++) {
                grid[i][j] = "w";
            }
        } else {
            grid[i][0] = "w";
            grid[i][grid.length - 1] = "w";
        }
    }
}

function addEntrance() {
    var x = randomNumber(1, grid.length - 1);
    grid[grid.length - 1][x] = "g";
    return x;
}

function addInnerWalls(h, minX, maxX, minY, maxY, gate) {
    if (h) {

        if (maxX - minX < 2) {
            return;
        }

        var y = Math.floor(randomNumber(minY, maxY)/2)*2;
        addHWall(minX, maxX, y);

        addInnerWalls(!h, minX, maxX, minY, y-1, gate);
        addInnerWalls(!h, minX, maxX, y + 1, maxY, gate);
    } else {
        if (maxY - minY < 2) {
            return;
        }

        var x = Math.floor(randomNumber(minX, maxX)/2)*2;
        addVWall(minY, maxY, x);

        addInnerWalls(!h, minX, x-1, minY, maxY, gate);
        addInnerWalls(!h, x + 1, maxX, minY, maxY, gate);
    }
}

function addHWall(minX, maxX, y) {
    var hole = Math.floor(randomNumber(minX, maxX)/2)*2+1;

    for (var i = minX; i <= maxX; i++) {
        if (i == hole) grid[y][i] = "";
        else grid[y][i] = "w";
    }
}

function addVWall(minY, maxY, x) {
    var hole = Math.floor(randomNumber(minY, maxY)/2)*2+1;

    for (var i = minY; i <= maxY; i++) {
        if (i == hole) grid[i][x] = "";
        else grid[i][x] = "w";
    }
}

function randomNumber(min, max) {
    return Math.floor(Math.random() * (max - min + 1) + min);
}

function display() {
    document.getElementById("cnt").innerHTML = "";

    for (var i = 0; i < grid.length; i++) {
        var output = "<div>";
        for (var j = 0; j < grid.length; j++) {
            output += "<b " + grid[i][j] + "></b>";
        }
        output += "</div>";
        document.getElementById("cnt").innerHTML += output;
    }
}
generate(31, 1, 1);
display();