Maze Generator/Solver in pure Lua

-------------------------------------------------------------------------------------------
-- Vector2

Vector2 = {}
local v2Meta = {}

local function isVector2(obj)
    local success,hasValues = pcall(function ()
        return obj.X + obj.Y + obj.magnitude
    end)
    return success
end

function v2Meta.__tostring(v2)
    return v2.X..", "..v2.Y
end

function v2Meta.__eq(self,other)
    return self.X == other.X and self.Y == other.Y
end

local v2Methods =
{
    add = "+";
    sub = "-";
    mul = "*";
    div = "/";
}

local v2Format = "return Vector2.new(%d%s%d,%d%s%d)"

for key,met in pairs(v2Methods) do
    v2Meta["__"..key] = function (self,other)
        if type(other) == "number" then
            other = Vector2.new(other,other)
        end
        local x = self.X
        local y = self.Y
        local ox = other.X
        local oy = other.Y
        local result = v2Format:format(x,met,ox,y,met,oy)
        return loadstring(result)()
    end
end

function Vector2.new(x,y)
    local x = tonumber(x) and x or 0
    local y = tonumber(y) and y or 0
    local vec =
    {
        X = x;
        Y = y;
        magnitude = math.sqrt(x^2+y^2);
    }
    if vec.magnitude ~= 1 and vec.magnitude ~= 0 then
        vec.unit = Vector2.new(x/vec.magnitude,y/vec.magnitude)
    else
        vec.unit = vec
    end
    setmetatable(vec,v2Meta)
    return vec

end

-------------------------------------------------------------------------------------------
-- Generate Random Maze

print("Generating Maze...")

local maze = {}
local width = 93
local height = 50
local cells = {}

if (width%2 == 0) then
    print("\t| Warning: Maze Width should be an odd number.")
    print("\t|          Changing from ".. width .." to ".. width+1 ..".")
    width = width + 1
end.

if (height%2 == 0) then
    print("\t| Warning: Maze Height should be an odd number.")
    print("\t|          Changing from ".. height .." to ".. height+1 ..".")
    height = height + 1
end

for x = 1,width do
    cells[x] = {}
    for y = 1,height do
        cells[x][y] = "#"
    end
end

local visited = {}

local function visitCell(x,y)
    if not visited[x] then
        visited[x] = {}
    end
    visited[x][y] = true
    cells[x][y] = " "
end

local function didVisit(x,y)
    return (visited[x] and visited[x][y])
end

local function inRange(pos)
    if pos.X > 1 and pos.Y > 1 then
        if pos.X < width and pos.Y < height then
            return true
        end
    end
    return false
end

local function getUnvisitedNeighbors(x,y)
    local neighbors = {}
    for ox = -1,1 do
        for oy = -1,1 do
            local isSame = (ox+oy==0)
            local isDiag = (math.abs(ox)+math.abs(oy))==2
            local cx = x+ox
            local cy = y+oy
            if not (isSame or isDiag) then
                cx = x+(ox*2)
                cy = y+(oy*2)
                if cells[cx] and cells[cx][cy] and not didVisit(cx,cy) then
                    local pos = Vector2.new(cx,cy)
                    table.insert(neighbors,pos)
                end
            end
        end
    end
    return neighbors
end

local activeIndex = 0
local backtrace = {}

local function depthSearch(currentCell)
    local x,y = currentCell.X,currentCell.Y
    visitCell(x,y)
    local n = getUnvisitedNeighbors(x,y)
    if #n > 0 then
        activeIndex = activeIndex + 1
        backtrace[activeIndex] = currentCell
        local unvis = n[math.random(1,#n)]
        -- break down wall
        local wallBetween = currentCell + (unvis-currentCell)/2
        local wx,wy = wallBetween.X,wallBetween.Y
        visitCell(wx,wy)
        depthSearch(unvis)
    else
        activeIndex = activeIndex - 1
        if activeIndex > 0 then
            depthSearch(backtrace[activeIndex])
        end
    end
end

local startPos = Vector2.new(2,2)
local endPos = Vector2.new(width-1,height)

cells[1][2] = "S"
cells[width-1][height] = "E"
cells[2][2] = " "
cells[width-1][height-1] = " "

depthSearch(Vector2.new(2,2))

for y = 1,height do
    local s = ""
    for x = 1,width do
        s = s .. cells[x][y]
    end
    table.insert(maze,s)
end

---------------------------------------------------------------------------------------------
-- A* Maze Solver

print("Solving Maze...")

local data = {}
local startPos
local endPos
local abs = math.abs
local showBlocked = true

for y,row in pairs(maze) do
    local x = 0
    for char in row:gmatch(".") do
        x = x + 1
        if not data[x] then
            data[x] = {}
        end
        if char == "S" then
            startPos = Vector2.new(x,y)
            data[x][y] = " "
        elseif char == "E" then
            endPos = Vector2.new(x,y)
            data[x][y] = " "
        else
            data[x][y] = char
        end
    end
end

if not startPos then
    error("FATAL ERROR: START POS NOT DEFINED IN MAZE",2)
end

if not endPos then
    error("FATAL ERROR: END POS NOT DEFINED IN MAZE",2)
end

local function surroundingCells(x,y)
    if y == nil then
        -- hack
        x,y = x.X,x.Y
    end
    local cells = {}
    for ox = -1,1 do
        for oy = -1,1 do
            local cx = x+ox
            local cy = y+oy
            local isSame = (ox+oy) == 0
            local isDiag = (abs(ox)+abs(oy)) == 2
            if not (isSame or isDiag) then
                local row = data[cx]
                if row then
                    local cell = data[cx][cy]
                    if cell then
                        local data =
                        {
                            Coord = Vector2.new(cx,cy);
                            Cell = cell;
                        }
                        table.insert(cells,data)
                    end
                end
            end
        end
    end
    local currentKey
    return function ()
        local key,value = next(cells,currentKey)
        if key and value then
            currentKey = key
            return value.Coord,value.Cell
        end
    end
end

local function aStar(s,e)
    local closedCache = {}
    local closedList = {}

    local function addToClosedList(pos)
        closedList[#closedList+1] = pos
        local x,y = pos.X,pos.Y
        if not closedCache[x] then
            closedCache[x] = {}
        end
        closedCache[x][y] = true
    end


    addToClosedList(s)

    local function getOpenList(pos)
        local openList = {}
        for openPos,cell in surroundingCells(pos) do
            if cell == " " or cell == "E" or cell == "S" then
                if not closedCache[openPos.X] then
                    closedCache[openPos.X] = {}
                end
                if not closedCache[openPos.X][openPos.Y] then
                    openList[#openList+1] = openPos
                end
            end
        end
        return openList
    end

    local foundPath = false

    while not foundPath do
        local g = #closedList-1
        local lastPos = closedList[g+1]
        local openList = getOpenList(lastPos)
        if #openList > 0 then
            local lowestF,bestPos = math.huge,Vector2.new()
            for _,pos in pairs(openList) do
                local h = (endPos-pos).magnitude
                if h == 0 then
                    addToClosedList(e)
                    foundPath = true
                    print("Path found!")
                    break
                end
                local f = g + h
                if f < lowestF then
                    lowestF = f
                    bestPos = pos
                end
            end
            if not foundPath then
                addToClosedList(bestPos)
            end
        else
            break
        end
    end

    return foundPath,closedList
end

local findingPath = true

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

local function printMaze(closedList,impossible)
    print()
    local dataCopy = deepCopy(data)

    local startPos = closedList[1]
    local endPos = closedList[#closedList]
    for index,node in pairs(closedList) do
        if startPos == node then
            dataCopy[node.X][node.Y] = "S"
        elseif endPos == node then
            dataCopy[node.X][node.Y] = "E"
        else
            dataCopy[node.X][node.Y] = string.char(165)
        end
    end

    local finalData = {}
    local blockedNodes = 0
    for y,row in pairs(dataCopy) do
        for x,char in pairs(row) do
            if not finalData[x] then
                finalData[x] = {}
            end
            if char == "B" then
                blockedNodes = blockedNodes + 1
                char = ((showBlocked or impossible) and "/" or " ")
            end
            finalData[x][y] = char
        end
    end

    for _,column in pairs(finalData) do
        print(table.concat(column,""))
    end
    if not impossible then
        print()
        print("We had to block "..blockedNodes.." nodes to find a path")
        print()
    end
end

local function block(node)
    data[node.X][node.Y] = "B"
end

local function checkIfImpossible()
    for pos,cell in surroundingCells(startPos) do
        if cell == " " then
            return false
        end
    end
    return true
end

local backIterates = 0

local function backIterateBlock(nodes)
    while true do
        local node = nodes[#nodes]
        local openCells = 0
        for pos,cell in surroundingCells(node) do
            if cell == " " then
                openCells = openCells + 1
            end
        end
        if openCells ~= 1 then
            backIterates = backIterates + 1
            break
        else
            block(node)
            table.remove(nodes,#nodes)
        end
    end
end

while true do
    local foundPath,nodes = aStar(startPos,endPos)
    if foundPath then
        printMaze(nodes)
        print("It required "..backIterates.." A* scans to solve.")
        break
    else
        local isImpossible = checkIfImpossible()
        if isImpossible then
            print("IMPOSSIBLE TO SOLVE")
            printMaze({},true)
            break
        else
            backIterateBlock(nodes)
        end
    end
end