TFS Pathing Upgrade

local progress = false
local nodes = {}
local currentNode = 0
local startPos = {}
local endPos = {}
local found = false
local dirListi = {}
local path = {}
local openNodes = true
local complete = false
local count = 30
local timeToPath = 0

local directionsList = {
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, -1},
    {1, -1},
    {1, 1},
    {-1, 1},
}

local function newLuaNode()
    openNodes = true
    currentNode = currentNode + 1
    nodes[currentNode] = {place=currentNode, children = {}, active = 1}
    return nodes[currentNode]
end

local function getWalkCost(fromPos, toPos)
    if(math.abs(fromPos.x - toPos.x) == math.abs(fromPos.y - toPos.y)) then
        return 3
    else
        return 1
    end
end

local function isTileWalkable(pos)
    local canWalk = true
    for a = 0, 255 do
        pos.stackpos = a
        local tileItem = getTileThingByPos(pos)
        if tileItem.itemid > 0 then
            local itemInfo = getItemInfo(tileItem.itemid)
            if itemInfo.blockSolid then
                canWalk = false
            end
        else
            if a == 0 then
                return false
            else
                return canWalk
            end
        end
    end
    return false
end

local function isTileZPath(cid, pos)
    local zPath = false
    local curInfo = getTileInfo({x=pos.x,y=pos.y,z=pos.z,stackpos=0})
    if curInfo then
        local curInfo = curInfo.floorChange
        if curInfo[9] == true then
            local upPos = {x=pos.x,y=pos.y,z=endPos.z,stackpos=0}
            local endInfo = getTileInfo(upPos)
            if endInfo then
                endInfo = endInfo.floorChange
                if endInfo[9] == true then
                    if startPos.z < endPos.z then
                        zPath = endInfo
                    else
                        zPath = curInfo
                    end
                end
            end
        end
    end
    return zPath
end


