ccmazegen

--local file=io.open("mazeBase","r")
os.loadAPI("blittle")
local maze={
  candidates={},
  cells={},
  nodes={},
}

function maze:getTypeAt(x,y)
  if y<1 or y>#self or x<1 or x>#self[y] then
    return "void"
  end
  return self[y][x].type
end

function maze:getNodeAt(x,y)
  if y<1 or y>#self or x<1 or x>#self[y] then
    return 0
  else
    local cell=self[y][x].cell
    if cell then
      return self.cells[cell].node
    else
      return 0
    end
  end
end

local tTypeChar={void=" ",wall="X",cell=" ",path=" ",candidate="."}

function maze:typeChar(x,y)
  return tTypeChar[self:getTypeAt(x,y)]
end

local function drawMaze(maze,mon,showSolution,redNode, blueNode,yellowPos)
--win.setVisible(false)
  if mon.setVisible then mon.setVisible(false) end
  mon.setBackgroundColor(colors.black)
  mon.clear()

  for y=1,#maze do
    local row=maze[y]
    for x=1,#row do
      mon.setCursorPos(x,y)
      local cell=maze[y][x]
      local type=cell.type
      local cellN=cell.cell
      local fg=colors.white
      local bg=colors.black
      local char=tTypeChar[type]
      if type=="wall" then
        bg=colors.white
      elseif type=="void" then
        bg=colors.black
      elseif cellN==maze.entrance then
        bg=colors.green
        char="s"
      elseif cellN==maze.exit then
        bg=colors.green
        char="e"
      elseif showSolution and cell.onPath==true then
        bg=colors.green
      elseif redNode and type=="cell" and maze.cells[cellN] and maze.cells[cellN].node==redNode then
        bg=colors.red
      elseif blueNode and type=="cell" and maze.cells[cellN] and maze.cells[cellN].node==blueNode then
        bg=colors.blue
      elseif yellowPos and x==yellowPos[1] and y==yellowPos[2] then
        bg=colors.yellow
      end

      mon.setTextColor(fg)
      mon.setBackgroundColor(bg)
      mon.write(char)
    end
  end
  if mon.setVisible then mon.setVisible(true) end
end


local mon=peripheral.wrap("right")
mon.setTextScale(.5)
w,h=mon.getSize()
mon.setBackgroundColor(colors.black)
mon.clear()

local win=mon
--[[]]
win=blittle.createWindow(mon,2,2,w-1,h-1,true)
win.setBackgroundColor(colors.black)
win.clear()
w,h=win.getSize()
w=w-2
h=h-2
--]]

if h%2==0 then h=h-1 end
if w%2==0 then w=w-1 end

local base={}

for row=1,h do
    local line=""
    for col=1,w-1 do
        if row==1 or col==1 or row==h or col==w then
            line=line.."x"
        elseif row%2==1 and col%2==1 then
            line=line.."x"
        elseif row%2==1 or col%2==1 then
            line=line.."."
        else
            line=line.."c"
        end
    end
    base[row]=line.."x"
end
--replace last line to add start and end
base[#base]="xs"..string.rep("x",w-4).."ex"
--[[]]

local function addRoom(x,y,w,h)--make a room in the middle!
    base[y]=base[y]:sub(1,x-1)..string.rep("x",(w-1)/2).."."..string.rep("x",(w-1)/2)..base[y]:sub(x+w)
    local mid=string.rep("c",w-2)
    for row=y+1,y+h-2 do
        base[row]=base[row]:sub(1,x-1)..(row==y+(h-1)/2 and ("."..mid..".") or ("x"..mid.."x"))..base[row]:sub(x+w)
    end
    base[y+h-1]=base[y+h-1]:sub(1,x-1)..string.rep("x",(w-1)/2).."."..string.rep("x",(w-1)/2)..base[y+h-1]:sub(x+w)
    os.sleep()
end

local function randomRoom()
    local rw=math.random(5)*4+3
    local rh=math.random(5)*4+3
    local rx=math.random((w-6-rw)/2)*2+3
    local ry=math.random((h-6-rh)/2)*2+3
    addRoom(rx,ry,rw,rh)
end
for i=1,10 do
    randomRoom()
end
--]]

local rowN=0
for _,line in ipairs(base) do
  local row={}
  rowN=rowN+1
  for i=1,#line do
    local ch=line:sub(i,i)
    if ch==" " then
      row[i]={type="void"}
    elseif ch=="x" then
      row[i]={type="wall"}
    elseif ch=="c" then
      maze.cells[#maze.cells+1]={pos={i,rowN}, candidates={} }
      row[i]={type="cell",num=#maze.cells}
    elseif ch=="s" then
      maze.cells[#maze.cells+1]={pos={i,rowN}, candidates={} }
      row[i]={type="cell",num=#maze.cells}
      maze.entrance=#maze.cells
    elseif ch=="e" then
      maze.cells[#maze.cells+1]={pos={i,rowN}, candidates={} }
      row[i]={type="cell",num=#maze.cells}
      maze.exit=#maze.cells
    elseif ch=="." then
      row[i]={type="candidate"}
      maze.candidates[#maze.candidates+1]={pos={i,rowN}, cells={} }
    end
    row[i].pos={i,rowN}
  end
  maze[rowN]=row
  os.sleep()
end
--file:close()
drawMaze(maze,win,false)
os.pullEvent("monitor_touch")

--if no entrance specified, place an entrance at the bottom-center
if not maze.entrance then
  local y=#maze
  local x=math.ceil(#maze[y]/2)
  maze[y][x]={type="cell",num=#maze.cells+1}
  maze.cells[#maze.cells+1]={pos={x,y},candidates={}}
  maze[y+1]={[x]={type="wall"}}
  maze.entrance=#maze.cells
end

if not maze.exit then
  local x,y
  enter=maze.cells[maze.entrance].pos
  repeat
    x=math.random(1,16)*2
    y=math.random(1,16)*2
  until (x-enter[1])^2+(y-enter[2])^2 > 10
  --make it the exit
  maze.exit=maze[y][x].num
  --surround with walls!
  local eCan={}
  local function makeWall(y,x)
    maze[y][x].type="wall"
    --killing a cell, so, uh, pop from end and push here?
    cells[maze[y][x].num]=cells[#cells]
    --and point the pop'd cell's node to the new cell
    maze[cells[#cells].pos[2]][cells[#cells].pos[1]].num=maze[y][x].num
    cells[#cells]=nil
  end
  if maze[y-1] and maze[y-1][x] and maze[y-1][x].type~="wall" then
    eCan[#eCan+1]={y-1,x}
  end
  if maze[y+1] and maze[y+1][x] and maze[y+1][x].type~="wall" then
    eCan[#eCan+1]={y+1,x}
  end
  if maze[y] and maze[y][x-1] and maze[y][x-1].type~="wall" then
    eCan[#eCan+1]={y,x-1}
  end
  if maze[y] and maze[y][x+1] and maze[y][x+1].type~="wall" then
    eCan[#eCan+1]={y,x+1}
  end
  --pick one at random to remove
  table.remove(eCan,math.random(1,#eCan))
  --make the rest walls
  for i=1,#eCan do
    makeWall(eCan[i][2],eCan[i][1])
  end

end

--TODO: identify and merge cells that are touching into single nodes
--for now just making every cell a node containing only that cell
local nextNode=1
for i=1,#maze.cells do
  --is there a cell to my left?
  local pos=maze.cells[i].pos
  local myNode=nextNode
  local merging=nil
  if maze[pos[2]-1][pos[1]].type=="cell" then
    --merge
    myNode=maze.cells[maze[pos[2]-1][pos[1]].cell].node
    merging="up"
  elseif maze[pos[2]][pos[1]-1].type=="cell" then
    myNode=maze.cells[maze[pos[2]][pos[1]-1].cell].node
    merging="left"
  else
    nextNode=nextNode+1
    maze.nodes[myNode]={}
  end
  maze[pos[2]][pos[1]].cell=i
  --[[
  if merging then
    print("merging "..merging)
    maze.cells[i].node="dummy"
    drawMaze(maze,win,false,"dummy",myNode)
    os.pullEvent("monitor_touch")
  end
  --]]
  table.insert(maze.nodes[myNode],i)
  maze.cells[i].node=myNode

end
os.sleep()


do

  local function tryAddCell(canN,x,y)
    local t=maze:getTypeAt(x,y)
    if t=="cell" then
      local candidate=maze.candidates[canN]
      local c=maze[y][x].cell
      table.insert(candidate.cells,c)
      table.insert(maze.cells[c].candidates,canN)
      return 1
    end
    return 0
  end

  --figure out which nodes touch each candidate. Should only be two...
  for i=1,#maze.candidates do
    local x,y=unpack(maze.candidates[i].pos)
    local numCells=0
    local can=maze.candidates[i]
    numCells=numCells+tryAddCell(i,x-1,y)
    numCells=numCells+tryAddCell(i,x+1,y)
    numCells=numCells+tryAddCell(i,x,y-1)
    numCells=numCells+tryAddCell(i,x,y+1)
    if numCells~=2 then
      error("Encountered "..numCells.." cells touching candidate at ("..x..","..y..")")
    end
    --draw touching nodes
    --drawMaze(maze,win,false,maze.candidates[i].cells[1],maze.candidates[i].cells[2])
    --os.pullEvent("monitor_touch")
  end
end

local function tableCopy(source)
  local copy={}
  for k,v in pairs(source) do
    if type(v)=="table" then
      copy[k]=tableCopy(v)
    else
      copy[k]=v
    end
  end
  return copy
end




local function genKruskal(maze,visualize)
  --now generate the actual maze!
  --copy candidates, nodes, and maze, since we change them
  local maze=tableCopy(maze)
  --while candidates remain
  while #maze.candidates>0 do
    --pick a random candidate
    local candidateNum=math.random(1,#maze.candidates)
    --print("candidate number "..candidateNum)
    local can=table.remove(maze.candidates,candidateNum)
    --print("position: ("..can.pos[1]..","..can.pos[2]..")")
    local c1, c2=can.cells[1],can.cells[2]
    --print("c1="..c1..", c2="..c2)
    local n1, n2=maze.cells[c1].node, maze.cells[c2].node
    --print("n1="..n1..", n2="..n2)
    --compade nodes of neighboring cells
    if n1~=n2 then
      if visualize then
        print(textutils.serialize(can.pos))
        drawMaze(maze,win,false,n1,n2,can.pos)
        os.pullEvent("monitor_touch")
      end
      --different, make type path
      maze[can.pos[2]][can.pos[1]].type="path"
      --merge nodes. For each cell in node n2
      local node1,node2=maze.nodes[n1],maze.nodes[n2]
      for i=1,#node2 do
        --add to n1's cell list
        local c=node2[i]
        table.insert(node1,c)
        --and move the cell to node n1
        maze.cells[c].node=n1
      end
    else
      --same, make type wall
      maze[can.pos[2]][can.pos[1]].type="wall"
    end
  end
  return maze;
end

local function genGrowingTree(maze)
  local maze=tableCopy(maze)

  local open={}
  --start at entrance if set, otherwise random
  if maze.entrance then
    open[1]=maze.entrance
  else
    open[1]=math.random(#maze.cells)
  end
  maze.cells[open[1]].visited=true
  --make all candidates walls first
  for i=1,#maze.candidates do
    local pos=maze.candidates[i].pos
    maze[pos[2]][pos[1]].type="wall"
  end

  while #open>0 do
    --choose a cell - for now we'll do newest
    local n
    local r=math.random(100)
    if r>25 then
      n=#open
    else
      n=math.random(#open)
    end
    local cellN=table.remove(open,n)
    local cell=maze.cells[cellN]
    if #cell.candidates>0 then
      --pick a random candidate from this cell
      local validCandidates={}
      --first identify valid candidates to unvisited cells
      for i=1,#cell.candidates do
        local can=maze.candidates[cell.candidates[i]]
        local cell2N=can.cells[1]==cellN and can.cells[2] or can.cells[1]
        local cell2=maze.cells[cell2N]
        if not cell2.visited then
          validCandidates[#validCandidates+1]={cell2N,cell.candidates[i]}
        end
      end
      if #validCandidates>0 then
        --there are valid candidates
        --re-add myself to open
        open[#open+1]=cellN
        local next=validCandidates[math.random(#validCandidates)]
        open[#open+1]=next[1]
        maze.cells[next[1]].visited=true
        --make this candidate not a wall
        local wallPos=maze.candidates[next[2]].pos
        maze[wallPos[2]][wallPos[1]].type="path"
      end
    end
  end

  return maze
end



local function analyze(maze)

  local open={}
  if maze.entrance then
    local c=maze.cells[maze.entrance]
    open[1]=maze[c.pos[2]][c.pos[1]]
  else
    local c=maze.cells[math.random(#maze.cells)]
    open[1]=maze[c.pos[2]][c.pos[1]]
  end
  open[1].cost=0

  local closed={}
  local neighbors={{-1,0},{1,0},{0,-1},{0,1}}
  local exit=maze.cells[maze.exit]
  exit=maze[exit.pos[2]][exit.pos[1]]
  local entrance=maze.cells[maze.entrance]
  entrance=maze[entrance.pos[2]][entrance.pos[1]]

  while #open>0 do
    --pop an open cell
    local cell=table.remove(open)
    local x,y=cell.pos[1],cell.pos[2]
    --is this the end?
    if cell==exit then
      --print("found exit!")
      --backtrack and mark as path
      local c=cell
      repeat
        maze[c.pos[2]][c.pos[1]].onPath=true
        c=c.prev
      until c==nil
    end

    --for each possible neighbor...
    for k,v in pairs(neighbors) do
      local nx, ny=x+v[1],y+v[2]
      local c=maze[ny] and maze[ny][nx] or nil
      local cost=cell.cost+1
      --if it's not closed or closed cost was more
      if c and (c.type=="path" or c.type=="cell") and (closed[c]==nil or c.cost>cell.cost) then
        --set/update cost and prev
        c.cost=cell.cost+1
        c.prev=cell
        --if not open already add to open
        if not c.isOpen then
          c.isOpen=true
          open[#open+1]=c
        end
        --if was closed, unclose
        if closed[c] then
          closed[c]=nil
        end
      end
    end
    closed[cell]=true
  end

end



local function saveMaze(maze,filename)
  local file=fs.open(filename,"w")
  for y=1,#maze do
    for x=1,#maze[y] do
      file.write(maze[y][x])
    end
    file.write("\n")
  end
  file.close()
end


while true do
    local finalMaze=genKruskal(maze)
    --local finalMaze=genGrowingTree(maze)
    analyze(finalMaze)
    drawMaze(finalMaze,win,false)
    os.pullEvent("monitor_touch")
    drawMaze(finalMaze,win,true)
    os.pullEvent("monitor_touch")
end