A* Pathfinder in Pure Lua.

-------------------------------------------------------------------------------------------
Vector2 = {}

local v2Meta = {}

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)
        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

-------------------------------------------------------------------------------------------

local maze =
{
    "##########################################";
    "# # #       #     #       #         #   #";
    "# # ### ### # ### ### ### ### # ### # # #";
    "#       #   #   #   # # #   # # # #   # #";
    "######### ##### ### # # ### ### # ##### #";
    "#       # #       #   #   #     #   #   #";
    "### ##### ####### ####### ####### ### ###";
    "# #     #     #   #           #         #";
    "# # ### ##### # ##### ##### # # #########";
    "# # #       #   #     #     # #         #";
    "# # # ### ####### ########### ######### #";
    "#   #   # #               #     #   #   #";
    "# ##### # # ############# ##### ### # ###";
    "# #     # #         # # #     #     #   #";
    "### ##### ######### # # ##### ######### #";
    "#   #   #   #               #       #   #";
    "# ### # ##### ##################### # ###";
    "#     #       #   # #         # #   #   #";
    "# ############# # # ######### # # ### ###";
    "# #       #     #               #   #   #";
    "S # ##### # ################### ### # ###";
    "# #     #   #     #   #       # #   #   #";
    "# ##### ##### ### # # # ##### # # ##### E";
    "#       #       #   #       #   #       #";
    "#########################################";
}


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

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

local function aStar(start_,end_)
    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
        if not closedCache[x][y] then
            closedCache[x][y] = true
        end
    end


    addToClosedList(start_)

    local function getOpenList(pos)
        local openList = {}
        local function processCell(cx,cy)
            if data[cx] then
                local cell = data[cx][cy]
                if cell and cell == " " then
                    if not closedCache[cx] then
                        closedCache[cx] = {}
                    end
                    if not closedCache[cx][cy] then
                        local openPos = Vector2.new(cx,cy)
                        table.insert(openList,openPos)
                    end
                end
            end
        end
        for x = -1,1 do
            for y = -1,1 do
                local isSame = (x+y == 0)
                local isDiagonal = (abs(x)+abs(y) == 2)
                if not (isSame or isDiagonal) then
                    local cx = pos.X + x
                    local cy = pos.Y + y
                    processCell(cx,cy)
                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(end_)
                    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 currentStartPos = startPos

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 arrowKeys =
{
    ["-1, 0"] = "<";
    ["1, 0"] = ">";
    ["0, -1"] = "^";
    ["0, 1"] = "v";
}

local function printMaze(closedList)
    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
            local nextNode = closedList[index+1]
            if nextNode then
                local movement = (nextNode-node).unit
                dataCopy[node.X][node.Y] = arrowKeys[tostring(movement)]
            end
            --dataCopy[node.X][node.Y] = string.char(165)

        end
    end

    local finalData = {}

    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
                char = " "
            end
            finalData[x][y] = char
        end
    end

    for _,column in pairs(finalData) do
        print(table.concat(column,""))
    end
    print()
end

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

while findingPath do
    local foundPath,nodes = aStar(currentStartPos,endPos)
    if foundPath then
        findingPath = false
        printMaze(nodes)
    else
        block(nodes[#nodes])
    end
end