StuartFeldt/README.md

## README.md

      
    Raw
  

              README.md
            
          
    This maze is generated using Wilson’s algorithm and then solved using breadth-first search. Compare to best-first search.

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  background: #000;
}

</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 960;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3,
    visited = 1 << 4;

var cellSize = 4,
    cellSpacing = 4,
    cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells = generateMaze(cellWidth, cellHeight);

var parent = d3.range(cellHeight * cellWidth).map(function() { return NaN; }),
    previous = (cellHeight - 1) * cellWidth,
    goalX = cellWidth - 1 - !((cellWidth & 1) | (cellHeight & 1)),
    goalY = 0,
    goalIndex = goalX + goalY * cellWidth,
    frontier = [previous];

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

context.translate(
  Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
  Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);

context.fillStyle = "#fff";

for (var j = 0; j < cellHeight; ++j) {
  for (var i = 0; i < cellWidth; ++i) {
    if (cells[j * cellWidth + i] >= 0) context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize);
    if (cells[j * cellWidth + i] & E) context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize);
    if (cells[j * cellWidth + i] & S) context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
  }
}

context.lineWidth = cellSize;
context.lineCap = "square";
context.strokeStyle = "#777";
context.translate(cellSize / 2, cellSize / 2);

d3.timer(function() {
  var done, k = 0;
  while (++k < 10 && !(done = exploreFrontier()));
  return done;
});

function exploreFrontier() {
  if ((i0 = popRandom(frontier)) == null) return true;

  var i0,
      x0 = i0 % cellWidth,
      y0 = i0 / cellWidth | 0,
      s0 = score(i0),
      i1;

  cells[i0] |= visited;

  context.strokeStyle = "#777";
  strokePath(previous);
  context.strokeStyle = "magenta";
  strokePath(previous = i0);
  if (!s0) return true;

  if (cells[i0] & N && !(cells[i1 = i0 - cellWidth] & visited)) parent[i1] = i0, frontier.push(i1);
  if (cells[i0] & S && !(cells[i1 = i0 + cellWidth] & visited)) parent[i1] = i0, frontier.push(i1);
  if (cells[i0] & W && !(cells[i1 = i0 - 1] & visited)) parent[i1] = i0, frontier.push(i1);
  if (cells[i0] & E && !(cells[i1 = i0 + 1] & visited)) parent[i1] = i0, frontier.push(i1);
}

function strokePath(index) {
  context.beginPath();
  moveTo(index);
  while (!isNaN(index = parent[index])) lineTo(index);
  context.stroke();
}

function moveTo(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.moveTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing);
}

function lineTo(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.lineTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing);
}

function score(i) {
  var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth | 0);
  return x * x + y * y;
}

function popRandom(array) {
  if (!(n = array.length)) return;
  var n, i = Math.random() * n | 0, t;
  t = array[i], array[i] = array[n - 1], array[n - 1] = t;
  return array.pop();
}

function generateMaze(width, height) {
  var cells = new Array(width * height), // each cell’s edge bits
      remaining = d3.range(width * height), // cell indexes to visit
      previous = new Array(width * height); // current random walk

  // Add a random cell.
  var start = remaining.pop();
  cells[start] = 0;

  // While there are remaining cells,
  // add a loop-erased random walk to the maze.
  while (!loopErasedRandomWalk());

  return cells;

  function loopErasedRandomWalk() {
    var direction,
        index0,
        index1,
        i,
        j;

    // Pick a location that’s not yet in the maze (if any).
    do if ((index0 = remaining.pop()) == null) return true;
    while (cells[index0] >= 0);

    // Perform a random walk starting at this location,
    previous[index0] = index0;
    walk: while (true) {
      i = index0 % width;
      j = index0 / width | 0;

      // picking a legal random direction at each step.
      direction = Math.random() * 4 | 0;
      if (direction === 0) { if (j <= 0) continue walk; --j; }
      else if (direction === 1) { if (j >= height - 1) continue walk; ++j; }
      else if (direction === 2) { if (i <= 0) continue walk; --i; }
      else { if (i >= width - 1) continue walk; ++i; }

      // If this new cell was visited previously during this walk,
      // erase the loop, rewinding the path to its earlier state.
      // Otherwise, just add it to the walk.
      index1 = j * width + i;
      if (previous[index1] >= 0) eraseWalk(index0, index1);
      else previous[index1] = index0;
      index0 = index1;

      // If this cell is part of the maze, we’re done walking.
      if (cells[index1] >= 0) {

        // Add the random walk to the maze by backtracking to the starting cell.
        // Also erase this walk’s history to not interfere with subsequent walks.
        while ((index0 = previous[index1]) !== index1) {
          direction = index1 - index0;
          if (direction === 1) cells[index0] |= E, cells[index1] |= W;
          else if (direction === -1) cells[index0] |= W, cells[index1] |= E;
          else if (direction < 0) cells[index0] |= N, cells[index1] |= S;
          else cells[index0] |= S, cells[index1] |= N;
          previous[index1] = NaN;
          index1 = index0;
        }

        previous[index1] = NaN;
        return;
      }
    }
  }

  function eraseWalk(index0, index1) {
    var index;
    while ((index = previous[index0]) !== index1) previous[index0] = NaN, index0 = index;
    previous[index0] = NaN;
  }
}

