Labyrinth Generator
Christian Ernst Rysgaard
Senior System Developer Consultant
Software Research Department, SimCorp A/S
Created June 19, 2000
Click to get the source files for this article
Introduction
This small program is used for generating a labyrinth with exactly one
solution. It was developed in Visual Basic and can be reused as you may wish. If
the algorithm and program actually works it was developed by Christian Ernst
Rysgaard, Software Research Department, SimCorp A/S, Denmark in June 2000 for
the Danish MSDN developer labyrinth contest
summer 2000. Otherwise I have no clue about who made it or even why.
The source files also includes
a solution using the same algorithm written in clean C with a
commandline interface. However speedier it does not beat the VB version in
readability. All maze operations are done using standard clib string functions -
a rather cunning and speedy solution but it obviously obscures any attempt to
grasp the mere outline of the algorithm.
Share and Enjoy!
User interface
The user interface is quite simple:
- Resize the form to adjust the height and width of the labyrinth
(dimension shown in caption)
- Press Generate to start generation of the labyrinth
- Press Solve to find the solution of the labyrinth (only enabled
after successful generation)
- Rightclick on the labyrinth to display the popup menu
The popup menu contains these functions:
- Redraw will redraw the labyrinth and remove any unused paths display
during Solve animation
- Use the "Show VRML" function to generate a VRML view of
the Labyrinth.
- Cellsize can be used to change the size of the cells in the
labyrinth
- Animation pause controls the pausing interval during animation
- Press Help to display this HTML file
The labyrinth is shown with the following legends:
- Blue cells are walls
- White cells are paths
- The green cell is the starting point
- The red cell is the end point
- Yellow cells are the path through the labyrinth
- Grey cells are cells tested and found not to be part of the path
|
 |
Please notice:
- Holding down the Shift key during Solve and Generate will improve speed by
disabling screen updating
- Pressing the Escape key during Generate or Solve will halt the process and
return command to the user.
- During the Solve process some cells are coloured grey as they are found
not to be part of the path.
- The VRML display of the labyrinth will only work if you have installed a
VRML viewer, otherwise the VRML source will be shown in Internet
Explorer.
The program has been tested on the following systems:
- Windows 2000 with VB6SP3 and IE5.01
- Windows NT4 SP5 with VB6SP3 and IE4.01
Algorithm
The program uses the following algorithm to generate a labyrinth.
- Fill the entire labyrinth with walls
- Find a random beginning position, store it as a possible position
and make it the current position
- Mark the current position as a path in the labyrinth and remove it from
the list of possible positions
- Remove surrounding positions invalidated by the current position from the
list of possible positions
- Add left, right, upper and lower cell positions created by the newly used
position to the list of possible positions
- If more possible positions are left then get the next random possible
position and restart from point 3
Example
The following table briefly shows the steps involved in four iterations of
the above algorithm (X = Wall, ? = Possible position, + = Selected position)
| 1 |
2 |
3 |
4 |
5 |
6 |
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX?XXX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX XXX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX XXX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XXX?XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XXX+XXX
XXXXXXX
XXXXXXX
|
| |
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XXX XXX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XX? ?XX
XXX?XXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XX? ?XX
XXX+XXX
XXXXXXX
|
| |
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XX? ?XX
XXX XXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XXX XXX
XXX XXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX? ?XX
XX? ?XX
XX? ?XX
XXX?XXX
|
XXXXXXX
XXXXXXX
XXX?XXX
XX+ ?XX
XX? ?XX
XX? ?XX
XXX?XXX
|
| |
|
XXXXXXX
XXXXXXX
XXX?XXX
XX ?XX
XX? ?XX
XX? ?XX
XXX?XXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XX ?XX
XXX ?XX
XX? ?XX
XXX?XXX
|
XXXXXXX
XXXXXXX
XX??XXX
X? ?XX
XXX ?XX
XX? ?XX
XXX?XXX
|
XXXXXXX
XXXXXXX
XX??XXX
X? ?XX
XXX ?XX
XX? +XX
XXX?XXX
|
As seen from the above algorithm, the two important parts are: the list of
possible positions and position validation.
List of possible positions
Think of it as a list of positions within the labyrinth that might be used as
a path. Once a possible position is turned into a path in the labyrinth some of
the surrounding possible positions might become invalid. That's why the
algorithm after selecting a random one from the list, removes all those
invalidated by the new position and then adds all extra positions created by the
new position. By constantly maintaining the list of possible positions instead
of rebuilding it for every iteration, the program adds extra speed to the
generation.
Position validation
The program uses the following algorithm to obtain all the possible positions
:
- Start in a new blank cell
- check left, right, up, down for non-blank cells
- check area left of the left cell: cells relative left, leftup, leftdown,
leftleft, leftleftup and leftleftdown must be walls
- check area right of the right cell: cells relative right, rightup,
rightdown, rightright, rightrightup and rightrightdown must be walls
- check area above the upper cell: cells relative up, upleft upright, upup,
upupleft and upupright must be walls
- check area below the lower cell: cells relative down, downleft, downright,
downdown, downdownleft and downdownright must be walls.
Each of the cells in steps 3 to 6 that are nonblank and complies with the
rules specified will be added as possible positions.
Example
The following example displays the validation of positions from a specific
position: (X=Wall, Space=Path, +=Current position, ?=Possible position):
| Current |
Up |
Right |
Left |
Down |
Result |
XXXXXXX
XXXXXXX
XXXXXXX
XXX +XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX +XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX +XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX +XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXXXXX
XXX +XX
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXXX?XX
XXX +?X
XXX XXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XXX+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XXX+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XXX+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XXX+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XXX+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXX X
XX?+X X
XXX X X
XXX X
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXXXXXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
XXXXXXX
XXX?XXX
XXX+XXX
XX XX
XXXXXXX
XXXXXXX
XXXXXXX
|
(The red colour is used to mark the area of interest.)
Seen from the above examples it is easy to deduce that new possible positions
will only pop up in the cases where the red area is completely filled with walls
(X's)
During documentation and test I have discovered that the cell validation
function misses some possible cells on the boundary of the labyrinth. Cells
starting horizontally from a clean cell on the vertical bound (and vice versa)
will be disregarded only based on their coordinates. The solution is obviously
to correct the error but this will severely obscure the readability of the
function (ok, I admit it - I couldn't locate the damn bug)!
Send feedback on
this article.