jamis

# Easy to use:
#
#   timer = LapTimer.new
#   # some task that might take awhile
#   timer.mark :step2
#   # another task that needs timing
#   timer.mark :step3
#   # and another task to time
#   timer.report
#

jamis

###########################################################################
# cube-maze.rb
# by Jamis Buck ([email protected])
# -------------------------------------------------------------------------
# This script generates a PNG image of all six faces of a cube, covered
# with the passages of a maze that wraps across all the faces.
#
# The movements between faces are computed using the WRAPS constant, which
# tells which face lies in each direction from any given face, as well as
# how the coordinates should be transformed when moving from face to face.

jamis

# --------------------------------------------------------------------
# An implementation of a "weave" maze generator. Weave mazes are those
# with passages that pass both over and under other passages. The
# technique used in this program was described to me by Robin Houston,
# and works by first decorating the blank grid with the over/under
# crossings, and then using Kruskal's algorithm to fill out the rest
# of the grid. (Kruskal's is very well-suited to this approach, since
# it treats the cells as separate sets and joins them together.)
# --------------------------------------------------------------------
# NOTE: the display routine used in this script requires a terminal

jamis

# --------------------------------------------------------------------
# An implementation of a "weave" maze generator. Weave mazes are those
# with passages that pass both over and under other passages. The
# technique used in this program was described to me by Robin Houston,
# and works by first decorating the blank grid with the over/under
# crossings, and then using Kruskal's algorithm to fill out the rest
# of the grid. (Kruskal's is very well-suited to this approach, since
# it treats the cells as separate sets and joins them together.)
# --------------------------------------------------------------------
# NOTE: the display routine used in this script requires a terminal

jamis

# --------------------------------------------------------------------
# An implementation of a "weave" maze (with over/under passages),
# using the Growing Tree maze generation algorithm.
# --------------------------------------------------------------------

# --------------------------------------------------------------------
# Helper data and methods
# --------------------------------------------------------------------

N, S, E, W, U = 0x01, 0x02, 0x04, 0x08, 0x10

jamis

# --------------------------------------------------------------------
# An implementation of the Sidewinder algorithm for maze generation.
# This algorithm is kind of a cross between the trivial Binary Tree
# algorithm, and Eller's algorithm. Like the Binary Tree algorithm,
# the result is biased (but not as heavily).
#
# Because the Sidewinder algorithm only needs to consider the current
# row, it can be used (like the Binary Tree and Eller's algorithms)
# to generate infinitely large mazes.
# --------------------------------------------------------------------

jamis

# --------------------------------------------------------------------
# An implementation of the "Binary Tree" algorithm. This is perhaps
# the simplest of the maze generation algorithms to implement, and the
# fastest to run, but it creates heavily biased mazes.
#
# It is novel in that it can operate without any state at all; it only
# needs to look at the current cell, without regard for the rest of
# the maze (or even the rest of the row). Thus, like Eller's algorithm
# it can be used to generate mazes of infinite size.
# --------------------------------------------------------------------

jamis

# --------------------------------------------------------------------
# An implementation of the "Recursive Division" algorithm. This is a
# kind of fractal maze algorithm, recursively dividing the maze into
# smaller and smaller cells. This algorithm stops at the integer
# boundary, but theoretically the algorithm could continue infinitely
# to smaller and smaller scales.
#
# Note that this algorithm is implemented as a "wall adder", rather
# than a "passage carver", so the meaning of the bits in each cell
# is reversed: instead of the S bit (for instance) meaning "a passage

jamis

# --------------------------------------------------------------------
# An implementation of the "Growing Tree" algorithm. This one is
# notable for it's ability to become nearly identical to Prim's
# algorithm, or the Recursive Backtracking algorithm, depending on
# how the cells are removed from the list that aggregates as the
# algorithm runs.
#
# This script allows you to play with those settings by specifying
# the mode after the width and height parameters, as "random" (pull
# the cell from list at random), "newest" (pull the newest cell),

jamis

# --------------------------------------------------------------------
# An implementation of the "Hunt and Kill" algorithm. This is fairly
# similar to the recursive backtracking algorithm, except that there
# is no recursion, and it doesn't backtrack. :) The algorithm can
# get a little slow towards the end, where the "hunt" phase has to
# search over nearly the entire field to find a candidate cell, but
# it's guaranteed to finish (unlike Aldous-Broder and Wilson's), and
# it's still pretty fast.
# --------------------------------------------------------------------