Implementation of an upsilon grid (tiled octagons & squares) and corresponding maze.

upsilon.rb

require 'chunky_png'

class Cell
  attr_reader :row, :col

  def initialize(row, col)
    @row, @col = row, col
    @links = {}
  end

  def link(cell, both=true)
    @links[cell] = true
    cell.link(self, false) if both
    self
  end

  def links
    @links.keys
  end

  def linked?(cell)
    @links.key?(cell)
  end

  def octagon?
    false
  end
end

class SquareCell < Cell
  attr_accessor :north, :south
  attr_accessor :east, :west

  def neighbors
    [north, south, east, west].compact
  end
end

class OctagonCell < Cell
  attr_accessor :north, :northwest, :northeast
  attr_accessor :east, :west
  attr_accessor :south, :southwest, :southeast

  def neighbors
    [north, northwest, northeast,
     east, west,
     south, southwest, southeast].compact
  end

  def octagon?
    true
  end
end

class UpsilonGrid
  attr_reader :rows, :cols

  def initialize(rows, cols)
    @rows, @cols = rows, cols
    _setup_grid
    _configure_cells
  end

  def [](row, col)
    return nil if row < 0 || row >= rows
    return nil if col < 0 || col >= cols
    @grid[row][col]
  end

  def sample
    @grid.sample.sample
  end

  def each_cell
    @grid.each do |row|
      row.each do |cell|
        yield cell
      end
    end
    self
  end

  def _setup_grid
    @grid = Array.new(rows) do |row|
      Array.new(cols) do |col|
        if (row + col).even?
          OctagonCell.new(row, col)
        else
          SquareCell.new(row, col)
        end
      end
    end
  end

  def _configure_cells
    each_cell do |cell|
      row, col = cell.row, cell.col

      cell.north = self[row-1, col]
      cell.south = self[row+1, col]
      cell.west  = self[row, col-1]
      cell.east  = self[row, col+1]

      if cell.octagon?
        cell.northwest = self[row-1, col-1]
        cell.northeast = self[row-1, col+1]
        cell.southwest = self[row+1, col-1]
        cell.southeast = self[row+1, col+1]
      end
    end
  end

  def to_png(size: 10)
    a_size = size / 2.0
    b_size = size / Math.sqrt(2)
    oct_size = size + b_size * 2

    img_width = (oct_size + (size + b_size) * (cols - 1)).to_i
    img_height = (oct_size + (size + b_size) * (rows - 1)).to_i

    background = ChunkyPNG::Color::WHITE
    wall = ChunkyPNG::Color::BLACK

    img = ChunkyPNG::Image.new(img_height+1, img_width+1,
      background)

    each_cell do |cell|
      cx = b_size + a_size + (b_size + size) * cell.col
      cy = b_size + a_size + (b_size + size) * cell.row

      if cell.octagon?
        _draw_octagon_cell(img, wall, cell, cx, cy, a_size, b_size)
      else
        _draw_square_cell(img, wall, cell, cx, cy, a_size)
      end
    end

    img
  end

  def _draw_octagon_cell(img, wall, cell, cx, cy, a_size, b_size)
    # f/n = far, near
    # n/s/e/w = north, south, east, west

    x_fw = (cx - a_size - b_size).to_i
    x_nw = (cx - a_size).to_i
    x_ne = (cx + a_size).to_i
    x_fe = (cx + a_size + b_size).to_i

    y_fn = (cy - a_size - b_size).to_i
    y_nn = (cy - a_size).to_i
    y_ns = (cy + a_size).to_i
    y_fs = (cy + a_size + b_size).to_i

    # outer walls
    img.line(x_nw, y_fn, x_ne, y_fn, wall) if !cell.north
    img.line(x_nw, y_fn, x_fw, y_nn, wall) if !cell.northwest
    img.line(x_fw, y_nn, x_fw, y_ns, wall) if !cell.west
    img.line(x_fw, y_ns, x_nw, y_fs, wall) if !cell.southwest

    # inner walls (depending on linkages)
    img.line(x_ne, y_fn, x_fe, y_nn, wall) if !cell.linked?(cell.northeast)
    img.line(x_fe, y_nn, x_fe, y_ns, wall) if !cell.linked?(cell.east)
    img.line(x_fe, y_ns, x_ne, y_fs, wall) if !cell.linked?(cell.southeast)
    img.line(x_nw, y_fs, x_ne, y_fs, wall) if !cell.linked?(cell.south)
  end

  def _draw_square_cell(img, wall, cell, cx, cy, a_size)
    x1 = (cx - a_size).to_i
    y1 = (cy - a_size).to_i
    x2 = (cx + a_size).to_i
    y2 = (cy + a_size).to_i

    img.line(x1, y1, x2, y1, wall) if !cell.north
    img.line(x1, y1, x1, y2, wall) if !cell.west
    img.line(x2, y1, x2, y2, wall) if !cell.linked?(cell.east)
    img.line(x1, y2, x2, y2, wall) if !cell.linked?(cell.south)
  end
end

grid = UpsilonGrid.new(11, 11)
grid.to_png(size: 15).save("upsilon.png")

stack = [ grid.sample ]
while stack.any?
  current = stack.last
  neighbors = current.neighbors.select { |n| n.links.empty? }
  neighbor = neighbors.sample

  if neighbor
    current.link(neighbor)
    stack.push(neighbor)
  else
    stack.pop
  end
end

grid.to_png(size: 15).save("upsilon-maze.png")