Prim's Algorithm

runner.rb

# Data structure for square
class Square
  attr_accessor :in, :frontier
  attr_reader :walls
  def initialize
    @walls = (0..3).to_a
    @in = false
    @frontier = false
  end

  def open_wall(i)
    @walls.delete(i)
  end
end

def neighbors(x, y, grid)
  [x - 1, x + 1]
    .select { |n| (0...grid[0].length).include?(n) }
    .product([y]) +
    [x].product([y - 1, y + 1]
      .select { |n| (0...grid.length).include?(n) })
  # n = []
  # n << [x - 1, y] if x > 0
  # n << [x + 1, y] if x + 1 < grid[0].length
  # n << [x, y - 1] if y > 0
  # n << [x, y + 1] if y + 1 < grid.length
  # n
end

def neighbors_in(x, y, grid)
  neighbors(x, y, grid).select { |nx, ny| grid[ny][nx].in }
end

def expand_frontier(x, y, grid, frontier)
  neighbors(x, y, grid).select { |nx, ny| !grid[ny][nx].frontier }
    .each do |nx, ny|
    frontier << [nx, ny]
    grid[ny][nx].frontier = true
  end
end

def connect(x, y, nx, ny, grid)
  if y > ny
    # grid[y][x].open_wall(0)
    grid[ny][nx].open_wall(2)
  elsif x < nx
    grid[y][x].open_wall(1)
    # grid[ny][nx].open_wall(3)
  elsif y < ny
    grid[y][x].open_wall(2)
    # grid[ny][nx].open_wall(0)
  elsif x > nx
    # grid[y][x].open_wall(3)
    grid[ny][nx].open_wall(1)
  end
end

def display_maze(grid)
  maze_string = "\e[2J\e[H" + '.' + '_.' * grid[0].length + "\n"
  grid.each do |row|
    row_string = '|'
    row.each do |square|
      row_string << (square.walls.include?(2) ? '_' : ' ')
      row_string << (square.walls.include?(1) ? '|' : '.')
    end
    row_string << "\n"
    maze_string += row_string
  end
  puts maze_string
end

HEIGHT = 20
WIDTH = 30
grid = Array.new(HEIGHT) { Array.new(WIDTH) { Square.new } }
frontier = [[rand(WIDTH), rand(HEIGHT)]]
x, y = frontier.first
p grid
grid[y][x].frontier = true

display_maze(grid)
while frontier.length > 0
  sleep 0.002
  x, y = frontier.delete_at(rand(frontier.length))
  nx, ny = neighbors_in(x, y, grid).sample
  connect(x, y, nx, ny, grid) if nx
  grid[y][x].in = true
  expand_frontier(x, y, grid, frontier)
  display_maze(grid)
end