Skip to content

Instantly share code, notes, and snippets.

@adilapapaya

adilapapaya/README.md

Forked from mbostock/.block
Last active August 29, 2015 14:01
Show Gist options
  • Save adilapapaya/82fe6e872d08294486ce to your computer and use it in GitHub Desktop.
Save adilapapaya/82fe6e872d08294486ce to your computer and use it in GitHub Desktop.
Download ZIP
Wilson's Algorithm (Forked from mbostock)
Raw
README.md
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
background: #000;
width:100%;
height:100%;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
(function(){
"use strict";
// size it according to the window dimensions
var width = window.innerWidth,
height = window.innerHeight;
var N = 1 << 0,
S = 1 << 1,
W = 1 << 2,
E = 1 << 3;
//larger cell size = less dense tree
var cellSize = 10,
cellSpacing = 10,
cellSum = cellSize + cellSpacing,
cellWidth = Math.floor((width - cellSpacing) / (cellSum)),
cellHeight = Math.floor((height - cellSpacing) / (cellSum)),
marginLeft = Math.floor((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2) + cellSpacing + cellSize / 2 + .5,
marginTop = Math.floor((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2) + cellSpacing + cellSize / 2 + .5,
root = generateTree(cellWidth, cellHeight); // each cell’s edge bits
width-=2*marginLeft;
height-=2*marginTop;
var tree = d3.layout.tree()
.size([height - 2 * marginTop, width - 2 * marginLeft]);
var nodes = tree.nodes(root),
links = tree.links(nodes);
var maxDepth = d3.max(nodes,function(d){ return d.depth; });
// red to blue color scheme
/*var color = d3.scale.linear()
.range(["red","steelblue"])
.domain([0,maxDepth])
.interpolate(d3.interpolateHcl);*/
// rainbow
function color(d){
return d3.hsl(d/maxDepth * 300 , 1, .5).toString();
}
var canvas = d3.select("body")
.append('div')
.append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
context.translate(marginLeft, marginTop);
context.strokeStyle = "#fff";
nodes.forEach(function(d) {
var i = d.index;
d.t = 0;
d[0] = (cellWidth - i % cellWidth - 1) * (cellSize + cellSpacing);
d[1] = (i / cellWidth | 0) * (cellSize + cellSpacing);
});
links.sort(function(a, b) {
return b.source.depth - a.source.depth;
});
d3.selectAll(nodes).transition()
.duration(1500)
.delay(function() { return this.depth * 10 + 500; })
.ease("quad-in-out")
.tween("position", function(d) {
var d = this, i = d3.interpolate([d[0], d[1]], [d.y, d.x]);
return function(t) { var p = i(t); d.t = t; d[0] = p[0]; d[1] = p[1]; };
});
d3.timer(function() {
context.clearRect(0, 0, width, height);
links.forEach(function(d) {
context.beginPath();
context.moveTo(d.source[0], d.source[1]);
context.lineTo(d.target[0], d.target[1]);
context.lineWidth = d.source.t + 1;
context.strokeStyle = color(d.target.depth);
context.stroke();
});
return !links[0].target.__transition__;
});
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment