class Theseus::Maze

Theseus::Maze is an abstract class, intended to act solely as a superclass for specific maze types. Subclasses include OrthogonalMaze, DeltaMaze, SigmaMaze, and UpsilonMaze.

Each cell in the maze is a bitfield. The bits that are set indicate which passages exist leading AWAY from this cell. Bits in the low byte (corresponding to the PRIMARY bitmask) represent passages on the normal plane. Bits in the high byte (corresponding to the UNDER bitmask) represent passages that are passing under this cell. (Under/over passages are controlled via the weave setting, and are not supported by all maze types.)

Constants

E
N
NE
NW
PRIMARY

bitmask identifying directional bits on the primary plane

RESERVED

bits reserved for use by individual algorithm implementations

S
SE
SW
UNDER

bitmask identifying directional bits under the primary plane

UNDER_SHIFT

The size of the PRIMARY bitmask (e.g. how far to the left the UNDER bitmask is shifted).

W

Attributes

algorithm[R]

The algorithm object used to generate this maze. Defaults to an instance of Algorithms::RecursiveBacktracker.

braid[R]

An integer between 0 and 100 (inclusive), signifying the percentage of deadends in the maze that will be extended in some direction until they join with an existing passage. This will create loops in the graph. Thus, 0 is a “perfect” maze (with no loops), and 100 is a maze that is totally multiply-connected, with no dead-ends.

entrance[R]

A 2-tuple (array) indicating the x and y coordinates where the maze should be entered. This is used primarly when generating the solution to the maze, and generally defaults to the upper-left corner.

exit[R]

A 2-tuple (array) indicating the x and y coordinates where the maze should be exited. This is used primarly when generating the solution to the maze, and generally defaults to the lower-right corner.

height[R]

The height of the maze (number of rows).

mask[R]

A Theseus::Mask (or similar) instance, that is used by the algorithm to determine which cells in the space are allowed. This lets you create mazes that fill shapes, or flow around patterns.

randomness[R]

An integer between 0 and 100 (inclusive). 0 means passages will only change direction when they encounter a barrier they cannot move through (or under). 100 means that as passages are built, a new direction will always be randomly chosen for each step of the algorithm.

symmetry[R]

One of :none, :x, :y, :xy, or :radial. Note that not all maze types support symmetry. The :x symmetry means the maze will be mirrored across the x axis. Similarly, :y symmetry means the maze will be mirrored across the y axis. :xy symmetry causes the maze to be mirrored across both axes, and :radial symmetry causes the maze to be mirrored radially about the center of the maze.

weave[R]

An integer between 0 and 100 (inclusive). 0 means passages will never move over or under existing passages. 100 means whenever possible, passages will move over or under existing passages. Note that not all maze types support weaving.

width[R]

The width of the maze (number of columns).

In general, it is safest to use the row_length method for a particular row, since it is theoretically possible for a maze subclass to describe a different width for each row.

wrap[R]

One of :none, :x, :y, or :xy, indicating which boundaries the maze should wrap around. The default is :none, indicating no wrapping. If :x, the maze will wrap around the left and right edges. If :y, the maze will wrap around the top and bottom edges. If :xy, the maze will wrap around both edges.

A maze that wraps in a single direction may be mapped onto a cylinder. A maze that wraps in both x and y may be mapped onto a torus.

Public Class Methods

generate(options={}) click to toggle source

A short-hand method for creating a new maze object and causing it to be generated, in one step. Returns the newly generated maze.

# File lib/theseus/maze.rb, line 107
def self.generate(options={})
  new(options).generate!
end
new(options={}) click to toggle source

Creates and returns a new maze object. Note that the maze will not be generated; the maze is initially blank.

Many options are supported:

:width

The number of columns in the maze. Note that different maze types count columns and rows differently; you'll want to see individual maze types for more info.

:height

The number of rows in the maze.

:algorithm

The maze algorithm to use. This should be a class, adhering to the interface described by Theseus::Algorithms::Base. It defaults to Theseus::Algorithms::RecursiveBacktracker.

:symmetry

The symmetry to be used when generating the maze. This defaults to :none, but may also be :x (to have the maze mirrored across the x-axis), :y (to mirror the maze across the y-axis), :xy (to mirror across both axes simultaneously), and :radial (to mirror the maze radially about the center). Some symmetry types may result in loops being added to the maze, regardless of the braid value (see the :braid parameter). (NOTE: not all maze types support symmetry equally.)

:randomness

An integer between 0 and 100 (inclusive) indicating how randomly the maze is generated. A 0 means that the maze passages will prefer to go straight whenever possible. A 100 means the passages will choose random directions as often as possible.

