21–27 of 27 posts
http://updates.html5rocks.com/2011/12/Transferable-Objects-L...
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…
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 use…
> 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.
Earlier quoted context omitted.
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 use…
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…
[1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...
Earlier quoted context omitted.
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…
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 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 r…
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.