mdengler/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Wilson’s algorithm uses loop-erased random walks to generate a uniform spanning tree — an unbiased sample of all possible spanning trees. Most other maze generation algorithms, such as Prim’s, random traversal and randomized depth-first traversal, do not have this beautiful property.
The algorithm initializes the maze with eight arbitrary starting cells. Then, a new cell is added to the maze, initiating a random walk (shown in magenta). The random walk continues until it reconnects with the existing maze (shown in white). However, if the random walk intersects itself, the resulting loop is erased before the random walk continues.
The global structure of the maze can be more easily seen by flooding it with color.
To play with this yourself, instructions from Uehreka on http://news.ycombinator.com:

Fork this Gist and make your changes.
Go to http://bl.ocks.org/<your github userame>, find your gist, and click on it to see the finished product.  bl.ocks just displays whatever Gists you have up on GitHub, so you don't have to make an account or anything.

The original demonstration initially chose only one arbitrary cell to color in; this is natural, but not as illustrative.
Initially, the algorithm was often frustratingly slow to watch, as the early random walks are unlikely to reconnect with the small existing maze. As the maze grew, this was no longer an issue: the random walks become more likely to collide with the maze and the algorithm accelerated dramatically.  By adding more than one initially-colored cell to the maze, we dramatically increase the likelihood the early random walks will collide with the maze.

  
## 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;

var cellSize = 4,
    cellSpacing = 4,
    cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
    remaining = d3.range(cellWidth * cellHeight), // cell indexes to visit
    previous = new Array(cellWidth * cellHeight), // current random walk path
    i0, x0, y0; // end of current random walk

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

// Add the starting cells.
context.fillStyle = "white";
for (var k = 0; k < 8; ++k) {
  var arbitraryIndex = Math.floor(Math.random() * remaining.length);
  remaining.splice(arbitraryIndex, 1);
  cells[arbitraryIndex] = 0;
  fillCell(arbitraryIndex);
}


// While there are remaining cells,
// add a loop-erased random walk to the maze.
context.fillStyle = "magenta";
d3.timer(function() {
  for (var k = 0; k < 50; ++k) {
    if (loopErasedRandomWalk()) {
      return true;
    }
  }
});

function loopErasedRandomWalk() {
  var i1;

  // Pick a location that’s not yet in the maze (if any).
  if (i0 == null) {
    do if ((i0 = remaining.pop()) == null) return true;
    while (cells[i0] >= 0);
    previous[i0] = i0;
    fillCell(i0);
    x0 = i0 % cellWidth;
    y0 = i0 / cellWidth | 0;
    return;
  }

  // Perform a random walk starting at this location,
  // by picking a legal random direction.
  while (true) {
    i1 = Math.random() * 4 | 0;
    if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - cellWidth; }
    else if (i1 === 1) { if (y0 >= cellHeight - 1) continue; ++y0, i1 = i0 + cellWidth; }
    else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
    else { if (x0 >= cellWidth - 1) continue; ++x0, i1 = i0 + 1; }
    break;
  }

  // If this new cell was visited previously during this walk,
  // erase the loop, rewinding the path to its earlier state.
  if (previous[i1] >= 0) eraseWalk(i0, i1);

  // Otherwise, just add it to the walk.
  else {
    previous[i1] = i0;
    fillCell(i1);
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
  }

  // If this cell is part of the maze, we’re done walking.
  if (cells[i1] >= 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.
    context.save();
    context.fillStyle = "#fff";
    fillCell(i1);
    while ((i0 = previous[i1]) !== i1) {
      fillCell(i0);
      if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W, fillEast(i0);
      else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E, fillEast(i1);
      else if (i1 === i0 + cellWidth) cells[i0] |= S, cells[i1] |= N, fillSouth(i0);
      else cells[i0] |= N, cells[i1] |= S, fillSouth(i1);
      previous[i1] = NaN;
      i1 = i0;
    }
    context.restore();

    previous[i1] = NaN;
    i0 = null;
  } else {
    i0 = i1;
  }
}

function eraseWalk(i0, i2) {
  var i1;
  context.save();
  context.globalCompositeOperation = "destination-out";
  do {
    i1 = previous[i0];
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else fillSouth(i0);
    fillCell(i0);
    previous[i0] = NaN;
    i0 = i1;
  } while (i1 !== i2);
  context.restore();
}

function fillCell(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
}

function fillEast(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
}

function fillSouth(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}

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;

	var cellSize = 4,
	cellSpacing = 4,
	cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
	cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
	cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
	remaining = d3.range(cellWidth * cellHeight), // cell indexes to visit
	previous = new Array(cellWidth * cellHeight), // current random walk path
	i0, x0, y0; // end of current random walk

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

	// Add the starting cells.
	context.fillStyle = "white";
	for (var k = 0; k < 8; ++k) {
	var arbitraryIndex = Math.floor(Math.random() * remaining.length);
	remaining.splice(arbitraryIndex, 1);
	cells[arbitraryIndex] = 0;
	fillCell(arbitraryIndex);
	}


	// While there are remaining cells,
	// add a loop-erased random walk to the maze.
	context.fillStyle = "magenta";
	d3.timer(function() {
	for (var k = 0; k < 50; ++k) {
	if (loopErasedRandomWalk()) {
	return true;
	}
	}
	});

	function loopErasedRandomWalk() {
	var i1;

	// Pick a location that’s not yet in the maze (if any).
	if (i0 == null) {
	do if ((i0 = remaining.pop()) == null) return true;
	while (cells[i0] >= 0);
	previous[i0] = i0;
	fillCell(i0);
	x0 = i0 % cellWidth;
	y0 = i0 / cellWidth \| 0;
	return;
	}

	// Perform a random walk starting at this location,
	// by picking a legal random direction.
	while (true) {
	i1 = Math.random() * 4 \| 0;
	if (i1 === 0) { if (y0 <= 0) continue; --y0, i1 = i0 - cellWidth; }
	else if (i1 === 1) { if (y0 >= cellHeight - 1) continue; ++y0, i1 = i0 + cellWidth; }
	else if (i1 === 2) { if (x0 <= 0) continue; --x0, i1 = i0 - 1; }
	else { if (x0 >= cellWidth - 1) continue; ++x0, i1 = i0 + 1; }
	break;
	}

	// If this new cell was visited previously during this walk,
	// erase the loop, rewinding the path to its earlier state.
	if (previous[i1] >= 0) eraseWalk(i0, i1);

	// Otherwise, just add it to the walk.
	else {
	previous[i1] = i0;
	fillCell(i1);
	if (i1 === i0 - 1) fillEast(i1);
	else if (i1 === i0 + 1) fillEast(i0);
	else if (i1 === i0 - cellWidth) fillSouth(i1);
	else fillSouth(i0);
	}

	// If this cell is part of the maze, we’re done walking.
	if (cells[i1] >= 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.
	context.save();
	context.fillStyle = "#fff";
	fillCell(i1);
	while ((i0 = previous[i1]) !== i1) {
	fillCell(i0);
	if (i1 === i0 + 1) cells[i0] \|= E, cells[i1] \|= W, fillEast(i0);
	else if (i1 === i0 - 1) cells[i0] \|= W, cells[i1] \|= E, fillEast(i1);
	else if (i1 === i0 + cellWidth) cells[i0] \|= S, cells[i1] \|= N, fillSouth(i0);
	else cells[i0] \|= N, cells[i1] \|= S, fillSouth(i1);
	previous[i1] = NaN;
	i1 = i0;
	}
	context.restore();

	previous[i1] = NaN;
	i0 = null;
	} else {
	i0 = i1;
	}
	}

	function eraseWalk(i0, i2) {
	var i1;
	context.save();
	context.globalCompositeOperation = "destination-out";
	do {
	i1 = previous[i0];
	if (i1 === i0 - 1) fillEast(i1);
	else if (i1 === i0 + 1) fillEast(i0);
	else if (i1 === i0 - cellWidth) fillSouth(i1);
	else fillSouth(i0);
	fillCell(i0);
	previous[i0] = NaN;
	i0 = i1;
	} while (i1 !== i2);
	context.restore();
	}

	function fillCell(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
	}

	function fillEast(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
	}

	function fillSouth(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
	}

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

	</script>