Skip to content

Instantly share code, notes, and snippets.

@azulus

azulus/gist:472fb73184bcb3ea11a2

Created December 30, 2014 09:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save azulus/472fb73184bcb3ea11a2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save azulus/472fb73184bcb3ea11a2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. azulus created this gist Dec 30, 2014.
    207 changes: 207 additions & 0 deletions gistfile1.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,207 @@
    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;
    };