Aldous-Broder Maze Algorithm

[wadez]

Hello,

I stumbled across this repo in search of maze algorithm implementations. I tried translating your code to Lua but I could not get the algorithm to work. For whatever reason, the algorithm would only generate zigzag patterns with a few joining cells...

Since then, I stumbled across the Aldous-Broder algorithm which you may find useful. The algorithm is the following:

// semi-pseudocode (translating from Lua to JS-like)

var visited = new Set();
function visit(cell) {
    cell.isVisited = true
    visited.add(cell)
}

function hasUnvisitedCells() {
    return visited.size < numberOfColumns * numberOfRows
}

function generate() {
    var cell = this.getRandomCell()
    visit(cell)
    while (this.hasUnvisitedCells()) {
        var neighbor = cell.neighbors.shuffle().first()
        if (!neighbor.isVisited) {
            cell.connect(neighbor)
            this.visit(neighbor)
        }
        cell = neighbor
   }
}

Cheers!