:mask

An instance of Theseus::Mask (or something that acts similarly). This can be used to constrain the maze so that it fills or avoids specific areas, so that shapes and patterns can be made. (NOTE: not all algorithms support masks.)

:weave

An integer between 0 and 100 (inclusive) indicating how frequently passages move under or over other passages. A 0 means the passages will never move over/under other passages, while a 100 means they will do so as often as possible. (NOTE: not all maze types and algorithms support weaving.)

:braid

An integer between 0 and 100 (inclusive) representing the percentage of dead-ends that should be removed after the maze has been generated. Dead-ends are removed by extending them in some direction until they join with another passage. This will introduce loops into the maze, making it “multiply-connected”. A braid value of 0 will always result in a “perfect” maze (with no loops), while a value of 100 will result in a maze with no dead-ends.

:wrap

Indicates which edges of the maze should wrap around. :x will cause the left and right edges to wrap, and :y will cause the top and bottom edges to wrap. You can specify :xy to wrap both left-to-right and top-to-bottom. The default is :none (for no wrapping).

:entrance

A 2-tuple indicating from where the maze is entered. By default, the maze's entrance will be the upper-left-most point. Note that it may lie outside the bounds of the maze by one cell (e.g. [-1,0]), indicating that the entrance is on the very edge of the maze.

:exit

A 2-tuple indicating from where the maze is exited. By default, the maze's entrance will be the lower-right-most point. Note that it may lie outside the bounds of the maze by one cell (e.g. [width,height-1]), indicating that the exit is on the very edge of the maze.

:prebuilt

Sometimes, you may want the new maze to be considered to be generated, but not actually have anything generated into it. You can set the :prebuilt parameter to true in this case, allowing you to then set the contents of the maze by hand, using the []= method.

# File lib/theseus/maze.rb, line 176
def initialize(options={})
  @deadends = nil

  @width = (options[:width] || 10).to_i
  @height = (options[:height] || 10).to_i

  @symmetry = (options[:symmetry] || :none).to_sym
  configure_symmetry

  @randomness = options[:randomness] || 100
  @mask = options[:mask] || TransparentMask.new
  @weave = options[:weave].to_i
  @braid = options[:braid].to_i
  @wrap = options[:wrap] || :none

  @cells = setup_grid or raise "expected #setup_grid to return the new grid"

  @entrance = options[:entrance] || default_entrance
  @exit = options[:exit] || default_exit

  algorithm_class = options[:algorithm] || Algorithms::RecursiveBacktracker
  @algorithm = algorithm_class.new(self, options)

  @generated = options[:prebuilt]
end

Public Instance Methods

[](x,y) click to toggle source

Returns the bitfield for the cell at the given (x,y) coordinate.

# File lib/theseus/maze.rb, line 257
def [](x,y)
  @cells[y][x]
end
[]=(x,y,value) click to toggle source

Sets the bitfield for the cell at the given (x,y) coordinate.

# File lib/theseus/maze.rb, line 262
def []=(x,y,value)
  @cells[y][x] = value
end
add_opening_from(point) click to toggle source

If point is already located at a valid point within the maze, this does nothing. Otherwise, it examines the potential exits from the given point and looks for the first one that leads immediately to a valid point internal to the maze. When it finds one, it adds a passage to that cell leading to point. If no such adjacent cell exists, this method silently does nothing.

# File lib/theseus/maze.rb, line 538
def add_opening_from(point)
  x, y = point
  if valid?(x, y)
    # nothing to be done
  else
    potential_exits_at(x, y).each do |direction|
      nx, ny = move(x, y, direction)
      if valid?(nx, ny)
        @cells[ny][nx] |= opposite(direction)
        return
      end
    end
  end
end
adjacent_point(point) click to toggle source

If point is already located at a valid point withint he maze, this simply returns point. Otherwise, it examines the potential exits from the given point and looks for the first one that leads immediately to a valid point internal to the maze. When it finds one, it returns that point. If no such point exists, it returns nil.

# File lib/theseus/maze.rb, line 558
def adjacent_point(point)
  x, y = point
  if valid?(x, y)
    point
  else
    potential_exits_at(x, y).each do |direction|
      nx, ny = move(x, y, direction)
      return [nx, ny] if valid?(nx, ny)
    end
  end
end
apply_move_at(x, y, direction) click to toggle source

Applies a move in the given direction to the cell at (x,y). The direction parameter may also be :under, in which case the cell is left-shifted so as to move the existing passages to the UNDER plane.

