mbostock · September 11, 2024 10:57 · Rufflewind · Jun 18, 2017
diff --git a/.block b/.block
 license: gpl-3.0
diff --git a/README.md b/README.md
diff --git a/generate-wilsons.js b/generate-wilsons.js
 var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

 self.addEventListener("message", function(event) {
  postMessage(generateMaze(event.data.width, event.data.height));
 });

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

  // Add the starting 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 i0,
        i1,
        x0,
        y0;

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

    // Perform a random walk starting at this location,
    previous[i0] = i0;
    while (true) {
      x0 = i0 % width;
      y0 = i0 / width | 0;

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

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

      // 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.
        while ((i0 = previous[i1]) !== i1) {
          if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W;
          else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E;
          else if (i1 === i0 + width) cells[i0] |= S, cells[i1] |= N;
          else cells[i0] |= N, cells[i1] |= S;
          previous[i1] = NaN;
          i1 = i0;
        }

        previous[i1] = NaN;
        return;
      }

      i0 = i1;
    }
  }

  function eraseWalk(i0, i2) {
    var i1;
    do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
  }
 }

 function range(n) {
  var range = new Array(n), i = -1;
  while (++i < n) range[i] = i;
  return range;
 }
diff --git a/index.html b/index.html
 <!DOCTYPE html>
 <meta charset="utf-8">
 <style>

 #wait {
  padding: 10px;
 }

 </style>
 <div id="wait">Please wait a moment; this is hard.</div>
 <canvas width="960" height="500"></canvas>
 <script src="//d3js.org/d3.v3.min.js"></script>
 <script>

 var canvas = d3.select("canvas"),
    context = canvas.node().getContext("2d"),
    width = canvas.property("width"),
    height = canvas.property("height");

 var worker = new Worker("generate-wilsons.js");
 worker.postMessage({width: width, height: height});
 worker.addEventListener("message", function(event) {
  worker.terminate();

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

  var cells = event.data,
      distance = 0,
      visited = new Array(width * height),
      frontier = [(height - 1) * width],
      image = context.createImageData(width, height);

  d3.select("#wait").transition()
      .style("opacity", 0)
      .remove();

  function flood() {
    var frontier1 = [],
        i0,
        n0 = frontier.length,
        i1,
        color = d3.hsl((distance += .5) % 360, 1, .5).rgb();

    for (var i = 0; i < n0; ++i) {
      i0 = frontier[i] << 2;
      image.data[i0 + 0] = color.r;
      image.data[i0 + 1] = color.g;
      image.data[i0 + 2] = color.b;
      image.data[i0 + 3] = 255;
    }

    for (var i = 0; i < n0; ++i) {
      i0 = frontier[i];
      if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, frontier1.push(i1);
      if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, frontier1.push(i1);
      if (cells[i0] & S && !visited[i1 = i0 + width]) visited[i1] = true, frontier1.push(i1);
      if (cells[i0] & N && !visited[i1 = i0 - width]) visited[i1] = true, frontier1.push(i1);
    }

    frontier = frontier1;
    return !frontier1.length;
  }

  d3.timer(function() {
    for (var i = 0, done; i < 3 && !(done = flood()); ++i);
    context.putImageData(image, 0, 0);
    return done;
  });
 });

 </script>
diff --git a/thumbnail.png b/thumbnail.png
	var N = 1 << 0,
	S = 1 << 1,
	W = 1 << 2,
	E = 1 << 3;

	self.addEventListener("message", function(event) {
	postMessage(generateMaze(event.data.width, event.data.height));
	});

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

	// Add the starting 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 i0,
	i1,
	x0,
	y0;

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

	// Perform a random walk starting at this location,
	previous[i0] = i0;
	while (true) {
	x0 = i0 % width;
	y0 = i0 / width \| 0;

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

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

	// 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.
	while ((i0 = previous[i1]) !== i1) {
	if (i1 === i0 + 1) cells[i0] \|= E, cells[i1] \|= W;
	else if (i1 === i0 - 1) cells[i0] \|= W, cells[i1] \|= E;
	else if (i1 === i0 + width) cells[i0] \|= S, cells[i1] \|= N;
	else cells[i0] \|= N, cells[i1] \|= S;
	previous[i1] = NaN;
	i1 = i0;
	}

	previous[i1] = NaN;
	return;
	}

	i0 = i1;
	}
	}

	function eraseWalk(i0, i2) {
	var i1;
	do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
	}
	}

	function range(n) {
	var range = new Array(n), i = -1;
	while (++i < n) range[i] = i;
	return range;
	}
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	#wait {
	padding: 10px;
	}

	</style>
	<div id="wait">Please wait a moment; this is hard.</div>
	<canvas width="960" height="500"></canvas>
	<script src="//d3js.org/d3.v3.min.js"></script>
	<script>

	var canvas = d3.select("canvas"),
	context = canvas.node().getContext("2d"),
	width = canvas.property("width"),
	height = canvas.property("height");

	var worker = new Worker("generate-wilsons.js");
	worker.postMessage({width: width, height: height});
	worker.addEventListener("message", function(event) {
	worker.terminate();

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

	var cells = event.data,
	distance = 0,
	visited = new Array(width * height),
	frontier = [(height - 1) * width],
	image = context.createImageData(width, height);

	d3.select("#wait").transition()
	.style("opacity", 0)
	.remove();

	function flood() {
	var frontier1 = [],
	i0,
	n0 = frontier.length,
	i1,
	color = d3.hsl((distance += .5) % 360, 1, .5).rgb();

	for (var i = 0; i < n0; ++i) {
	i0 = frontier[i] << 2;
	image.data[i0 + 0] = color.r;
	image.data[i0 + 1] = color.g;
	image.data[i0 + 2] = color.b;
	image.data[i0 + 3] = 255;
	}

	for (var i = 0; i < n0; ++i) {
	i0 = frontier[i];
	if (cells[i0] & E && !visited[i1 = i0 + 1]) visited[i1] = true, frontier1.push(i1);
	if (cells[i0] & W && !visited[i1 = i0 - 1]) visited[i1] = true, frontier1.push(i1);
	if (cells[i0] & S && !visited[i1 = i0 + width]) visited[i1] = true, frontier1.push(i1);
	if (cells[i0] & N && !visited[i1 = i0 - width]) visited[i1] = true, frontier1.push(i1);
	}

	frontier = frontier1;
	return !frontier1.length;
	}

	d3.timer(function() {
	for (var i = 0, done; i < 3 && !(done = flood()); ++i);
	context.putImageData(image, 0, 0);
	return done;
	});
	});

	</script>