Given some parameters to create a maze out of a grid of 0's and 1's, determines if we can get from a start point to an exit.

MazeHasExit.js

/**
 * The purpose of this is to randomly generate a grid of preset height and width (dimensionX, dimensionY)
 * with each cell either a 0 or a 1.  There is a randomly assigned start and exit position, and you must
 * determine if, by following a trail of contiguous ones in the up, down, left, right positions, you can
 * get from the start to the exit.
 *
 * Assumptions:
 * 1. the start coordinates fall within valid grid
 * 2. You can only move up, down, left, right
 * 3. You cannot jump a 0.
 * 4. You may only move where a 1 exists.
 */

/**
 * Generate the grid, passing in a difficulty rating which
 * is a value between 1 and 2.  The higher the difficulty, the
 * less a change of finding a way out
 */
function generateInput(x, y, difficulty) {
    input = [];
    for (var i = 0; i < y; i++) {
        var arr = [];
        for (var j = 0; j < x; j++) {
            arr[j] = Math.round(Math.random() / difficulty);
        }
        input[i] = arr;
    }

    /**
     * Writeout the grid to the console, so we can verify this
     */
    input.forEach(function (row) {
            console.log(row.toString());
        });

    return input;
}

/**
 * Set the dimensions and difficulty, the input grid, start coordinates and
 * end coordinates will be generated automatically here
 */
var dimensionX = 8
    , dimensionY = 8
    , difficultyMultiplier = 1
    , input = generateInput(dimensionX, dimensionY, difficultyMultiplier)
    , exit = [(Math.round(Math.random() * (dimensionX - 1))), (Math.round(Math.random() * (dimensionY - 1)))]
    , start = [(Math.round(Math.random() * (dimensionX - 1))), (Math.round(Math.random() * (dimensionY - 1)))];


/**
 * This allows us to visualize the start and end points in the console writeout, below
 */
input[start[1]][start[0]] = "S";
input[exit[1]][exit[0]] = "E";

var alreadyTraveled = {};
var hasExited = false;
var totalMoves = 0;

/**
 * Recursive function to get all possible moves.  Each
 * possible move is verified against previous position traveled, as
 * we don't want to double back, and is verified against the grid itself
 * to determine if we can move there or not.
 *
 * Only by recursing through this may we eventually land on the exit, at which point
 * we abort operations.
 */
var getPossibleMoves = function (coords) {
    var x = coords[0]
        , y = coords[1];

    setAlreadyTraveled(x, y);

    console.log("Move Number " + ++totalMoves + "; " + x + "," + y);

    if (isExit(x, y) == true) {
        hasExited = true;
        console.log("Moved Matched! " + x + "," + y);
        return true;
    }

    var newMoves = [];
    getUpPosition(x, y, newMoves);
    getRightPosition(x, y, newMoves);
    getDownPosition(x, y, newMoves);
    getLeftPosition(x, y, newMoves);

    while (newMoves.length && hasExited == false) {
        if (getPossibleMoves(newMoves.shift())) {
            return true;
        }
    }

    console.log("NO MOVES MATCHED: " + x + "," + y);
    return false;
};

getUpPosition = function (x, y, arr) {
    if (y == 0) {
        return null;
    }

    if (isValidPosition(x, y - 1)) {
        var result = [x, y-1];
        if (arr) {
            arr.push(result);
        }
        return result;
    }

    return null;
};

getRightPosition = function (x, y, arr) {
    if (x >= dimensionX - 1) {
        return null;
    }
    if (isValidPosition(x + 1, y)) {
        var result = [x + 1, y];
        if (arr) {
            arr.push(result);
        }
        return result;
    }

    return null;
};

getDownPosition = function (x, y, arr) {
    if (y >= dimensionY - 1) {
        return null;
    }

    if (isValidPosition(x, y + 1)) {
        var result = [x, y + 1];
        if (arr) {
            arr.push(result);
        }
        return result;
    }

    return null;
};

getLeftPosition = function (x, y, arr) {
    if (x <= 0) {
        return null;
    }

    if (isValidPosition(x - 1, y)) {
        var result = [x - 1, y];
        if (arr) {
            arr.push(result);
        }
        return result;
    }

    return null;
};

var isValidPosition = function (x, y) {
    return (isExit(x,y) || input[y][x] == 1) && isAlreadyTraveled(x, y) == false && !(x == start[0] && y == start[1]);
};

var isAlreadyTraveled = function (x, y) {
    return alreadyTraveled[x + "," + y] === true;
};

var setAlreadyTraveled = function (x, y) {
    alreadyTraveled[x + "," + y] = true;
};

var isExit = function (x, y) {
    return x == exit[0] && y == exit[1];
};


//Start the process!
(function() {
    var hasAWayOut = getPossibleMoves(start);

    console.log("HAS A WAY OUT: " + hasAWayOut);
})();