local function playDirectionList(cid)
    if #dirListi > 0 then
        for a = 1, #dirListi do
            newPos = getPositionByDirection(startPos, dirListi[#dirListi-a+1])
            addEvent(doMoveCreature, a*10, cid, dirListi[#dirListi-a+1])
            doSendMagicEffect(newPos, 55)
            startPos = newPos
        end
    end
    return true
end

local function doDirectionList(cid, lastPos)
    dirListi = {}
    while lastPos.place ~= 1 do
        local oldPos = {x=nodes[lastPos.parent].x,y=nodes[lastPos.parent].y,z=nodes[lastPos.parent].z}
        local newPos = {x=lastPos.x,y=lastPos.y,z=lastPos.z}
        table.insert(dirListi, getDirectionTo(oldPos, newPos, true))
        lastPos = nodes[lastPos.parent]
    end
    --doCreatureSay(cid, table.serialize(dirListi), 1)
    playDirectionList(cid)
    return true
end

local function getTotalCost(cid, node, cost)
    while node.place ~= 1 do
        cost = cost + node.cost
        node = nodes[node.parent]
    end
    return cost
end

local function opposingDir(node)
    local endDir = getDirectionTo(startPos, endPos)
    local nodeDir = getDirectionTo(startPos, node)
    if endDir == 0 and isInArray({2, 4, 5}, nodeDir) then
        return true
    elseif endDir == 1 and isInArray({3, 4, 6}, nodeDir) then
        return true
    elseif endDir == 2 and isInArray({0, 6, 7}, nodeDir) then
        return true
    elseif endDir == 3 and isInArray({1, 5, 7}, nodeDir) then
        return true
    elseif endDir == 4 and isInArray({7, 0, 1}, nodeDir) then
        return true
    elseif endDir == 5 and isInArray({6, 0, 3}, nodeDir) then
        return true
    elseif endDir == 6 and isInArray({5, 2, 1}, nodeDir) then
        return true
    elseif endDir == 7 and isInArray({4, 2, 3}, nodeDir) then
        return true
    end
    return false
end

local function getBestNode()
    local node = false
    local cost = 100000
    for _, tid in ipairs(nodes) do
        if tid.active == 1 then
            local testCost = getTotalCost(0, tid, 0)
            local normDist = getDistanceBetween(startPos, endPos)
            local nodeDist = getDistanceBetween(tid, endPos)
            local diffDist = nodeDist - normDist
            if opposingDir(tid) then diffDist = diffDist + 10 end
            if tid.z ~= endPos.z then diffDist = diffDist + 1000 end
            testCost = testCost+(getDistanceBetween(tid, endPos))+diffDist
            if testCost < cost then
                node = tid
                cost = testCost
            end
        end
    end
    return node
end

local function pathLength(cid, node, countPath)
    while node.place ~= 1 and countPath < 50 do
        countPath = countPath + 1
        node = nodes[node.parent]
    end
    return countPath
end

local function checkNeighbors(cid, currentPos)
    local pos = {}
    while count > 0 and openNodes do
        local currentPos = getBestNode()
        if not currentPos then
            openNodes = false
        end
        if found and currentPos then
            if getTotalCost(cid, found, 0) < (getTotalCost(cid, currentPos, 0)+getDistanceBetween(currentPos, found)) then
                openNodes = false
                currentPos.active = 0
                currentPos = false
                doCreatureSay(cid, "Script still open for a total of "..os.mtime()-timeToPath.." milliseconds.", 1)
            end
        end
        if currentPos then
            count = count - 1
            for a = 1, 8 do
                currentPos.active = 0
                pos.x = currentPos.x - directionsList[a][1]
                pos.y = currentPos.y - directionsList[a][2]
                pos.z = currentPos.z
                pos.cost = getWalkCost(currentPos, pos)
                inRange = true
                if getDistanceBetween(pos, startPos) > 50 or getDistanceBetween(pos, endPos) > 50 then
                    inRange = false
                end

                if inRange and isTileWalkable(pos) then
                    local newcost = getWalkCost(currentPos, pos)
                    local neighbor = false
                    for _, tid in ipairs(nodes) do
                        if tid.x == pos.x and tid.y == pos.y and tid.z == pos.z and tid.parent > 0 then
                            if pos.x == endPos.x and pos.y == endPos.y and pos.z == endPos.z then
                                neighbor = false
                            else
                                neighbor = true
                            end
                            local oldPath = getTotalCost(cid, tid, 0)
                            local newPath = getTotalCost(cid, nodes[currentPos.place], newcost)
                            if oldPath > newPath then
                                tid.parent = currentPos.place
                                tid.cost = newcost
                            end
                        end
                    end
                    if not neighbor then
                        doSendMagicEffect(pos, 56)
                        pos.cost = newcost
                        local neighbor = newLuaNode()
                        neighbor.x = pos.x
                        neighbor.y = pos.y
                        neighbor.z = pos.z
                        neighbor.cost = pos.cost
                        neighbor.parent = currentPos.place
                        table.insert(nodes[currentPos.place].children, neighbor.place)
                        if endPos.z ~= neighbor.z then
                            local zInfo = isTileZPath(cid, neighbor)
                            if zInfo then
                                oldNeighbor = neighbor
                                neighbor = newLuaNode()
                                neighbor.x = pos.x
                                neighbor.y = pos.y
                                neighbor.z = pos.z
                                neighbor.cost = pos.cost
                                neighbor.parent = oldNeighbor.place
                                local zMult = 1
                                if startPos.z > endPos.z then zMult = -1 end
                                if zInfo[1] then
                                    neighbor.y = neighbor.y + zMult
                                elseif zInfo[2] then
                                    neighbor.x = neighbor.x + zMult
                                elseif zInfo[3] then
                                    neighbor.y = neighbor.y - zMult
                                elseif zInfo[4] then
                                    neighbor.x = neighbor.x - zmult
                                end
                                neighbor.z = endPos.z
                                table.insert(nodes[oldNeighbor.place].children, neighbor.place)
                            end
                        elseif neighbor.x == endPos.x and neighbor.y == endPos.y and neighbor.z == endPos.z then
                            if found == false then
                                doCreatureSay(cid, "Found Path after checking "..#nodes.." tiles taking "..os.mtime()-timeToPath.." milliseconds.", 1)
                                timeToPath = os.mtime()
                                found = neighbor
                            end
                        end
                    end
                end
            end
        end
    end
    if found then
        return doDirectionList(cid, found)
    else
        doCreatureSay(cid, "There is no possible path", 1)
    end
    return true
end


function onUse(cid, item, fromPosition, itemEx, toPosition)
    timeToPath = os.mtime()
    progress = true
    nodes = {}
    count = 1000
    usedNodes = {}
    currentNode = 0
    startPos = {}
    found = false
    complete = false
    startPos = getCreaturePosition(cid)
    endPos = toPosition

    local fast = false
    if (isSightClear(startPos, endPos, false)) then
        fast = true
    end

    local startNode = newLuaNode()
    startNode.x = startPos.x
    startNode.y = startPos.y
    startNode.z = startPos.z
    startNode.cost = 0
    startNode.parent = 0

    local pos = {}
    pos.x = startNode.x
    pos.y = startNode.y
    pos.z = startNode.z
    pos.cost = startNode.cost
    pos.place = startNode.place

    checkNeighbors(cid, {x=pos.x,y=pos.y,z=pos.z,cost=pos.cost,place=pos.place})
    return true
end