Skip to content

Instantly share code, notes, and snippets.

@azulus
Created December 30, 2014 09:18
Show Gist options
  • Save azulus/472fb73184bcb3ea11a2 to your computer and use it in GitHub Desktop.
Save azulus/472fb73184bcb3ea11a2 to your computer and use it in GitHub Desktop.
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;
};
@drjasonharrison
Copy link

drjasonharrison commented Nov 24, 2023

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment