Samuel Benge wrote:

> Care to give an overview of the algorithm?

I don't know what Robert used, but generating a maze was one of the
exercises in the introduction to computer science course I took way
back when I was young ;) There we were to apply a strategy called
union-find, a general way to manage disjoint partitions of sets.

The application here was to imagine a grid where each tile could
either be free or filled with a wall, and start out with a with a
"maze" consisting of completely disconnected rooms (or, in the
language of the data structure, one-element subsets).

######...
# # #
######...
# # #
######...
...

You can then randomly merge two rooms by removing a common wall,
if available. In the union-find structure they are replaced by a
two-element subset, so that basically manages the list of already
connected component. Repeat the process until only one subset is
left (this generates a maze where every two rooms are connected
by exactly one path).

Post a reply to this message