Color Flood: Wilson's Algorithm

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)

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 )

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

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

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