Glenn M. Lewis wrote:
>     Could you please elaborate?

It's been quite a while since I did this stuff, but I do recall
solving the problem, and only afterwards finding some other
work that reflected the same solution.

It'd be very cool to do this again in Ruby with OpenGL :-))).

The idea is to start as Dominik did, with a maze having all
walls intact - every cell has two intact walls so it's closed
from every other cell. Every cell is numbered, say top-left
to bottom-right, 0..(W*H-1). This number is known as the
domain number, and every cell bearing a certain number is
defined to be reachable from any cell in that domain.

Whenever you break a wall separating two distinct domains,
you join them into one domain, because any cell in either
domain can now reach any cell in the other domain. So to keep
things intact, you must eliminate one domain by changing all
occurrences of that number to the other one. I always eliminate
the higher numbered one, so the maze ends up as one domain
numbered zero.

Whenever you consider a wall you might want to break, check
the domain numbers on either side. If they're the same, there
is already a path between the two cells, and breaking this wall
will make a duplicate path - which is not what you want. If
they're different however, there is no path between the two
cells and it's ok to break this wall, eliminating one of the
two domains.

The only remaining task is to find an efficient and random
search for a wall to break. The easiest way is to choose a
cell at random, check both walls (in random order), and if
that wall divides two domains, break it. If not, consider
the next cell (circular search) until you find a wall you can
break.

Because you have W*H cells, there are initially that many domains,
and because every break reduces the domain count by one, you must
break exactly W*H-1 walls to get to a maze where every cell is
reachable from every other.

I set my son the challenge of doing this in three dimensions,
and we arranged things so the ladders (=broken floors) were
much less numerous than the horizontal connections. You can
do this simply by skewing the random number generator that
chooses which wall to break. If it tries the north wall 45%
of the time, the east wall 45%, and the floor only 10%, you
get the desired outcome.

Similarly in a 2-D maze, you can skew the generation so that
more of the paths are E-W rather than N-S.

Then we created a 3-D perspective view looking in from near one
corner between two layers, so you can see all the passages, the
ladders climbing up to the layer above, and the manholes where
ladders appear from below, so you can wander around the maze at
will. We even animated the ladder climbing using double
buffering, moving the camera up past the floor to the next floor.
All in Turbo-Pascal for a year 10 assignment :-). My son solved
a 20x20x20 maze in about 10 minutes, much to his teacher's
astonishment - he has an amazing visual memory.

I used to print him 2-D mazes with a 1/8" cell size, full page on
letter paper - perhaps 60x80 in size. When he was four years old,
he complained that he needed some new ones, and my wife pointed
out that he had a stack of sixty that were unmarked. He quickly
went through the stack, pointing to the solution on each one. He
had not only solved them all by eye, but he recognised each one
and remembered its solution! Scary...

Clifford Heath.