Skip to content

Instantly share code, notes, and snippets.

@jamis
Last active Oct 17, 2017
Embed
What would you like to do?
Generate and display a toroidal grid (adaptively subdivided to reduce distortion).
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment