gistfile1.js

    var reducePath = function (x, y, entryOffset, rangeOffset, entryRequiredWall, entryDisallowedWall) {
        var rangeEntryRequiredDirections = [entryDisallowedWall, OppositeDirections[entryDisallowedWall]];
        var rangeEntryDisallowedDirections = [entryRequiredWall, OppositeDirections[entryRequiredWall]];
        var endDisallowedDirections = [OppositeDirections[entryRequiredWall], OppositeDirections[entryDisallowedWall]];
        var endRequiredDirections = [entryRequiredWall, entryDisallowedWall];

        var tile = tiles[x][y];
        var color = tile.color;
        var entry = tiles[x+entryOffset[0]][y+entryOffset[1]];

        // make sure theres a path from below
        if (!entry.walls[entryRequiredWall] ||
            entry.walls[entryDisallowedWall]) {
            return false;
        }

        // seed the next tile and starting tile for evaluation
        var endX = x+rangeOffset[0];
        var endY = y+rangeOffset[1];
        var end = tiles[endX][endY];
        var entry = tiles[endX+entryOffset[0]][endY+entryOffset[1]];

        // loop while the next tile continues as the boundary of the "U"
        while (end.walls[rangeEntryRequiredDirections[0]] &&
                !end.walls[rangeEntryDisallowedDirections[0]] &&
                !end.walls[rangeEntryDisallowedDirections[1]]) {
            if (entry.color !== EMPTY_COLOR) {
                // if the entry to the tile isn't a U, it must have walls 
                // on both sides perpindicular to the entry direction
                var dirs = Object.keys(entry.walls);
                if (dirs.length !== 2 || dirs[0] != OppositeDirections[dirs[1]]) {
                    return false;
                }
            }
            endX += rangeOffset[0];
            endY += rangeOffset[1];
            end = tiles[endX][endY];
            entry = tiles[endX+entryOffset[0]][endY+entryOffset[1]];
        }

        var endWallDirs = Object.keys(end.walls);

        if (endWallDirs.length !== 2) {
            // end wall must be a corner
            return false;
        }

        for (var key in endWallDirs) {
            if (key === entryDisallowedWall) {
                continue;
            } else if (!tile.walls[key] && key !== OppositeDirections[entryDisallowedWall]) {
                // if the wall doesn't exist on the origin and it's not blocking off
                // the direction we're collapsing into, it should be safe
                continue;
            }
            return false;
        }

        var endDown = tiles[endX+entryOffset[0]][endY+entryOffset[1]];
        if (endDown.color === EMPTY_COLOR ||
                !endDown.walls[OppositeDirections[entryRequiredWall]] ||
                endDown.walls[entryDisallowedWall]) {
            return false;
        }

        var startWalls = {};
        for (var key in tile.walls) {
            startWalls = tile.walls[key];
            delete startWalls[entryDisallowedWall];
        }

        for (var xOffset = 0, xIters = Math.abs(endX - x); xOffset <= xIters; xOffset++) {
            var changeX = Math.min(x, endX) + xOffset;
            for (var yOffset = 0, yIters = Math.abs(endY - y); yOffset <= yIters; yOffset++) {
                var changeY = Math.min(y, endY) + yOffset;

                var entryX = changeX+entryOffset[0];
                var entryY = changeY+entryOffset[1];
                entry = tiles[entryX][entryY];

                entry.walls[entryDisallowedWall] = true;

                var checkOffset, checkIters, checkMin, checkMax;

                if (rangeOffset[0] !== 0) {
                    checkOffset = xOffset;
                    checkIters = xIters;
                    checkMin = rangeOffset[0] > 0 ? xIters : 0;
                    checkMax = rangeOffset[0] > 0 ? 0 : xIters;
                } else {
                    checkOffset = yOffset;
                    checkIters = yIters;
                    checkMin = rangeOffset[1] > 0 ? yIters : 0;
                    checkMax = rangeOffset[1] > 0 ? 0 : yIters;
                }

                if (checkOffset > 0 && checkOffset < checkIters) {
                    if (entry.color === EMPTY_COLOR) {
                        entry.walls[OppositeDirections[entryDisallowedWall]] = true;
                    }
                    entry.walls[entryRequiredWall] = true;
                    entry.walls[OppositeDirections[entryRequiredWall]] = true;
                }
                if (checkOffset !== checkMin) {
                    delete entry.walls[entryRequiredWall];
                }
                if (checkOffset !== checkMax) {
                    delete entry.walls[OppositeDirections[entryRequiredWall]];
                }


                entry.color = color;

                tile = tiles[changeX][changeY];
                tile.walls = {};
                tile.color = EMPTY_COLOR;
            }
        }

        return true;
    };

    var reduceNorth = function(x, y) {
        var entryOffset = [0, -1];
        var rangeOffset = [1, 0];
        var entryRequiredWall = Directions.EAST;
        var entryDisallowedWall = Directions.SOUTH;

        return reducePath(x, y, entryOffset, rangeOffset, entryRequiredWall, entryDisallowedWall);
    };

    var reduceSouth = function(x, y) {
        var entryOffset = [0, 1];
        var rangeOffset = [1, 0];
        var entryRequiredWall = Directions.EAST;
        var entryDisallowedWall = Directions.NORTH;

        return reducePath(x, y, entryOffset, rangeOffset, entryRequiredWall, entryDisallowedWall);
    };

    var reduceEast = function(x, y) {
        var entryOffset = [1, 0];
        var rangeOffset = [0, 1];
        var entryRequiredWall = Directions.SOUTH;
        var entryDisallowedWall = Directions.WEST;

        return reducePath(x, y, entryOffset, rangeOffset, entryRequiredWall, entryDisallowedWall);
    };

    var reduceWest = function(x, y) {
        var entryOffset = [-1, 0];
        var rangeOffset = [0, 1];
        var entryRequiredWall = Directions.SOUTH;
        var entryDisallowedWall = Directions.EAST;

        return reducePath(x, y, entryOffset, rangeOffset, entryRequiredWall, entryDisallowedWall);
    };

    var reduceSlack = function() {
        var count = 0;
        do {
            var found = false;

            for (var x = 0; x <= MAX_X; x++) {
                for (var y = 0; y <= MAX_Y; y++) {
                    var tile = tiles[x][y];
                    var walls = tile.walls;
                    var dirs = Object.keys(walls);
                    var singleFound = false;

                    if (dirs.length !== 2) continue;

                    if (walls[Directions.NORTH]) {
                        if (walls[Directions.WEST]) {
                            if (y < MAX_Y) {
                                // top left corner could mean merging a slack path south
                                singleFound = reduceSouth(x, y);
                            }

                            if (!singleFound && x < MAX_X) {
                                // top left corner could mean merging a slack path east
                                singleFound = reduceEast(x, y);
                            }
                        } else if (walls[Directions.EAST] && x > 0) {
                            // top right corner could mean merging a slack path west
                            singleFound = reduceWest(x, y);
                        }

                    } else if (walls[Directions.SOUTH] && y > 0 && walls[Directions.WEST]) {
                        // bottom left corner could mean merging a slack path north
                        singleFound = reduceNorth(x, y);
                    }

                    if (singleFound) {
                        found = true;
                        count++;
                    }
                    if (SHOULD_DEMO && count > 10) {
                        return false;
                    }
                }
            }

        } while (found);

        return true;
    };

See also https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ where the author of this gist commented:

Jeremy Stanley 9 years ago

I went ahead and reimplemented this (very non-performantly for now) using React and plain Javascript and ended up feeling the same way about the windyness of the maze as you had expressed. I added an extra step towards the end which is a bit costly but reduces slack in the maze. See http://fishi.es/dungeon or http://fishi.es/dungeon/demo to see it in being drawn. Here's the source for the slack-reduction algorithm: https://gist.github.com/azu...