maze.js

// 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)));