-- http://www.astrolog.org/labyrnth/algrithm.htm
-- recursive backtracker

mw, mh = 64, 64       -- size
bx, by = 40, 13       -- beginning

local seed = arg and arg[1] or os.time()
print("seed="..seed)
math.randomseed(seed)

map = {}
for i = 1, mh do
  map[i] = {}
  for j = 1, mw do map[i][j] = false end
end
map[-1] = {}; map[0] = {}; map[mh+1] = {}; map[mh+2] = {}

--map[63][64], map[63][63], map[63][62] = nil
--map[1][2], map[2][2], map[3][2] = nil

stack = { n=1, {bx,by} }

local function carve(n,x,y)
  if map[y][x] ~= false then return end
  local r = 0
  if map[y-1][x] == true then r = r + 1 end
  if map[y+1][x] == true then r = r + 1 end
  if map[y][x-1] == true then r = r + 1 end
  if map[y][x+1] == true then r = r + 1 end
  if r ~= 1 then return end
  table.insert(n, {x,y})
end

while stack.n > 0 do
  x, y = unpack(stack[stack.n])
  map[y][x] = true
  local neighbors = {}
  carve(neighbors, x-1, y); carve(neighbors, x+1, y)
  carve(neighbors, x, y-1); carve(neighbors, x, y+1)
  if #neighbors == 0 then
    stack[stack.n] = nil; stack.n = stack.n - 1
  else
    stack.n = stack.n + 1
    stack[stack.n] = neighbors[math.random(#neighbors)]
  end
end

for i = 1, mh do
  for j = 1, mw do io.write(map[i][j] and ' ' or '#') end
  io.write'\n'
end