###
NOTE: This module is being re-written. From now on version 1.0x will only be changed for bug fixes and maintenance. New features will be in the version 2.00-track. See the TODO file for more information. ###

Revision history:

0.01 Wed Apr 28 14:14:56 1999

• original version; created by h2xs 1.18

0.7     Tue Feb 8 16:51:03 2000
        - Many incremental changes, leading up to:
          1) Hash-style parameters to new()
          2) Inheritance in similarly-dimensioned classes.
             We now have Games::Maze, and Games::MazeFlat.
          3) Code re-organized as a result of inheritance -
             there are a lot more hidden member functions
             created from sniplets of code that cannot cross the
             package barrier.
          4) More efficient use of internal constants.  We
             no longer have separate constants for the direction
             and the wall in that direction.  Now one constant
             handles both the wall and the direction we face.
          5) "make test" has tests for the 48-bit rand() function.

0.8     Wed Apr 19 10:57:35 2000
        - Games::MazeFlat goes away.  There was no real reason
          beyond sentimentality to keep it.
        - The direction values for all mazes are now the same.  South,
          for example, is now 0x20 for all mazes, instead of being 0x08
          for square mazes, and 0x10 for hexagon mazes.  This is an
          obvious thing to do in retrospect, but way back when they were
          separate programs with separate constants.
        - This lets me move the contants and some more functions
          into the base class, which makes the reading of the hex
          dump easier.

0.9     Thu Oct 19 11:39:54 2000
        - The maze object is now created via a call to
          Games::Maze->new() only.  The child classes ::Rect and
          ::Hex are dealt with in new().  The user need not deal
          with it at all.

1.0     Wed Apr 24 13:27:19 2002
        - Hexagonal Hexagon mazes
        - Big changes in the stringifying functions, mostly by deleting
          code, and fixing up the border cells values.
        - The 'cols', 'rows', and 'lvls' parameters have been replaced by
          a single 'dimensions' parameter.
        - New parameter 'start' tells the make() method where to start
          the random walk from.
        - New parameter 'fn_choosedir' chooses which direction your random
          walk takes while making the maze.
        - New parameters 'entry' and 'exit' let you place the beginning
          and ending points.

1.01 Tue May 07 21:55:39 2002

• Bug fixes for bugs found by Pete Stewart. Having added the 'entry' and 'exit' parameters, the case where those parameters aren't used became broken.
• Fix to two of the test files involving an unintialized variable.
• Add a Northward entry to the cell with the entrance. Hadn't done that before because the printing routine to_ascii() didn't need it, but now that another module will be using this, i need to knock down the wall on both the border and maze cells.
• Added the unsolve() method.

1.02 Mon Jun 03 19:29:53 2002

• Documentation fixes as pointed out by David Hand.

1.03 Wed Feb 21 2007

• Some changes to the structure of the distribution directory in order to keep up with the current state of perl.
• Use Test::Simple for tests, Module::Build for buiding, and add a META.yml file.

HISTORY & BACKGROUND INFORMATION

The code started out as a fairly direct translation of the CDC Pascal source, which in turn was translated from the original CDC Fortran (well, MNF to be precise) program written back in 1978 or 1979.

The Algorithm

The algorithm is simple. The maze is considered to be an array of cells, each cell bounded by walls that are shared with its neighbor. The program starts with a random cell, and randomly 'walks' through a wall (knocking it down in the process) into a neighboring enclosed cell. If it reaches a dead end, it returns to a point where it can continue its random walk. When it runs out of enclosed cells to break into, the algorithm is done.

Solving

Since this process creates singly-connected mazes (that is, a maze where there is only one path between any two points), the solving method is straightforward. Go forward until either you reach the exit, or until you run into a wall. If you have run into a wall, turn to the next direction and walk forward. Repeat. Drop off or pick up path marks as you exit one cube for another.

A 'hand-on-wall' method of solving (not included in the packages) that you may have learned as a kid works, but only for the 2-dimensional mazes. Sadly, it will often wind up in an infinite loop when it is extended to the three-dimensional case. I suspect that for this solving algorithm to work, it would have to chose its next move based not only on the current wall, but the prior move's wall as well. I haven't bothered to test this, though. Since the go-forward method works so well with both 2- and 3-dimensional mazes, I haven't attempted to adapt the hand-on-wall methd.

Representing Hexagonal Mazes

Hexagonal mazes, as you may notice if you study the code, are simply rectangular mazes with a 'hexagonal drift'. That is,

hexagonal mesh square grid with 'hexagonal drift'

  1  2  3  4  5  6  7  8             1   2   3   4   5   6   7   8
  __    __    __    __              ___     ___     ___     ___    
 /  \__/  \__/  \__/  \__          |   |___|   |___|   |___|   |___
 \__/  \__/  \__/  \__/  \         |___|   |___|   |___|   |___|   |
 /  \__/  \__/  \__/  \__/         |   |___|   |___|   |___|   |___|
 \__/  \__/  \__/  \__/  \         |___|   |___|   |___|   |___|   |
 /  \__/  \__/  \__/  \__/         |   |___|   |___|   |___|   |___|
 \__/  \__/  \__/  \__/  \         |___|   |___|   |___|   |___|   |
 /  \__/  \__/  \__/  \__/         |   |___|   |___|   |___|   |___|
 \__/  \__/  \__/  \__/  \         |___|   |___|   |___|   |___|   |
    \__/  \__/  \__/  \__/             |___|   |___|   |___|   |___|

Moving the squares back in position gives us a basic 8x4 matrix, which is easy to represent in perl code. This leaves only the question of which six of the eight cells we can move to after choosing one of the six possible directions to go. There are two possible choices:

      _\|/_  or   __|__
        |          /|\

Which one we use depends upon whether we are in an up-shifted column or not.

Incidently, these are also the moves allowed to the opposing Gold General pieces in the game Shogi (a chess-like game from Japan). Coincidence? Well, probably, but it is interesting to contemplate.