Color Flood: Wilson's Algorithm | Hacker News Reader

Color Flood: Wilson's Algorithm

bl.ocks.org

111 pointsdsilver26 comments

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.

(This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599)

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:

http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s...

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:

http://bl.ocks.org/mbostock/11159599

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.

[1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...

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).

Here’s my version of this from last year: http://bl.ocks.org/robinhouston/6027749

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.

It's a colored version of this: https://en.wikipedia.org/wiki/Uniform_spanning_tree

Warning for the link to Prim's Algorithm: it's a beast and will make FF fairly unresponsive.

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.

Quick screencast: https://docs.google.com/file/d/0B4MGwWE_SNv0elNfUVdmalp5NVE

What version/OS are you on?

I'm running 29 (Aurora? Beta? Whatever it's called :)) on OS X and it's perfectly smooth, low CPU usage.

I've got the same problem with version 28.0 on Linux.

28, Linux

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.

http://updates.html5rocks.com/2011/12/Transferable-Objects-L...

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].

[1] http://people.renci.org/~borland/pdfs/RainbowColorMap_VisVie...

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.

[1] http://bl.ocks.org/mbostock/3014589

I'm not quite sure exactly what I'm looking at, but it looks cool as hell.

the point of Wilson's algorithm is that each spanning is equally likely.

Each tree is selected uniformly amoug the HUGE set of possible spanning trees of this graph.

The color patterns in this algorithm vs. Prim algorithm are very different. Unlike Prim algorithm, this pattern is random and has a fractal structure.

Is there a good reason a programmer might need each UST to be equally likely?

I've noticed it stops filling the canvas when I switch tabs, why is that?

This is beautiful. I want to hang it on my wall :)

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

Those labelled jumps are equivalent to common unlabeled continues, but safer.

The braceless do-whiles are isolated by blank lines and have leading comments.

I'd prefer bostock's code over the average uncommented code with cryptic abbreviated var names.

These would basically be "time for serious feedback" at any place I've worked in the last 25 years.

Seriously, the style is going to generate errors.

so bostock has gotten better, but there was a time (also known as when I did a lot of stuff with topojson and unraveled how it worked) where it looked like this https://github.com/mbostock/topojson/blob/fe691fc61c38a79b09...

Yep, I just a couple of hours messing around with it and got tripped up many times by this stuff.

Reply on news.ycombinator.com