Generate a maze that spans all six faces of a cube.

cube-maze.rb

###########################################################################
# 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.
# -------------------------------------------------------------------------
# License? What license? We don't need no stinkin' license.
# This code is in the public domain. Knock yourself out. Use it however
# you want. Please prefer good over evil.
###########################################################################

require 'chunky_png'

# number of cells on a side, on each face of the cube
DIM = (ARGV[0] || 5).to_i

# the number to seed the random number generator with
SEED = (ARGV[1] || Time.now.to_i)

srand(SEED)

# Various constants to use during the maze generation process

N = 1
S = 2
E = 4
W = 8
DIRS = [N, S, E, W]

DX = { N => 0, S => 0, E => 1, W => -1 }
DY = { N => -1, S => 1, E => 0, W => 0 }
OPP = { N => S, S => N, E => W, W => E }

WRAPS = {
  0 => { N => [3, { :x => :x, :y => :max, :d => S }],
         S => [1, { :x => :x, :y => 0, :d => N }],
         W => [4, { :x => :y, :y => 0, :d => N }],
         E => [5, { :x => :dy, :y => 0, :d => N }] },

  1 => { N => [0, { :x => :x, :y => :max, :d => S }],
         S => [2, { :x => :x, :y => 0, :d => N }],
         W => [4, { :x => :max, :y => :y, :d => E }],
         E => [5, { :x => 0, :y => :y, :d => W }] },

  2 => { N => [1, { :x => :x, :y => :max, :d => S }],
         S => [3, { :x => :x, :y => 0, :d => N }],
         W => [4, { :x => :dy, :y => :max, :d => S }],
         E => [5, { :x => :y, :y => :max, :d => S }] },

  3 => { N => [2, { :x => :x, :y => :max, :d => S }],
         S => [0, { :x => :x, :y => 0, :d => N }],
         W => [4, { :x => 0, :y => :dy, :d => W }],
         E => [5, { :x => :max, :y => :dy, :d => E }] },

  4 => { N => [0, { :x => 0, :y => :x, :d => W }],
         S => [2, { :x => 0, :y => :dx, :d => W }],
         W => [3, { :x => 0, :y => :dy, :d => W }],
         E => [1, { :x => 0, :y => :y, :d => W }] },

  5 => { N => [0, { :x => :max, :y => :dx, :d => E }],
         S => [2, { :x => :max, :y => :x, :d => E }],
         W => [1, { :x => :max, :y => :y, :d => E }],
         E => [3, { :x => :max, :y => :dy, :d => E }] }
}

_ = nil
LAYOUT = [
  [ _, 0, _ ],
  [ 4, 1, 5 ],
  [ _, 2, _ ],
  [ _, 3, _ ]
]

UTF8_LINES = [" ", "╵", "╷", "│", "╶", "└", "┌", "├", "╴", "┘", "┐", "┤", "─", "┴", "┬", "┼"]

# Some helper functions

def map(x, y, cmd)
  case cmd
  when :x then x
  when :y then y
  when :max then DIM-1
  when :dx then DIM - x - 1
  when :dy then DIM - y - 1
  else cmd
  end
end

def move(from_face, from_x, from_y, dir)
  to_face = from_face
  to_x = from_x + DX[dir]
  to_y = from_y + DY[dir]

  if to_x < 0 || to_x >= DIM || to_y < 0 || to_y >= DIM
    to_face, mapping = WRAPS[from_face][dir]
    new_x = map(to_x, to_y, mapping[:x])
    new_y = map(to_x, to_y, mapping[:y])
    route = mapping[:d]
    to_x, to_y = new_x, new_y
  else
    route = OPP[dir]
  end

  [to_face, to_x, to_y, route]
end

COLORS = [7, 6, 5, 4, 3, 2]
def draw(faces)
  print "\e[H" # move to upper-left

  LAYOUT.each do |row|
    DIM.times do |y|
      row.each do |face|
        print "\e[#{face ? 40+COLORS[face] : 40};#{face ? 30 : 37}m"
        DIM.times do |x|
          print(face ? UTF8_LINES[faces[face][y][x]] : " ")
        end
      end
      puts
    end
  end

  print "\e[0m"
end

# The data structures for use in the algorithm

faces = Array.new(6) { Array.new(DIM) { Array.new(DIM, 0) } }
queue = [ [0, 0, 0] ]

print "\e[2J" # clear the screen

# Use the "growing tree" algorithm to build the maze, with a
# cell-selection heuristic of "last added". This gives long,
# windy passages and fewer dead-ends.

while queue.any?
  face, x, y = queue.last

  moved = false
  DIRS.shuffle.each do |dir|
    new_face, new_x, new_y, route = move(face, x, y, dir)
    if faces[new_face][new_y][new_x] == 0
      faces[face][y][x] |= dir
      faces[new_face][new_y][new_x] = route
      queue << [new_face, new_x, new_y]
      moved = true
      draw(faces)
      break
    end
  end

  queue.pop if !moved
end

puts "generating `cube.png'..."

# Build the PNG output file.

CELL_DIM = 19
CELL_MID = (CELL_DIM + 1) / 2

CORNERS = [
  [DIM * CELL_DIM + 10, 10],                      # 0
  [DIM * CELL_DIM + 10, DIM * CELL_DIM + 10],     # 1
  [DIM * CELL_DIM + 10, 2 * DIM * CELL_DIM + 10], # 2
  [DIM * CELL_DIM + 10, 3 * DIM * CELL_DIM + 10], # 3
  [10, DIM * CELL_DIM + 10],                      # 4
  [2 * DIM * CELL_DIM + 10, DIM * CELL_DIM + 10], # 5
]

png = ChunkyPNG::Image.new(DIM * CELL_DIM * 3 + 20, DIM * CELL_DIM * 4 + 20, ChunkyPNG::Color::TRANSPARENT)

CORNERS.each_with_index do |(x, y), face|
  # draw face boxes
  png.rect(x, y, x + DIM * CELL_DIM, y + DIM * CELL_DIM, ChunkyPNG::Color.rgb(127, 127, 127))

  DIM.times do |cy|
    DIM.times do |cx|
      cell = faces[face][cy][cx]

      x_edge = x + cx * CELL_DIM
      x_mid = x_edge + CELL_MID
      y_edge = y + cy * CELL_DIM
      y_mid = y_edge + CELL_MID

      png.line(x_mid, y_edge, x_mid, y_mid, ChunkyPNG::Color::BLACK) if (cell & N) == N
      png.line(x_mid, y_mid, x_mid, y_edge+CELL_DIM, ChunkyPNG::Color::BLACK) if (cell & S) == S
      png.line(x_edge, y_mid, x_mid, y_mid, ChunkyPNG::Color::BLACK) if (cell & W) == W
      png.line(x_mid, y_mid, x_edge+CELL_DIM, y_mid, ChunkyPNG::Color::BLACK) if (cell & E) == E
    end
  end
end

png.save('cube.png')

puts "done: #{$0} #{DIM} #{SEED}"