mbostock/.block

## .block
license: gpl-3.0

## README.md

      
    Raw
  

              README.md
            
          
    Applying a tree layout on Wilson’s algorithm.

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

.link {
  fill: none;
  stroke: #000;
  stroke-width: 1.5px;
}

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

var margin = {top: 20, right: 20, bottom: 20, left: 20},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

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

var root = generateTree(40, 40);

var tree = d3.layout.tree()
    .size([height, width]);

var nodes = tree.nodes(root),
    links = tree.links(nodes);

var svg = d3.select("body").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

svg.selectAll(".link")
    .data(links)
  .enter().append("path")
    .attr("class", "link")
    .attr("d", function(d) { return "M" + d.source.y + "," + d.source.x + "L" + d.target.y + "," + d.target.x; });

function generateTree(width, height) {
  var cells = generateMaze(width, height), // each cell’s edge bits
      visited = d3.range(width * height).map(function() { return false; }),
      root = {index: cells.length - 1, children: []},
      frontier = [root],
      parent,
      child,
      childIndex,
      cell;

  while ((parent = frontier.pop()) != null) {
    cell = cells[parent.index];
    if (cell & E && !visited[childIndex = parent.index + 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & W && !visited[childIndex = parent.index - 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & S && !visited[childIndex = parent.index + width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
    if (cell & N && !visited[childIndex = parent.index - width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
  }

  return root;
}

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

</script>

## thumbnail.png

      
    Raw
  

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

	.link {
	fill: none;
	stroke: #000;
	stroke-width: 1.5px;
	}

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

	var margin = {top: 20, right: 20, bottom: 20, left: 20},
	width = 960 - margin.left - margin.right,
	height = 500 - margin.top - margin.bottom;

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

	var root = generateTree(40, 40);

	var tree = d3.layout.tree()
	.size([height, width]);

	var nodes = tree.nodes(root),
	links = tree.links(nodes);

	var svg = d3.select("body").append("svg")
	.attr("width", width + margin.left + margin.right)
	.attr("height", height + margin.top + margin.bottom)
	.append("g")
	.attr("transform", "translate(" + margin.left + "," + margin.top + ")");

	svg.selectAll(".link")
	.data(links)
	.enter().append("path")
	.attr("class", "link")
	.attr("d", function(d) { return "M" + d.source.y + "," + d.source.x + "L" + d.target.y + "," + d.target.x; });

	function generateTree(width, height) {
	var cells = generateMaze(width, height), // each cell’s edge bits
	visited = d3.range(width * height).map(function() { return false; }),
	root = {index: cells.length - 1, children: []},
	frontier = [root],
	parent,
	child,
	childIndex,
	cell;

	while ((parent = frontier.pop()) != null) {
	cell = cells[parent.index];
	if (cell & E && !visited[childIndex = parent.index + 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & W && !visited[childIndex = parent.index - 1]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & S && !visited[childIndex = parent.index + width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	if (cell & N && !visited[childIndex = parent.index - width]) visited[childIndex] = true, child = {index: childIndex, children: []}, parent.children.push(child), frontier.push(child);
	}

	return root;
	}

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

	</script>