Skip to content

Instantly share code, notes, and snippets.

@graue graue/maze.js
Created Jul 6, 2014

Embed
What would you like to do?
// Adapted from Clojure code by Pablo Torres
// Original: https://gist.github.com/ptn/3c94f540b2e8d26bafce
var Immutable = require('immutable');
var V = Immutable.Vector;
var I = Immutable.fromNative;
// Helper: shuffle an immutable vector, returning a new one.
function shuffle(vec) {
var out = [];
for (var i = 0; i < vec.length; i++) {
var j = randInt(i + 1);
if (j !== i) {
out[i] = out[j];
}
out[j] = vec.get(i);
}
return I(out, true); // The boolean = whether to do shallow conversion.
}
// Helper: random int from 0 (inclusive) to n (non-inclusive).
function randInt(n) {
return Math.floor(Math.random() * n);
}
// Helper: flatten a vector of vectors (by one level only).
function flatten(vec) {
return vec.reduce(function(acc, val) {
return acc.concat(val);
});
}
// Returns neighbors of the given position, unbounded.
// In the order: top, bottom, left, right.
function neighbors(pos) {
x = pos.get(0);
y = pos.get(1);
return I([[-1, 0], [1, 0], [0, -1], [0, 1]]).map(function(xy) {
return I([xy.get(0)+x, xy.get(1)+y]);
});
}
// Pick a position to go to next. May return undefined if none possible.
function findNextPos(dim, pos, visited) {
var candidates = neighbors(pos);
candidates = candidates.filter(function(xy) {
var x = xy.get(0), y = xy.get(1);
return x >= 0 && x < dim && y >= 0 && y < dim &&
visited.indexOf(xy) === -1;
});
return shuffle(candidates).get(0);
}
// Returns the tunnel carved through the walls of a square maze of the
// given dimension.
function tunnel(dim, path, positions, visited) {
if (arguments.length === 1) {
var initialPos = I([randInt(dim), randInt(dim)]);
path = I([]);
positions = I([initialPos]);
visited = positions; // Should really be a set.
}
while (positions.length > 0) {
var pos = positions.peek();
var nextPos = findNextPos(dim, pos, visited);
if (nextPos) {
path = path.push(I([pos, nextPos]));
positions = positions.push(nextPos);
visited = visited.push(nextPos);
} else {
positions = positions.pop();
}
}
return path;
}
// Returns a square maze of the given dimension where all walls exist.
function emptyMaze(dim) {
var cell = I([true, true, true, true]);
var row = [];
var i;
for (i = 0; i < dim; i++) {
row.push(cell);
}
row = I(row);
var maze = [];
for (i = 0; i < dim; i++) {
maze.push(row);
}
return I(maze);
}
// Destroy the given wall at pos.
function carve(maze, pos, idx) {
var x = pos.get(0), y = pos.get(1);
// I need a better way to make this nested update!
return maze.set(x,
maze.get(x).set(y,
maze.get(x).get(y).set(idx, false)));
}
// Generate a square maze of the given dimension.
function generateMaze(dim) {
var empty = emptyMaze(dim);
var generatedTunnel = tunnel(dim);
return generatedTunnel.reduce(function(maze, pairOfCells) {
var orig = pairOfCells.get(0), dest = pairOfCells.get(1);
maze = carve(maze, orig, neighbors(orig).indexOf(dest));
maze = carve(maze, dest, neighbors(dest).indexOf(orig));
return maze;
}, empty);
}
// maze is a vector [whole maze] of vectors [rows] of vectors [4 booleans,
// whether there is a wall at top, bottom, left, right].
function renderMazeRow(row) {
var strs = ['#', '#'];
var TOP = 0, BOTTOM = 1, LEFT = 2, RIGHT = 3;
row.forEach(function(cell) {
strs[0] += ' ' + (cell.get(RIGHT) ? '#' : ' ');
strs[1] += (cell.get(BOTTOM) ? '#' : ' ') + '#';
});
return I(strs);
}
// Render a maze as a string.
function renderMaze(maze) {
var topline = '';
for (var i = 0; i < maze.length*2+1; i++) {
topline += '#';
}
return topline + '\n' +
flatten(maze.map(renderMazeRow)).toNative().join('\n');
}
console.log(renderMaze(generateMaze(9)));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.