--
-- DESCRIPTION:  Maze generation program Lua <-> C:
--               Lua - maze generation
--               C   - maze visualization
--      AUTHOR:  Alexander Simakov, <xdr [dot] box [at] Gmail>
--               http://alexander-simakov.blogspot.com/
--     LICENSE:  Public domain
--  HOW-TO RUN:  gcc -o maze_generator -Wall `pkg-config lua5.1 --libs --cflags` maze_generator.c
--              ./maze_generator ./maze_dfs.lua 15 10
--
--               OR
--
--               Uncomment usage example at the end of the file and
--               run as a stand alone Lua program:
--               chmod 755 maze_dfs.lua
--               ./maze_dfs.lua

local Maze = {}

--
-- Public methods
--

-- Create new Maze instance
function Maze:new(width, height)
    local obj = {
        width       = width,
        height      = height,
        cells       = {},
        ascii_board = {},
        visited = 0,
        max = width*height,
    }

    setmetatable(obj, self)
    self.__index = self

    return obj
end

-- Generate maze
function Maze:generate()
    self:_init_cells()
    self:_init_ascii_board()

    self.cells[1][1].left_wall                     = false -- open entry point
    self.cells[self.height][self.width].right_wall = false -- open exit point

    self:_process_neighbor_cells(1, 1);
    local result = {self:_render()}
    return unpack(result)
end

--
-- Private methods
--

-- Close all walls, mark all cells as not visited yet
function Maze:_init_cells()
    self.cells = {}
    for y = 1, self.height do
        self.cells[y] = {}
        for x = 1, self.width do
            self.cells[y][x] = {
                left_wall   = true,
                right_wall  = true,
                top_wall    = true,
                bottom_wall = true,
                is_visited  = false,
            }
        end
    end

    return
end

-- Draw +---+---+ ... +---+
function Maze:_draw_horizontal_bar()
    local line = ''

    for x = 1, self.width do
        line = line .. '+---'
    end
    line = line .. '+'

    return line
end

-- Draw |   |   | ... |   |
function Maze:_draw_vertical_bars()
    local line = ''

    for x = 1, self.width do
        line = line .. '|   '
    end
    line = line .. '|'

    return line
end

-- Draw ascii chess-like board with all walls closed
function Maze:_init_ascii_board()
    self.ascii_board = {}

    for y = 1, self.height do
        local horizontal_bar = self:_string_to_array(self:_draw_horizontal_bar());
        local vertical_bars  = self:_string_to_array(self:_draw_vertical_bars());

        table.insert( self.ascii_board, horizontal_bar )
        table.insert( self.ascii_board, vertical_bars )
    end

    local horizontal_bar = self:_string_to_array(self:_draw_horizontal_bar());
    table.insert( self.ascii_board, horizontal_bar )

    return
end

-- Get cells neighbor to the cell (x,y): left, right, top, bottom
function Maze:_get_neighbor_cells(x, y)
    local neighbor_cells = {}
    local shifts = {
        { x = -1, y =  0 },
        { x =  1, y =  0 },
        { x =  0, y =  1 },
        { x =  0, y = -1 },
    }
    for index, shift in ipairs(shifts) do
        new_x = x + shift.x
        new_y = y + shift.y
        if new_x >= 1 and new_x <= self.width  and
           new_y >= 1 and new_y <= self.height
        then
            table.insert( neighbor_cells, { x = new_x, y = new_y } )
        end
    end
    return neighbor_cells
end
Num = 0
-- Process the cell with all its neighbors in random order

function round(num, idp)
  local mult = 10^(idp or 0)
  return math.floor(num * mult + 0.5) / mult
end

function Maze:_process_neighbor_cells(ox, oy)
    local cellList = { {ox,oy} }
    local Prev = 0
    while #cellList > 0 do
        local cell = table.remove(cellList,1)
        local x,y = cell[1],cell[2]
        local parent = cell[3]
        if not self.cells[y][x].is_visited then
            self.cells[y][x].is_visited = true
            self.visited = self.visited+1
            if Prev ~= round(((self.visited)/(self.max)*100)) then
              Prev = round(((self.visited)/(self.max)*100))
              print(Prev.."%")
              os.queueEvent("randomEvent")
              os.pullEvent()
            end
            local neighbor_cells = self:_shuffle(self:_get_neighbor_cells(x, y))
            if parent then
                if parent.x > x     then     -- open wall with right neighbor
                    self.cells[y][x].right_wall                              = false
                    self.cells[parent.y][parent.x].left_wall   = false
                elseif parent.x < x then     -- open wall with left neighbor
                    self.cells[y][x].left_wall                               = false
                    self.cells[parent.y][parent.x].right_wall  = false
                elseif parent.y > y then     -- open wall with bottom neighbor
                    self.cells[y][x].bottom_wall                             = false
                    self.cells[parent.y][parent.x].top_wall    = false
                elseif parent.y < y then     -- open wall with top neighbor
                    self.cells[y][x].top_wall                                = false
                    self.cells[parent.y][parent.x].bottom_wall = false
                end

            end
            for index, neighbor_cell in ipairs(neighbor_cells) do
                if self.cells[neighbor_cell.y][neighbor_cell.x].is_visited == false then
                    table.insert(cellList,1,{neighbor_cell.x,neighbor_cell.y,{x=x,y=y}})
                end
                --self:_process_neighbor_cells(neighbor_cell.x, neighbor_cell.y)
            end
        end
    end

    return
end


function Maze:_wipe_left_wall(x, y)
    self.ascii_board[y * 2][(x - 1) * 4 + 1] = ' '
    return
end

function Maze:_wipe_right_wall(x, y)
    self.ascii_board[y * 2][x * 4 + 1] = ' '
    return
end

function Maze:_wipe_top_wall(x, y)
    for i = 0, 2 do
        self.ascii_board[(y - 1) * 2 + 1][ (x - 1) * 4 + 2 + i] = ' '
    end
    return
end

function Maze:_wipe_bottom_wall(x, y)
    for i = 0, 2 do
        self.ascii_board[y * 2 + 1][(x - 1) * 4 + 2 + i] = ' '
    end
    return
end

function Maze:_render()
    for y = 1, self.height do
        for x = 1, self.width do
            if self.cells[y][x].left_wall == false then
                self:_wipe_left_wall(x, y)
            end

            if self.cells[y][x].right_wall == false then
                self:_wipe_right_wall(x, y)
            end

            if self.cells[y][x].top_wall == false then
                self:_wipe_top_wall(x, y)
            end

            if self.cells[y][x].bottom_wall == false then
                self:_wipe_bottom_wall(x, y)
            end
        end
    end

    local result = {}
    for index, chars in ipairs(self.ascii_board) do
        result[index] = self:_array_to_string(chars)
    end

    return unpack(result)
end

--
-- Utils
--

-- Generate random number: use either external random
-- number generator or internal - math.random()
function Maze:_rand(max)
    if type(external_rand) ~= "nil" then
        return external_rand(max)
    else
        return math.random(max)
    end
end

-- Shuffle array (external_rand() is external C function)
function Maze:_shuffle(array)
    for i = 1, #array do
        index1 = self:_rand(#array)
        index2 = self:_rand(#array)

        if index1 ~= index2 then
            array[index1], array[index2] = array[index2], array[index1]
        end
    end

    return array
end

-- Split string into array of chars
function Maze:_string_to_array(str)
    local array = {}
    for char in string.gmatch(str, '.') do
        table.insert(array, char)
    end

    return array
end

function Maze:_array_to_string(array)
    return table.concat(array, '')
end

function generate_maze(width, height)
    maze = Maze:new(width, height)
    return maze:generate()
end
--[[
math.randomseed( os.time() )

for i = 1, 10 do
    print(generate_maze(6, 5))
    os.execute('sleep 1')
end
--]]

--Map API. Revised.
--[[
Cheat sheet
createMap(MapName)
loadMap(MapName) -- Load a file into the API
cView(Viewer, Map, xWide, yHigh) -- Create a view point on this map which is x chars wide and y chars high
dView(Viewer) -- delete the viewer
draw(Viewer) -- Draws the viewpoint from the viewer.
editMap(Map, X, Y, Char) -- Edit the map at this point to replace the char there with this char
returnView(Viewer) -- Returns the view to whatever called it. Catch like this Stuff = {returnView("ME!!")} then its loaded into the table "stuff" in your program
moveScreen(Viewer, X, Y) Moves the viewpoint of the viewer to that x, y
saveMap(Map, Location) Saves the loaded map into the location
replaceLine(Map, LineNo, From, To, StuffToReplaceWith) replaceLine("World", 3, 10, 30, "") would replace line 3 at map World chars 10 to 30 with ""
insertLine(Map, y) Makes a new line there
removeLine(Map, y) do I really need to say this?
]]
Maps = {}
Views = {}

function replaceLine(Map, y, from, to, Stuff)
  Maps[Map][y] = string.sub(Maps[Map][y], 1, from)..Stuff..string.sub(Maps[Map][y], to, string.len(Maps[Map][y]))
end

function insertLine(Map, y, data)
  table.insert(Maps[Map], y, data)
end

function removeLine(Map, y)
  table.remove(Maps[Map], y)
end

function loadMap(MapName) -- Loads a map into a table, The info included is loaded into another table
  if not fs.exists(MapName) then error("Please use a map that exists! Use something like Folder/Folder/File") end
  Maps[MapName] = {}
  local MapLoadVari = io.open(MapName, "r")
  local i = 1 -- how many its done.
  local a = 1 -- x len
  local b = 1 -- y len
  for line in MapLoadVari:lines() do
    i = i+1
    Maps[MapName][i] = line
    b = b+1
    if string.len(line) > a then
        a = string.len(line)
    end
  end
  Maps[MapName]["X"] = a
  Maps[MapName]["Y"] = b
end

function createMap(MapName)
  Maps[MapName] = {}
  Maps[MapName][1] = {}
end

function cView(Viewer, Map, xWide, yHigh)
  Views[Viewer] = {}
  Views[Viewer]["Wide"] = xWide
  Views[Viewer]["Map"] = Map
  Views[Viewer]["High"] = yHigh
end

function dView(Name)
  Views[Viewer] = nil
end

function draw(Viewer)
  for n=1,Views[Viewer]["High"] do
    if Maps[Views[Viewer]["Map"]][(Views[Viewer]["Y"]+n-1)] then
       C = 0
      if Views[Viewer]["X"] < 1 then
        C = math.abs(Views[Viewer]["X"])
      end
      local Y = Views[Viewer]["Y"]
      local X = Views[Viewer]["X"]
      local B = (X+Views[Viewer]["Wide"])-string.len(Maps[(Views[Viewer]["Map"])][(Y+n-1)])
      if B < 1 then
        B = 0
      end
      Views[Viewer][n] = string.rep(" ", C)..string.sub(Maps[(Views[Viewer]["Map"])][(Y+n-1)], X+C+1, X+Views[Viewer]["Wide"])..string.rep(" ", B)
    else
      Views[Viewer][n] = string.rep(" ", Views[Viewer]["Wide"])
    end
  end
end

function editMap(Map, X, Y, Char)
  Maps[Map][Y] = string.sub(Maps[Map][Y], 1, X-1)..Char..string.sub(Maps[Map][Y], X+1, string.len(Maps[Map][Y]))
end

function returnView(Viewer)
  local Sec = {}
  for n=1,Views[Viewer]["High"] do
    Sec[n] = Views[Viewer][n]
  end
  return unpack(Sec)
end

function returnChar(Map, x, y)
  if x*y > 0 and Maps[Map][y] then
    if string.sub(Maps[Map][y], x, x) ~= "" then
      return string.sub(Maps[Map][y], x, x)
    end
  end
  return false
end

function moveScreen(Viewer, xAmount, yAmount) -- Was going to add in checking if bla bla exists but..
  Views[Viewer]["X"] = xAmount
  Views[Viewer]["Y"] = yAmount
end

function saveMap(Map, Location)
  local Beauty = io.open(Location, "w")
  for n=1,#Maps[Map] do
    Beauty:write(Maps[Map][n])
    if #Maps[Map]+1 then
      Beauty:write("\n")
    end
  end
  Beauty:close()
end

function getSize(Map)
  return string.len(Maps[Map][1]), #Maps[Map]
end
--[[
Cheat sheet
createMap(MapName)
loadMap(MapName) -- Load a file into the API
cView(Viewer, Map, xWide, yHigh) -- Create a view point on this map which is x chars wide and y chars high
dView(Viewer) -- delete the viewer
draw(Viewer) -- Draws the viewpoint from the viewer.
editMap(Map, X, Y, Char) -- Edit the map at this point to replace the char there with this char
returnView(Viewer) -- Returns the view to whatever called it. Catch like this Stuff = {returnView("ME!!")} then its loaded into the table "stuff" in your program
moveScreen(Viewer, X, Y) Moves the viewpoint of the viewer to that x, y
saveMap(Map, Location) Saves the loaded map into the location
replaceLine(Map, LineNo, From, To, StuffToReplaceWith) replaceLine("World", 3, 10, 30, "") would replace line 3 at map World chars 10 to 30 with ""
insertLine(Map, y, data) Makes a new line there
removeLine(Map, y) do I really need to say this?
getSize(Map)
returnChar(Map, X, Y) returns the char there
]]

Stuff = {...}
if Stuff[1] and tonumber(Stuff[2]) then
  Maps["Maze"] = {generate_maze(tonumber(Stuff[1]), tonumber(Stuff[2]))}
else
  Maps["Maze"] = {generate_maze(20, 20)}
end
if Stuff[3] then
  math.randomseed(tonumber(Stuff[3]))
end
cView("Main", "Maze", term.getSize())
local xx, yy = term.getSize("Maze")
local x = 1
local y = 2
local Char = ">"
local xx = math.floor(xx/2)
local yy = math.floor(yy/2)
moveScreen("Main", x-xx, y-yy)
draw("Main")
local G = {returnView("Main")}
for n=1,#G do
  term.setCursorPos(1,n)
  term.write(G[n])
end
term.setCursorPos(xx, yy+1)
term.write(Char)
function safe(x, y)
  print(x.." "..y)
  local B = returnChar("Maze", x, y)
  if B then
    if B ~= "-" and B ~= "+" and B ~= "|" then
      return true
    end
  end
  return false
end

while true do
  event,param1 = os.pullEvent()
  if event == "char" then
    if param1 == "w" then
      if safe(x, y-1) then
        y = y-1
        Char = "^"
      end
    elseif param1 == "s" then
      if safe(x, y+1) then
        y = y+1
        Char = "v"
      end
    elseif param1 == "a" then
      if safe(x-1, y) then
        x = x-1
        Char = "<"
      end
    elseif param1 == "d" then
      if safe(x+1, y) then
        x = x+1
        Char = ">"
      end
    end
    moveScreen("Main", x-xx, y-yy)
    draw("Main")
    term.setCursorPos(1,1)
    local G = {returnView("Main")}
    for n=1,#G do
      term.setCursorPos(1,n)
      term.write(G[n])
    end
    term.setCursorPos(xx, yy+1)
    term.write(Char)
  end
end