Color Flood: Wilson's Algorithm

Color Flood: Wilson's Algorithm(bl.ocks.org)

111 points by dsilver 12 years ago | 26 comments

sltkr 12 years ago |

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)

mbostock 12 years ago | |

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

sltkr 12 years ago | | |

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.

robinhouston 12 years ago |

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

tripzilch 12 years ago |

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 )

morsch 12 years ago | |

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.

thomasahle 12 years ago | |

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

nly 12 years ago |

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

ne0phyte 12 years ago | |

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

notjosh 12 years ago | |

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.

ema 12 years ago | | |

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

nly 12 years ago | | |

28, Linux

tantalor 12 years ago |

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

santaclaus 12 years ago |

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

mbostock 12 years ago | |

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

rectangletangle 12 years ago |

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

mrcactu5 12 years ago |

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?

hcarvalhoalves 12 years ago |

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

goshx 12 years ago |

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

cwmma 12 years ago |

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

judk 12 years ago | |

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.

kabdib 12 years ago | | |

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.

cwmma 12 years ago | | |

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

IneffablePigeon 12 years ago | |

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

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