This method also handles the application of symmetrical moves, in the case where symmetry has been specified.

You'll generally never call this method directly, except to construct grids yourself.

# File lib/theseus/maze.rb, line 622
def apply_move_at(x, y, direction)
  if direction == :under
    @cells[y][x] <<= UNDER_SHIFT
  else
    @cells[y][x] |= direction
  end

  case @symmetry
  when :x      then move_symmetrically_in_x(x, y, direction)
  when :y      then move_symmetrically_in_y(x, y, direction)
  when :xy     then move_symmetrically_in_xy(x, y, direction)
  when :radial then move_symmetrically_radially(x, y, direction)
  end
end
clockwise(direction) click to toggle source

Returns the direction that results by rotating the given direction 90 degrees in the clockwise direction. This will work even if the direction value is in the UNDER bitmask.

# File lib/theseus/maze.rb, line 460
def clockwise(direction)
  if direction & UNDER != 0
    clockwise(direction >> UNDER_SHIFT) << UNDER_SHIFT
  else
    case direction
    when N  then E
    when E  then S
    when S  then W
    when W  then N
    when NW then NE
    when NE then SE
    when SE then SW
    when SW then NW
    end
  end
end
counter_clockwise(direction) click to toggle source

Returns the direction that results by rotating the given direction 90 degrees in the counter-clockwise direction. This will work even if the direction value is in the UNDER bitmask.

# File lib/theseus/maze.rb, line 480
def counter_clockwise(direction)
  if direction & UNDER != 0
    counter_clockwise(direction >> UNDER_SHIFT) << UNDER_SHIFT
  else
    case direction
    when N  then W
    when W  then S
    when S  then E
    when E  then N
    when NW then SW
    when SW then SE
    when SE then NE
    when NE then NW
    end
  end
end
dead?(cell) click to toggle source

Returns true if the given cell is a dead-end. This considers only passages on the PRIMARY plane (the UNDER bits are ignored, because the current algorithm for generating mazes will never result in a dead-end that is underneath another passage).

# File lib/theseus/maze.rb, line 526
def dead?(cell)
  raw = cell & PRIMARY
  raw == N || raw == S || raw == E || raw == W ||
    raw == NE || raw == NW || raw == SE || raw == SW
end
dead_ends() click to toggle source

Returns a array of all dead-ends in the maze. Each element of the array is a 2-tuple containing the coordinates of a dead-end.

# File lib/theseus/maze.rb, line 365
def dead_ends
  dead_ends = []

  @cells.each_with_index do |row, y|
    row.each_with_index do |cell, x|
      dead_ends << [x, y] if dead?(cell)
    end
  end

  dead_ends
end
dx(direction) click to toggle source

Returns the change in x implied by the given direction.

# File lib/theseus/maze.rb, line 498
def dx(direction)
  case direction
  when E, NE, SE then 1
  when W, NW, SW then -1
  else 0
  end
end
dy(direction) click to toggle source

Returns the change in y implied by the given direction.

# File lib/theseus/maze.rb, line 507
def dy(direction)
  case direction
  when S, SE, SW then 1
  when N, NE, NW then -1
  else 0
  end
end
finish() click to toggle source

Since exit may be external to the maze, finish returns the cell adjacent to exit that lies within the maze. If exit is already internal to the maze, this method returns exit. If exit is not adjacent to any internal cell, this method returns nil.

# File lib/theseus/maze.rb, line 304
def finish
  adjacent_point(@exit)
end
generate!() { || ... } click to toggle source

Generates the maze if it has not already been generated. This is essentially the same as calling step repeatedly. If a block is given, it will be called after each step.

# File lib/theseus/maze.rb, line 205
def generate!
  yield if block_given? while step unless generated?
  self
end
generated?() click to toggle source

Returns true if the maze has been generated.

# File lib/theseus/maze.rb, line 288
def generated?
  @generated
end
hmirror(direction) click to toggle source

Returns the direction that is the horizontal mirror to the given direction. This will work even if the direction value is in the UNDER bitmask.

# File lib/theseus/maze.rb, line 423
def hmirror(direction)
  if direction & UNDER != 0
    hmirror(direction >> UNDER_SHIFT) << UNDER_SHIFT
  else
    case direction
    when E  then W
    when W  then E
    when NW then NE
    when NE then NW
    when SW then SE
    when SE then SW
    else direction
    end
  end
end
move(x, y, direction) click to toggle source

Moves the given (x,y) coordinates a single step in the given direction. If wrapping in either x or y is active, the result will be mapped to the maze's current bounds via modulo arithmetic. The resulting coordinates are returned as a 2-tuple.

Example:

x2, y2 = maze.move(x, y, Maze::W)
# File lib/theseus/maze.rb, line 354
def move(x, y, direction)
  nx, ny = x + dx(direction), y + dy(direction)

  ny %= height if wrap_y?
  nx %= row_length(ny) if wrap_x? && ny > 0 && ny < height

  [nx, ny]
end
new_path(meta={}) click to toggle source

Creates a new Theseus::Path object based on this maze instance. This can be used to (for instance) create special areas of the maze or routes through the maze that you want to color specially. The following demonstrates setting a particular cell in the maze to a light-purple color:

path = maze.new_path(color: 0xff7fffff)
path.set([5,5])
maze.to(:png, paths: [path])
# File lib/theseus/maze.rb, line 218
def new_path(meta={})
  Path.new(self, meta)
end
new_solver(options={}) click to toggle source

Instantiates and returns a new solver instance which encapsulates a solution algorithm. The options may contain the following keys:

:type

This defaults to :backtracker (for the Theseus::Solvers::Backtracker solver), but may also be set to :astar (for the Theseus::Solvers::Astar solver).

:a

A 2-tuple (defaulting to start) that says where in the maze the solution should begin.

:b

A 2-tuple (defaulting to finish) that says where in the maze the solution should finish.

The returned solver will not yet have generated the solution. Use Theseus::Solvers::Base#solve or Theseus::Solvers::Base#step to generate the solution.

# File lib/theseus/maze.rb, line 236
def new_solver(options={})
  type = options[:type] || :backtracker

  require "theseus/solvers/#{type}"
  klass = Theseus::Solvers.const_get(type.to_s.capitalize)

  a = options[:a] || start
  b = options[:b] || finish

  klass.new(self, a, b)
end
opposite(direction) click to toggle source

Returns the direction opposite to the given direction. This will work even if the direction value is in the UNDER bitmask.

# File lib/theseus/maze.rb, line 404
def opposite(direction)
  if direction & UNDER != 0
    opposite(direction >> UNDER_SHIFT) << UNDER_SHIFT
  else
    case direction
    when N  then S
    when S  then N
    when E  then W
    when W  then E
    when NE then SW
    when NW then SE
    when SE then NW
    when SW then NE
    end
  end
end
potential_exits_at(x, y) click to toggle source

Returns an array of the possible exits for the cell at the given coordinates. Note that this does not take into account boundary conditions: a move in any of the returned directions may not actually be valid, and should be verified before being applied.

This is used primarily by subclasses to allow for different shaped cells (e.g. hexagonal cells for SigmaMaze, octagonal cells for UpsilonMaze).

# File lib/theseus/maze.rb, line 315
def potential_exits_at(x, y)
  raise NotImplementedError, "subclasses must implement #potential_exits_at"
end
relative_direction(from, to) click to toggle source

Returns the direction of to relative to from. to and from are both points (2-tuples).

# File lib/theseus/maze.rb, line 572
def relative_direction(from, to)
  # first, look for the case where the maze wraps, and from and to
  # are on opposite sites of the grid.
  if wrap_x? && from[1] == to[1] && (from[0] == 0 || to[0] == 0) && (from[0] == @width-1 || to[0] == @width-1)
    if from[0] < to[0]
      W
    else
      E
    end
  elsif wrap_y? && from[0] == to[0] && (from[1] == 0 || to[1] == 0) && (from[1] == @height-1 || to[1] == @height-1)
    if from[1] < to[1]
      N
    else
      S
    end
  elsif from[0] < to[0]
    if from[1] < to[1]
      SE
    elsif from[1] > to[1]
      NE
    else
      E
    end
  elsif from[0] > to[0]
    if from[1] < to[1]
      SW
    elsif from[1] > to[1]
      NW
    else
      W
    end
  elsif from[1] < to[1]
    S
  elsif from[1] > to[1]
    N
  else
    # same point!
    nil
  end
end
row_length(row) click to toggle source

Returns the number of cells in the given row. This is generally safer than relying the width method, since it is theoretically possible for a maze to have a different number of cells for each of its rows.

# File lib/theseus/maze.rb, line 518
def row_length(row)
  @cells[row].length
end
solve(options={}) click to toggle source

Returns the solution for the maze as an array of 2-tuples, each indicating a cell (in sequence) leading from the start to the finish.

See new_solver for a description of the supported options.

# File lib/theseus/maze.rb, line 252
def solve(options={})
  new_solver(options).solution
end
sparsify!() click to toggle source

