From: Clifford Heath <no@...>
Date: 2005-05-13T09:05:29+09:00
Subject: Re: [SUMMARY] Amazing Mazes (#31)

Ruby Quiz wrote:
> Below, I want to look into Dominik Bathon's code.

Nicely coded, I enjoyed learning some Ruby tricks.

Unfortunately if you look at the mazes this algorithm generates,
you'll see a serious flaw. They always seem to "fan out" from
the start position - in other words there is not a random nature
to the shape of the paths away from the start position. It makes
the mazes much easier to solve. I made the same mistake when I
first wrote a maze generator.

The commonly accepted alternative method (which produces *random*
mazes) is to number every square with a distinct number 0..N, then
choose a random wall which divides two cells having different
numbers. Throughout the maze, change the higher number to the
lower number, and repeat until the whole maze is numbered 0. This
takes exactly N cycles.

The search for a random wall requires a circular search around the
maze from a randomly-chosen start position, until a suitable wall
is found.

Clifford Heath.