class Theseus::OrthogonalMaze
An orthogonal maze is one in which the field is tesselated into squares. This is probably the type of maze that most people think of, when they think of mazes.
The orthogonal maze implementation in Theseus
is the most complete, supporting weaving as well as all four symmetry types. You can even convert any “perfect” (no loops) orthogonal maze to a “unicursal” maze. (Unicursal means “one course”, and refers to a maze that has no junctions, only a single path that takes you through every cell in the maze exactly once.)
maze = Theseus::OrthogonalMaze.generate(width: 10) puts maze
Public Instance Methods
Takes the current orthogonal maze and converts it into a unicursal maze. A unicursal maze is one with only a single path, and no dead-ends or junctions. Such mazes are more properly called “labyrinths”. Note that although this method will always return a new OrthogonalMaze
instance, it is not guaranteed to be a valid maze unless the current maze is “perfect” (not braided, containing no loops).
The resulting unicursal maze will be twice as wide and twice as high as the original maze.
The options
hash can be used to specify the :entrance
and :exit
points for the resulting maze. Currently, both the entrance and the exit must be adjacent.
The process of converting an orthogonal maze to a unicursal maze is straightforward; take the maze, and divide all passages in half down the middle, making two passages. Dead-ends become a u-turn, etc. This is why the maze increases in size.
# File lib/theseus/orthogonal_maze.rb, line 108 def to_unicursal(options={}) unicursal = OrthogonalMaze.new(options.merge(width: @width*2, height: @height*2, prebuilt: true)) set = lambda do |x, y, direction, *recip| nx, ny = move(x, y, direction) unicursal[x,y] |= direction unicursal[nx, ny] |= opposite(direction) if recip[0] end @cells.each_with_index do |row, y| row.each_with_index do |cell, x| x2 = x * 2 y2 = y * 2 if cell & N != 0 set[x2, y2, N] set[x2+1, y2, N] set[x2, y2+1, N, true] if cell & W == 0 set[x2+1, y2+1, N, true] if cell & E == 0 set[x2, y2+1, E, true] if (cell & PRIMARY) == N end if cell & S != 0 set[x2, y2+1, S] set[x2+1, y2+1, S] set[x2, y2, S, true] if cell & W == 0 set[x2+1, y2, S, true] if cell & E == 0 set[x2, y2, E, true] if (cell & PRIMARY) == S end if cell & W != 0 set[x2, y2, W] set[x2, y2+1, W] set[x2+1, y2, W, true] if cell & N == 0 set[x2+1, y2+1, W, true] if cell & S == 0 set[x2+1, y2, S, true] if (cell & PRIMARY) == W end if cell & E != 0 set[x2+1, y2, E] set[x2+1, y2+1, E] set[x2, y2, E, true] if cell & N == 0 set[x2, y2+1, E, true] if cell & S == 0 set[x2, y2, S, true] if (cell & PRIMARY) == E end if cell & (N << UNDER_SHIFT) != 0 unicursal[x2, y2] |= (N | S) << UNDER_SHIFT unicursal[x2+1, y2] |= (N | S) << UNDER_SHIFT unicursal[x2, y2+1] |= (N | S) << UNDER_SHIFT unicursal[x2+1, y2+1] |= (N | S) << UNDER_SHIFT elsif cell & (W << UNDER_SHIFT) != 0 unicursal[x2, y2] |= (E | W) << UNDER_SHIFT unicursal[x2+1, y2] |= (E | W) << UNDER_SHIFT unicursal[x2, y2+1] |= (E | W) << UNDER_SHIFT unicursal[x2+1, y2+1] |= (E | W) << UNDER_SHIFT end end end enter_at = unicursal.adjacent_point(unicursal.entrance) exit_at = unicursal.adjacent_point(unicursal.exit) if enter_at && exit_at unicursal.add_opening_from(unicursal.entrance) unicursal.add_opening_from(unicursal.exit) if enter_at[0] < exit_at[0] unicursal[enter_at[0], enter_at[1]] &= ~E unicursal[enter_at[0]+1, enter_at[1]] &= ~W elsif enter_at[1] < exit_at[1] unicursal[enter_at[0], enter_at[1]] &= ~S unicursal[enter_at[0], enter_at[1]+1] &= ~N end end return unicursal end