Generate and display a toroidal grid (adaptively subdivided to reduce distortion).

torus-grid.rb

require 'chunky_png'

class ToroidalGrid
  class Cell
    attr_reader :row, :column
    attr_reader :north, :south
    attr_accessor :east, :west

    def initialize(row, column)
      @row, @column = row, column
      @north, @south = [], []
      @east = @west = nil
      @links = {}
    end

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

    def link!(neighbor, once=false)
      @links[neighbor] = true
      neighbor.link!(self, true) unless once
    end

    def linked?(neighbor)
      @links[neighbor]
    end

    def links
      @links.keys
    end
  end

  attr_reader :row_count, :minor_radius

  def initialize(row_count, minor_radius)
    raise ArgumentError, "must have at least 3 rows" if row_count < 3
    raise ArgumentError, "minor radius must be in (0,1)" if minor_radius <= 0 || minor_radius >= 1

    @row_count = row_count
    @minor_radius = minor_radius

    configure_grid!
  end

  def configure_grid!
    @rows = Array.new(row_count)

    # angular height of a single row (unit circle)
    theta = 2 * Math::PI / row_count

    # minor circumference of the torus (poloidal distance)
    minor_circ = 2 * Math::PI * minor_radius
    row_height = minor_circ / row_count

    # the row with the largest dimension, and maximum # of cells
    equator = (row_count-1) / 2

    # south side of first row == outermost major circumference
    # north side of last row == south side of first row

    row_count.times do |row_idx|
      north_angle = theta * row_idx
      south_angle = theta * (row_idx + 1)

      # 1 == major radius of torus
      # north/south radius -- radius of the circle formed by the
      #   boundary on that side of the current row
      south_radius = 1 - minor_radius * Math.cos(south_angle)
      north_radius = 1 - minor_radius * Math.cos(north_angle)

      # distance around the torus for the given boundary of the current
      # row
      south_circ = 2 * Math::PI * south_radius
      north_circ = 2 * Math::PI * north_radius

      longest = [south_circ, north_circ].max
      ideal_count = longest / row_height

      if row_idx == 0
        count = [1, ideal_count.round].max
      elsif row_idx > equator
        mirror = @rows.length - row_idx - 1
        count = @rows[mirror].length
      else
        prior_count = @rows[row_idx-1].length

        if ideal_count < (prior_count * 2.0 / 3)
          count = prior_count / 2
        elsif ideal_count > (prior_count * 3.0 / 2)
          count = prior_count * 2
        else
          count = prior_count
        end
      end

      row = @rows[row_idx] = Array.new(count) { |col| Cell.new(row_idx, col) }
      configure_row!(row)
    end

    # account for the north/south boundary wrapping
    @rows[0].each do |cell|
      neighbor = @rows[-1][cell.column]
      cell.north.push neighbor
      neighbor.south.push cell
    end
  end

  def configure_row!(row)
    first_cell = row[0]
    north = first_cell.row > 0 ? @rows[first_cell.row-1] : nil

    row.each do |cell|
      if north
        if north.length == row.length
          cell.north.push north[cell.column]
        elsif north.length < row.length
          cell.north.push north[cell.column/2]
        else
          cell.north.push north[cell.column*2]
          cell.north.push north[cell.column*2+1]
        end

        cell.north.each { |c| c.south.push(cell) }
      end

      cell.west = row[(cell.column-1) % row.length]
      cell.east = row[(cell.column+1) % row.length]
    end
  end

  def each_row
    @rows.each do |row|
      yield row
    end

    self
  end

  def each_cell
    each_row do |row|
      row.each do |cell|
        yield cell
      end
    end
  end

  def sample
    @rows.flatten.sample
  end

  def [](row, column)
    @rows[row][column]
  end

  def to_png(size: 10)
    equator = @rows.length / 2
    img_width = @rows[equator].length * size
    img_height = @rows.length * size

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

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

    each_cell do |cell|
      y1 = cell.row * size
      y2 = (cell.row+1) * size - 1

      cell_width = img_width / @rows[cell.row].length.to_f
      x1 = (cell.column * cell_width).round

      img.line(x1, y1, x1, y2, wall) if !cell.linked?(cell.west)

      wall_inc = cell_width / cell.south.length
      walls = (0..cell.south.length).map { |i| (x1 + wall_inc * i).round }

      cell.south.each_with_index do |neighbor, idx|
        if !cell.linked?(neighbor)
          img.line(walls[idx], y2, walls[idx+1], y2, wall)
        end
      end
    end

    img
  end
end

grid = ToroidalGrid.new(16, 0.5)
grid.to_png.save("torus-grid.png")

stack = [ grid.sample ]

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

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

grid.to_png.save("torus-maze.png")