local mazegen = {}

math.randomseed( os.time() )
 
-- Fisher-Yates shuffle from http://santos.nfshost.com/shuffling.html
local function shuffle(t)
  for i = 1, #t - 1 do
    local r = math.random(i, #t)
    t[i], t[r] = t[r], t[i]
  end
end

mazegen.shuffle = shuffle 
-- builds a width-by-height grid of trues
local function initialize_grid(w, h)
  local a = {}
  for i = 1, h do
    table.insert(a, {})
    for j = 1, w do
      table.insert(a[i], true)
    end
  end
  return a
end
 
mazegen.initialize_grid = initialize_grid
-- average of a and b
local function avg(a, b)
  return (a + b) / 2
end
 
 
local dirs = {
  {x = 0, y = -2}, -- north
  {x = 2, y = 0}, -- east
  {x = -2, y = 0}, -- west
  {x = 0, y = 2}, -- south
}
 
local function make_maze(w, h)
  w = w or 16
  h = h or 8
 
  local map = initialize_grid(w*2+1, h*2+1)
 
  function walk(x, y)
    map[y][x] = false
 
    local d = { 1, 2, 3, 4 }
    shuffle(d)
    for i, dirnum in ipairs(d) do
      local xx = x + dirs[dirnum].x
      local yy = y + dirs[dirnum].y
      if map[yy] and map[yy][xx] then
        map[avg(y, yy)][avg(x, xx)] = false
        walk(xx, yy)
      end
    end
  end
 
  walk(math.random(1, w)*2, math.random(1, h)*2)
 
  local s = {}
  for i = 1, h*2+1 do
    for j = 1, w*2+1 do
      if map[i][j] then
        table.insert(s, '#')
      else
        table.insert(s, ' ')
      end
    end
    table.insert(s, '\n')
  end
  return table.concat(s)
end

mazegen.make_maze = make_maze

function make_maze_tex(w, h, m)
  w = w or 16
  h = h or 8
 
  local map = initialize_grid(w*2+1, h*2+1)
 
  function walk(x, y)
    map[y][x] = false
 
    local d = { 1, 2, 3, 4 }
    shuffle(d)
    for i, dirnum in ipairs(d) do
      local xx = x + dirs[dirnum].x
      local yy = y + dirs[dirnum].y
      if map[yy] and map[yy][xx] then
        map[avg(y, yy)][avg(x, xx)] = false
        walk(xx, yy)
      end
    end
  end
 
  walk(math.random(1, w)*2, math.random(1, h)*2)
 
 tex.print([[\bgroup]])
 tex.print([[\baselineskip ]]..m)
  local s = {}
  for i = 1, h*2+1 do
    --table.insert(s, [[\hbox{]])
    tex.print([[\hbox{]])
    for j = 1, w*2+1 do
     -- table.insert(s, [[\hbox{]])
      if (j == 1 and i == 2) or (j == 2*w + 1 and i == 2*h) then 
        tex.print([[\hskip ]]..m)
      elseif map[i][j] then
        --table.insert(s, [[\vrule width ]]..m..[[ height ]]..m)
        tex.print([[\vrule width ]]..m..[[ height ]]..m)
      else
        --table.insert(s, [[\hskip ]]..m)
        tex.print([[\hskip ]]..m)
      end
    --  table.insert(s, [[}]].."\n")
    end
    --table.insert(s, [[}]])
  tex.print([[}]])
  end
 --tex.print(table.concat(s))
 tex.print([[\egroup]])
end

mazegen.make_maze_tex = make_maze_tex

return mazegen