5 ms·

Maze Generation: Kruskal's Algorithm

42 points by ph0rque 16y ago

sqrt17 16y ago
In order to get the O(log(n)) runtime that you talk about, you need to take care that the Tree data structure doesn't devolve into a list, e.g. by keeping track of a child count and always putting the smaller tree as a child of the larger tree (see http://en.wikipedia.org/wiki/Disjoint-set_data_structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure) Discussing asymptotic behaviour is only useful if you're able to understand how your code needs to look to actually achieve it.
- jamis 16y ago
  Good point. I've removed the bit about O(log n), since aside from being misleading, it really wasn't even relevant to the point of the article.
- baddox 16y ago
  The disjoint set is one of my favorite data structures because the amortized running time of its basic operations is O(α(n)), α being the inverse of the Ackermann function. The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe), so its inverse grows extremely slowly. In fact, α(x) is less than 5 for "reasonable" values of x such as the number of atoms in the universe. Therefore, the amortized run time of the disjoint set operations can be thought of as essentially constant. Also of interest to me is that the inverse Ackermann function is proven to be the asymptotically optimal run time for the disjoint set operations. I'm not equipped to understand that particular proof of asymptotic optimality, but other such proofs (like the O(n lg n) running time for comparison sort) are elegant and awesome.
  - adrianN 16y ago
    > The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe) This is correct. It was basically invented to show that primitive recursion is not capable of computing every computable function.
cdr 16y ago
Previous maze discussion from Jamis's series: http://news.ycombinator.com/item?id=2048752 http://news.ycombinator.com/item?id=2048752
robinhouston 16y ago
I’m loving this series of articles. Here’s a simple (not very efficient) implementation you can play with, in both senses: http://s3.boskent.com/mazes/kruskal.html http://s3.boskent.com/mazes/kruskal.html
thamer 16y ago
Here is some Erlang code doing pretty much the same: https://github.com/nicolasff/mazes-erlang https://github.com/nicolasff/mazes-erlang And a sample output: http://i.imgur.com/uV4XR.png http://i.imgur.com/uV4XR.png I find that the Kruskal mazes often have long walls or large open spaces; they don't have those tricky dead-ends that you can find in newspaper mazes, for instance.
jules 16y ago
Are there efficient algorithms to generate uniformly random mazes? i.e. selects a maze randomly with uniform probability from the set of all valid mazes.
- jamis 16y ago
  http://www.astrolog.org/labyrnth/algrithm.htm#perfect http://www.astrolog.org/labyrnth/algrithm.htm#perfect says that both the Aldous-Broder and Wilson's algorithms will generate "all possible Mazes of a given size with equal probability". But neither meets your criteria of "efficient", since neither is even guaranteed to finish. I'm curious, too, whether there is an efficient algorithm with the same property (generate any valid maze with equal probability).

42 points by ph0rque 16y ago

In order to get the O(log(n)) runtime that you talk about, you need to take care that the Tree data structure doesn't devolve into a list, e.g. by keeping track of a child count and always putting the smaller tree as a child of the larger tree (see http://en.wikipedia.org/wiki/Disjoint-set_data_structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure) Discussing asymptotic behaviour is only useful if you're able to understand how your code needs to look to actually achieve it.

jamis 16y ago
Good point. I've removed the bit about O(log n), since aside from being misleading, it really wasn't even relevant to the point of the article.
baddox 16y ago
The disjoint set is one of my favorite data structures because the amortized running time of its basic operations is O(α(n)), α being the inverse of the Ackermann function. The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe), so its inverse grows extremely slowly. In fact, α(x) is less than 5 for "reasonable" values of x such as the number of atoms in the universe. Therefore, the amortized run time of the disjoint set operations can be thought of as essentially constant. Also of interest to me is that the inverse Ackermann function is proven to be the asymptotically optimal run time for the disjoint set operations. I'm not equipped to understand that particular proof of asymptotic optimality, but other such proofs (like the O(n lg n) running time for comparison sort) are elegant and awesome.
- adrianN 16y ago
  > The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe) This is correct. It was basically invented to show that primitive recursion is not capable of computing every computable function.

cdr 16y ago

Previous maze discussion from Jamis's series: http://news.ycombinator.com/item?id=2048752 http://news.ycombinator.com/item?id=2048752

robinhouston 16y ago

I’m loving this series of articles. Here’s a simple (not very efficient) implementation you can play with, in both senses: http://s3.boskent.com/mazes/kruskal.html http://s3.boskent.com/mazes/kruskal.html

thamer 16y ago

Here is some Erlang code doing pretty much the same: https://github.com/nicolasff/mazes-erlang https://github.com/nicolasff/mazes-erlang And a sample output: http://i.imgur.com/uV4XR.png http://i.imgur.com/uV4XR.png I find that the Kruskal mazes often have long walls or large open spaces; they don't have those tricky dead-ends that you can find in newspaper mazes, for instance.

jules 16y ago

Are there efficient algorithms to generate uniformly random mazes? i.e. selects a maze randomly with uniform probability from the set of all valid mazes.

jamis 16y ago
http://www.astrolog.org/labyrnth/algrithm.htm#perfect http://www.astrolog.org/labyrnth/algrithm.htm#perfect says that both the Aldous-Broder and Wilson's algorithms will generate "all possible Mazes of a given size with equal probability". But neither meets your criteria of "efficient", since neither is even guaranteed to finish. I'm curious, too, whether there is an efficient algorithm with the same property (generate any valid maze with equal probability).