Removes one cell from all dead-ends in the maze. Each call to this method removes another level of dead-ends, making the maze increasingly sparse.

# File lib/theseus/maze.rb, line 379
def sparsify!
  dead_ends.each do |(x, y)|
    cell = @cells[y][x]
    direction = cell & PRIMARY
    nx, ny = move(x, y, direction)

    # if the cell includes UNDER codes, shifting it all UNDER_SHIFT bits to the right
    # will convert those UNDER codes to PRIMARY codes. Otherwise, it will
    # simply zero the cell, resulting in a blank spot.
    @cells[y][x] >>= UNDER_SHIFT

    # if it's a weave cell (that moves over or under another corridor),
    # nix it and move back one more, so we don't wind up with dead-ends
    # underneath another corridor.
    if @cells[ny][nx] & (opposite(direction) << UNDER_SHIFT) != 0
      @cells[ny][nx] &= ~((direction | opposite(direction)) << UNDER_SHIFT)
      nx, ny = move(nx, ny, direction)
    end

    @cells[ny][nx] &= ~opposite(direction)
  end
end
start() click to toggle source

Since entrance may be external to the maze, start returns the cell adjacent to entrance that lies within the maze. If entrance is already internal to the maze, this method returns entrance. If entrance is not adjacent to any internal cell, this method returns nil.

# File lib/theseus/maze.rb, line 296
def start
  adjacent_point(@entrance)
end
step() click to toggle source

Completes a single iteration of the maze generation algorithm. Returns false if the method should not be called again (e.g., the maze has been completed), and true otherwise.

# File lib/theseus/maze.rb, line 269
def step
  return false if @generated

  if @deadends && @deadends.any?
    dead_end = @deadends.pop
    braid_cell(dead_end[0], dead_end[1])

    @generated = @deadends.empty?
    return !@generated
  end

  if @algorithm.step
    return true
  else
    return finish!
  end
end
to(format, options={}) click to toggle source

Returns the maze rendered to a particular format. Supported formats are currently :ascii and :png. The options hash is passed through to the formatter.

# File lib/theseus/maze.rb, line 646
def to(format, options={})
  case format
  when :ascii then
    require "theseus/formatters/ascii/#{type.downcase}"
    Formatters::ASCII.const_get(type).new(self, options)
  when :png then
    require "theseus/formatters/png/#{type.downcase}"
    Formatters::PNG.const_get(type).new(self, options).to_blob
  else
    raise ArgumentError, "unknown format: #{format.inspect}"
  end
end
to_s(options={}) click to toggle source

Returns the maze rendered to a string.

# File lib/theseus/maze.rb, line 660
def to_s(options={})
  to(:ascii, options).to_s
end
type() click to toggle source

Returns the type of the maze as a string. OrthogonalMaze, for instance, is reported as “orthogonal”.

# File lib/theseus/maze.rb, line 639
def type
  self.class.name[/::(.*?)Maze$/, 1]
end
valid?(x, y) click to toggle source

Returns true if the given coordinates are valid within the maze. This will be the case if:

  1. The coordinates lie within the maze's bounds, and

  2. The current mask for the maze does not restrict the location.

If the maze wraps in x, the x coordinate is unconstrained and will be mapped (via modulo) to the bounds. Similarly, if the maze wraps in y, the y coordinate will be unconstrained.

# File lib/theseus/maze.rb, line 338
def valid?(x, y)
  return false if !wrap_y? && (y < 0 || y >= height)
  y %= height
  return false if !wrap_x? && (x < 0 || x >= row_length(y))
  x %= row_length(y)
  return @mask[x, y]
end
vmirror(direction) click to toggle source

Returns the direction that is the vertical mirror to the given direction. This will work even if the direction value is in the UNDER bitmask.

# File lib/theseus/maze.rb, line 441
def vmirror(direction)
  if direction & UNDER != 0
    vmirror(direction >> UNDER_SHIFT) << UNDER_SHIFT
  else
    case direction
    when N  then S
    when S  then N
    when NE then SE
    when NW then SW
    when SE then NE
    when SW then NW
    else direction
    end
  end
end
wrap_x?() click to toggle source

Returns true if the maze may be wrapped in the x direction (left-to-right).

# File lib/theseus/maze.rb, line 320
def wrap_x?
  @wrap == :x || @wrap == :xy
end
wrap_y?() click to toggle source

Returns true if the maze may be wrapped in the y direction (top-to-bottom).

# File lib/theseus/maze.rb, line 325
def wrap_y?
  @wrap == :y || @wrap == :xy
end