Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active February 9, 2016 01:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mbostock/a1acb68314187458a244 to your computer and use it in GitHub Desktop.
Save mbostock/a1acb68314187458a244 to your computer and use it in GitHub Desktop.
Download ZIP
Prim’s Algorithm IV
Raw
.block
license: gpl-3.0
Raw
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),
frontier = minHeap(function(a, b) { return a.weight - b.weight; }),
startIndex = (height - 1) * width;
cells[startIndex] = 0;
frontier.push({index: startIndex, direction: N, weight: Math.random()});
frontier.push({index: startIndex, direction: E, weight: Math.random()});
while ((edge = frontier.pop()) != null) {
var edge,
i0 = edge.index,
d0 = edge.direction,
i1 = i0 + (d0 === N ? -width : d0 === S ? width : d0 === W ? -1 : +1),
x0 = i0 % width,
y0 = i0 / width | 0,
x1,
y1,
d1,
open = cells[i1] == null; // opposite not yet part of the maze
if (d0 === N) x1 = x0, y1 = y0 - 1, d1 = S;
else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
else x1 = x0 + 1, y1 = y0, d1 = W;
if (open) {
cells[i0] |= d0, cells[i1] |= d1;
if (y1 > 0 && cells[i1 - width] == null) frontier.push({index: i1, direction: N, weight: Math.random()});
if (y1 < height - 1 && cells[i1 + width] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
if (x1 < width - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E, weight: Math.random()});
}
}
return cells;
function minHeap(compare) {
var heap = {},
array = [],
size = 0;
heap.empty = function() {
return !size;
};
heap.push = function(value) {
up(array[size] = value, size++);
return size;
};
heap.pop = function() {
if (size <= 0) return;
var removed = array[0], value;
if (--size > 0) value = array[size], down(array[0] = value, 0);
return removed;
};
function up(value, i) {
while (i > 0) {
var j = ((i + 1) >> 1) - 1,
parent = array[j];
if (compare(value, parent) >= 0) break;
array[i] = parent;
array[i = j] = value;
}
}
function down(value, i) {
while (true) {
var r = (i + 1) << 1,
l = r - 1,
j = i,
child = array[j];
if (l < size && compare(array[l], child) < 0) child = array[j = l];
if (r < size && compare(array[r], child) < 0) child = array[j = r];
if (j === i) break;
array[i] = child;
array[i = j] = value;
}
}
return heap;
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment