That code does NOT implement Prim's algorithm on a graph with randomly-weighted edges. Instead it just does a randomized breadth-first search of the area (starting from the corner), which is the same algorithm used for colouring, which is why the radial pattern occurs.
For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm.
I’d be happy if you could explain more, but the edges here are intentionally unweighted, so I believe the algorithm is correct. It’s based on the description here:
EDIT: Looks like you’re right! It makes a huge difference if you assign each edge a random weight once, rather than simply pulling a random edge of the frontier. Seems like the reference I used has this bug? Here is a fixed version:
Yeah, I'm pretty sure the site you linked is wrong too, and I think the author doesn't realize it, because he says:
> My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm.
But his implementation is NOT the same! (His implementation of Kruskal's algorithm does look correct.) Extracting elements at a random index is not equivalent to assigning random weights to elements and extracting the minimum-weight elements.
I spoke to Jamis Buck on Twitter. It’s called “Randomized Prim’s” on Wikipedia [1], but of course Wikipedia is not authoritative. It does seem confusing to call it a variant of Prim’s given how different the behavior is.
I see -- apparently it's common to call this "Prim's algorithm" even though it is more accurately described as a randomized variant of breadth/depth-first search. Thanks for clarifying that.
I do still object to the text reading "This article is about using another minimal spanning tree algorithm to do the same" -- what is described there is not a minimal spanning tree algorithm (even if it's called Prim's algorithm).
I love mike bostock's stuff, but his code often makes me feel sorry for whoever has to deal with his code after him
// Pick a location that’s not yet in the maze (if any).
do if ((index0 = remaining.pop()) == null) return true;
while (cells[index0] >= 0);
// Perform a random walk starting at this location,
previous[index0] = index0;
walk: while (true) {
i = index0 % width;
j = index0 / width | 0;
// picking a legal random direction at each step.
direction = Math.random() * 4 | 0;
if (direction === 0) { if (j <= 0) continue walk; --j; }
else if (direction === 1) { if (j >= height - 1) continue walk; ++j; }
else if (direction === 2) { if (i <= 0) continue walk; --i; }
else { if (i >= width - 1) continue walk; ++i; }
note the braceless do while and the labeled jump statements
Weird. It's super smooth even in the Android WebKit control embedded in the HN app on Android 4.4.2.
It's been a long time since I switched to Chromium but I really thought Firefox got faster by now.
Looks cool. The article could use a bit more explanation of what exactly I'm looking at.
Is this is a flood-fill algorithm?
Cause what I remember from back in the day when you could still watch MS Paint do the flood fill, a more efficient version fills out horizontal spans all at once, instead of growing like an ink blot.
But it looks cool.
EDIT: maybe this is one of those "use the entire RGB colour space" type of renderings? (see http://allrgb.com )
It's mostly a visualisation of the tree underlying the colours, I'd say. The pixels of the canvas form a grid, and a spanning tree is created for this graph. A spanning tree contains all nodes of a graph, but only a subset of the edges. A tree is a graph that does not contain any cycles.
You could use an transferable typed array buffer instead of copying an array of integers from the worker thread. Looks like the array is under 4mb, so copying doesn't take very long, and you only do it once, but if you're going to use a worker you might as well.
It would be cool to visualize the depth with a colormap that makes it visually possible to compare depths, e.g. Matlab's Hot. HSV colormaps are pretty but make direct visual comparisons difficult [1].
Yes, this is not intended to be a visualization; it is merely something pretty. D3 supports Lab and HCL color spaces [1] which are perceptually uniform; I could use those to improve the accuracy of the distance encoding, but I’d have to sacrifice the current garish aesthetic.
For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm.
(This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599)