Skip to content

Instantly share code, notes, and snippets.

@rrichardsonv

rrichardsonv/maze.js

Created April 27, 2018 22:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rrichardsonv/24ba83995d1d7271e04e41307b3fc04f to your computer and use it in GitHub Desktop.
Save rrichardsonv/24ba83995d1d7271e04e41307b3fc04f to your computer and use it in GitHub Desktop.
Download ZIP
MazeGeneration(might as well be stream of consciousness haha)
Raw
maze.js
// create a function that accepts two paraments: an empty maze and a starting coordinate
// the maze will be an array of arrays of objects. the objects will look like:
// {
// "n": true,
// "e": true,
// "s": true,
// "w": true,
// "visited": false
// }
//
// the outer array (that contains arrays) represents the y axis. the inner arrays (that contains
// objects) are represent the x axis. maze[y][x]
//
// the starting coordinates will be a pair, an array of two numbers, [x, y]. the first
// number will be the x position and the second will be the y position
//
// generateMaze will return the same maze (you can operate on the parameter itself)
//
// a function called randomizeDirection is globally available. it will return to you an array of
// ['n', 'e', 's', 'w'] in random order. in order to be able unit test this, these return values
// are pre-determined. if you want to have a truly random return, call setOrder(null) (another
// globally available function.) if you call it too frequently to pass the unit test, you'll see an
// error in the console.
//
// it will also attempt to draw your maze as you write your algorithm. you'll see two lines for each
// cell since neighbors each has its own walls. writeMaze assumes your data is well formatted . if you
// have unvisted cells, they'll be highlighted in red
//
// if you'd like to see the utlities functions, they're kept in this CodePen:
// https://codepen.io/btholt/pen/bLEryO?editors=0010
//
// I highly suggest you work on one unit test at a time. Mark the others `xit('...', () => ...)` instead of
// `it('...', () => ...)` so they won't run.
const buildMaze = (maze, x, y, dir) => {
let i = 0;
maze[y][x].visited = true;
while(i < 4){
let next = nextCoords(maze, dir[i], x, y);
if(next && maze[y][x][dir[i]] && !maze[next.y][next.x].visited){
maze[y][x][dir[i]] = false;
let opp = OPPOSITE[dir[i]];
maze[next.y][next.x][opp] = false;
buildMaze(maze, next.x, next.y, randomizeDirection());
}
i++;
}
return maze
}
const OPPOSITE = {e: 'w', w: 'e', s: 'n', n:'s'};
const nextCoords = (maze, dir, x, y) => {
return nextCoordsForLength(maze.length)(x, y)(dir);
}
const nextCoordsForLength = (length) => (x, y) => (dir) => {
if(dir === 'n' && y + 1 < length) {
return {x, y:y+1, dir, opp: OPPOSITE[dir]};
}
if(dir === 's' && y > 0) {
return {x, y:y-1, dir, opp: OPPOSITE[dir]};
}
if(dir === 'e' && x + 1 < length) {
return {x:x+1, y, dir, opp: OPPOSITE[dir]};
}
if(dir === 'w' && x > 0) {
return {x:x-1, y, dir, opp: OPPOSITE[dir]};
}
return false;
}
const recursiveGen = (maze, startX, startY, directions, getNextStartingAt) => {
maze[startY][startX].visited = true;
const getNext = getNextStartingAt(startX, startY);
directions
.map(getNext)
.filter(dir => !!dir)
.forEach(({x, y, dir, opp}) => {
if(maze[startY][startX][dir] && !maze[y][x].visited){
maze[startY][startX][dir] = false;
maze[y][x][opp] = false;
recursiveGen(maze, x, y, randomizeDirection(), getNextStartingAt);
}
});
}
const generateMaze = (maze, [xStart, yStart]) => {
// const getNextCoords = nextCoordsForLength(maze.length);
// recursiveGen(maze, xStart, yStart, randomizeDirection(), getNextCoords);
buildMaze(maze, xStart, yStart, randomizeDirection());
return maze;
};
// unit tests
// do not modify the below code
describe("mazes", function() {
beforeEach(() => {});
it("5x5", () => {
setOrder(1);
const maze = generateMaze(genEmptyMaze(5, 5), [0, 0]);
writeMaze(maze, document.getElementById("maze-1"));
expect(maze).toEqual([
[
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: false, e: true, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true }
],
[
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: false, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true }
],
[
{ n: true, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true }
]
]);
});
it("8x8", () => {
setOrder(2);
const maze = generateMaze(genEmptyMaze(8, 8), [5, 3]);
writeMaze(maze, document.getElementById("maze-2"));
expect(maze).toEqual([
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: true, visited: true },
{ n: false, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: true, visited: true }
],
[
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true }
],
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true }
]
]);
});
it("15x15", () => {
setOrder(3);
const maze = generateMaze(genEmptyMaze(15, 15), [10, 2]);
writeMaze(maze, document.getElementById("maze-3"));
expect(maze).toEqual([
[
{ n: false, e: true, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true }
],
[
{ n: false, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: true, s: true, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: true, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: false, visited: true }
],
[
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: true, s: false, w: true, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: false, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: false, w: false, visited: true }
],
[
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: true, w: false, visited: true },
{ n: false, e: true, s: false, w: true, visited: true },
{ n: true, e: true, s: false, w: true, visited: true }
],
[
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: true, s: false, w: true, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: false, e: false, s: true, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: false, e: true, s: true, w: false, visited: true }
],
[
{ n: true, e: true, s: false, w: true, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: true, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: false, s: false, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true },
{ n: true, e: false, s: false, w: true, visited: true },
{ n: true, e: false, s: true, w: false, visited: true },
{ n: true, e: true, s: false, w: false, visited: true }
]
]);
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment