The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Games-Maze-1.01
River stage one • 2 direct dependents • 2 total dependents
++

Changes for version 1.01 - 2002-05-07

  • 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.
  • 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.

Modules

Games::Maze
Create Mazes as Objects.

Provides

Games::Maze::Hex
in Maze.pm
Games::Maze::Quad
in Maze.pm

Other files