3opt api

-- [[ API file ]] --
local w,h = term.getSize()

function calculateDistance(tNode1,tNode2)
    local turnCost = 0
    local deltaY,deltaZ
    local y1 = tNode1[2]
    local z1 = tNode1[3]
    local y2 = tNode2[2]
    local z2 = tNode2[3]

    deltaZ = z2-z1
    deltaY = y2-y1

    if deltaZ == 0 or deltaY == 0 then
        turnCost = 0
    else
        turnCost = 1
    end

    return math.abs(deltaZ) + math.abs(deltaY) + turnCost
    --return math.sqrt( (z2-z1)^2 + (y2-y1)^2 )
end

function twoOptSwap(route, i, k)
    local new_route = {}
    for c = 1,i-1 do
        table.insert(new_route,route[c])
    end
    for c = k,i,-1 do
        table.insert(new_route,route[c])
    end
    for c = k+1,#route do
        table.insert(new_route,route[c])
    end
    return new_route
end

function calculateTotalDistance(route)
    local total = 0
    for i = 1,#route-1 do
        total = total + calculateDistance(route[i],route[i+1])
    end
    return total
end

function display(route,distance)
    local l,h = term.getSize()
    shell.run("clear")

    for i = 1,#route-1 do
        paintutils.drawLine(route[i][2],route[i][3],route[i+1][2],route[i+1][3],colors.lime)
    end
    for i,coord in pairs(route) do
        term.setBackgroundColor(colors.yellow)
        term.setTextColor(colors.magenta)
        term.setCursorPos(coord[2]+1,coord[3]+1)
        term.write(string.char(i+64))
    end
    term.setBackgroundColor(colors.black)
    term.setTextColor(colors.white)
    term.setCursorPos(1,h)
    term.write(distance)
end


--[[nodes = {}
local x= 12
for y = 0,finaly do
    for z = 0,finalz do
        local id = getBlockId(x,y,z)
        if id and id > 0 then
            table.insert(nodes,{x,y,z})
        end
    end
end
]]


-- [[ Main File ]] --

route = {}
route[1] = {1,28,3}
route[2] = {1,36,13}
route[3] = {1,20,8}
route[4] = {1,8,8}
route[5] = {1,44,5}
route[6] = {1,32,13}
route[7] = {1,20,17}
--route[8] = {1,28,3}

route2 = {
{6,5,1},
{6,1,2},
{6,1,5},
{6,2,1},
{6,2,6},
{6,3,1},
{6,3,6},
{6,4,1},
{6,4,6},
{6,5,6},
{6,6,2},
{6,6,5},
}

for i = 1,#route2 do
    route2[i][2] = (route2[i][2]/6)*w
    route2[i][3] = (route2[i][3]/6)*h
end

function nearest_neighbor(existing_route)
    local best_distance = 10000
    local best_route = { route[1] }

    for i = 2,#existing_route-1 do
        for k = i+1,#existing_route do
            local new_distance = calculateDistance(existing_route[i],existing_route[k])
            if new_distance < best_distance then
                best_distance = new_distance
                best_route[i+1] = existing_route[k]
            end
        end
    end

    return best_route,best_distance
end


function tsp_algorithm(existing_route)
    local improve = 0
    while improve < 3 do
        local best_distance = calculateTotalDistance(existing_route)
        for i = 2,#existing_route-1 do
            for k = i + 1, #existing_route do
                new_route = twoOptSwap(existing_route, i, k)
                new_distance = calculateTotalDistance(new_route)
                if new_distance < best_distance then
                    improve = 0
                    existing_route = new_route
                    best_distance = calculateTotalDistance(existing_route)
                    display(existing_route,best_distance)
                    sleep(0)
                end
            end
        end
        improve = improve + 1
    end
    return existing_route, best_distance
end

--local best_route,best_distance = tsp_algorithm(nodes)

--display(best_route,best_distance)

--term.setCursorPos(1,h-#best_route)
--for i,v in pairs(best_route) do
    --print(i," ",v[2]," ",v[3])
--end


--textutils.pagedPrint(textutils.serialize(best_route))