d3.select(self.frameElement).style("height", height + "px");

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	body {
	background: #000;
	}

	</style>
	<body>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script>

	var width = 960,
	height = 960;

	var N = 1 << 0,
	S = 1 << 1,
	W = 1 << 2,
	E = 1 << 3,
	visited = 1 << 4;

	var cellSize = 4,
	cellSpacing = 4,
	cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
	cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
	cells = generateMaze(cellWidth, cellHeight);

	var parent = d3.range(cellHeight * cellWidth).map(function() { return NaN; }),
	previous = (cellHeight - 1) * cellWidth,
	goalX = cellWidth - 1 - !((cellWidth & 1) \| (cellHeight & 1)),
	goalY = 0,
	goalIndex = goalX + goalY * cellWidth,
	frontier = [previous];

	var canvas = d3.select("body").append("canvas")
	.attr("width", width)
	.attr("height", height);

	var context = canvas.node().getContext("2d");

	context.translate(
	Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
	Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
	);

	context.fillStyle = "#fff";

	for (var j = 0; j < cellHeight; ++j) {
	for (var i = 0; i < cellWidth; ++i) {
	if (cells[j * cellWidth + i] >= 0) context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize);
	if (cells[j * cellWidth + i] & E) context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize);
	if (cells[j * cellWidth + i] & S) context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
	}
	}

	context.lineWidth = cellSize;
	context.lineCap = "square";
	context.strokeStyle = "#777";
	context.translate(cellSize / 2, cellSize / 2);

	d3.timer(function() {
	var done, k = 0;
	while (++k < 10 && !(done = exploreFrontier()));
	return done;
	});

	function exploreFrontier() {
	if ((i0 = popRandom(frontier)) == null) return true;

	var i0,
	x0 = i0 % cellWidth,
	y0 = i0 / cellWidth \| 0,
	s0 = score(i0),
	i1;

	cells[i0] \|= visited;

	context.strokeStyle = "#777";
	strokePath(previous);
	context.strokeStyle = "magenta";
	strokePath(previous = i0);
	if (!s0) return true;

	if (cells[i0] & N && !(cells[i1 = i0 - cellWidth] & visited)) parent[i1] = i0, frontier.push(i1);
	if (cells[i0] & S && !(cells[i1 = i0 + cellWidth] & visited)) parent[i1] = i0, frontier.push(i1);
	if (cells[i0] & W && !(cells[i1 = i0 - 1] & visited)) parent[i1] = i0, frontier.push(i1);
	if (cells[i0] & E && !(cells[i1 = i0 + 1] & visited)) parent[i1] = i0, frontier.push(i1);
	}

	function strokePath(index) {
	context.beginPath();
	moveTo(index);
	while (!isNaN(index = parent[index])) lineTo(index);
	context.stroke();
	}

	function moveTo(index) {
	var i = index % cellWidth, j = index / cellWidth \| 0;
	context.moveTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing);
	}

	function lineTo(index) {
	var i = index % cellWidth, j = index / cellWidth \| 0;
	context.lineTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing);
	}

	function score(i) {
	var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth \| 0);
	return x * x + y * y;
	}

	function popRandom(array) {
	if (!(n = array.length)) return;
	var n, i = Math.random() * n \| 0, t;
	t = array[i], array[i] = array[n - 1], array[n - 1] = t;
	return array.pop();
	}

	function generateMaze(width, height) {
	var cells = new Array(width * height), // each cell’s edge bits
	remaining = d3.range(width * height), // cell indexes to visit
	previous = new Array(width * height); // current random walk

	// Add a random cell.
	var start = remaining.pop();
	cells[start] = 0;

	// While there are remaining cells,
	// add a loop-erased random walk to the maze.
	while (!loopErasedRandomWalk());

	return cells;

	function loopErasedRandomWalk() {
	var direction,
	index0,
	index1,
	i,
	j;

	// Pick a location that’s not yet in the maze (if any).
	do if ((index0 = remaining.pop()) == null) return true;
	while (cells[index0] >= 0);

	// Perform a random walk starting at this location,
	previous[index0] = index0;
	walk: while (true) {
	i = index0 % width;
	j = index0 / width \| 0;

	// picking a legal random direction at each step.
	direction = Math.random() * 4 \| 0;
	if (direction === 0) { if (j <= 0) continue walk; --j; }
	else if (direction === 1) { if (j >= height - 1) continue walk; ++j; }
	else if (direction === 2) { if (i <= 0) continue walk; --i; }
	else { if (i >= width - 1) continue walk; ++i; }

	// If this new cell was visited previously during this walk,
	// erase the loop, rewinding the path to its earlier state.
	// Otherwise, just add it to the walk.
	index1 = j * width + i;
	if (previous[index1] >= 0) eraseWalk(index0, index1);
	else previous[index1] = index0;
	index0 = index1;

	// If this cell is part of the maze, we’re done walking.
	if (cells[index1] >= 0) {

	// Add the random walk to the maze by backtracking to the starting cell.
	// Also erase this walk’s history to not interfere with subsequent walks.
	while ((index0 = previous[index1]) !== index1) {
	direction = index1 - index0;
	if (direction === 1) cells[index0] \|= E, cells[index1] \|= W;
	else if (direction === -1) cells[index0] \|= W, cells[index1] \|= E;
	else if (direction < 0) cells[index0] \|= N, cells[index1] \|= S;
	else cells[index0] \|= S, cells[index1] \|= N;
	previous[index1] = NaN;
	index1 = index0;
	}

	previous[index1] = NaN;
	return;
	}
	}
	}

	function eraseWalk(index0, index1) {
	var index;
	while ((index = previous[index0]) !== index1) previous[index0] = NaN, index0 = index;
	previous[index0] = NaN;
	}
	}

	d3.select(self.frameElement).style("height", height + "px");

	</script>