Maze Generation: Kruskal's Algorithm | Hacker News Reader

Maze Generation: Kruskal's Algorithm

weblog.jamisbuck.org

42 pointsph0rque9 comments

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)

Discussing asymptotic behaviour is only useful if you're able to understand how your code needs to look to actually achieve it.

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.

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

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.

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

Here is some Erlang code doing pretty much the same: https://github.com/nicolasff/mazes-erlang

And a sample output: 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.

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.

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

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

Reply on news.ycombinator.com