CCTweaked Graph: unweighted, undirected

turtle_direction = nil
-- helper function to print date and time to a file
-- format: "[mm-dd-yyyy | hr:min:sec] "
output_file = "graph_error_log.txt"
local function write_date_time(file_name)
    local file = io.open(file_name, "a")
    -- Dividing by 1000 converts it from milliseconds to seconds.
    --local time = os.epoch("local") / 1000
    --local time_table = os.date("*t", time)
    --file:write("[" .. time_table.month .. "-" .. time_table.day .. "-" .. time_table.year .. " | ")
    --file:write(time_table.hour .. ":" .. time_table.minute .. ":" .. time_table.sec .. "] ")
    file:write("[DAY " .. os.day("ingame") .. "] ")
    file:close()
end
-- initialize Graph metatable (sort of a class)
-- Graph is undirected and unweighted using an adjacency list.
-- vertices store (x, y, z) coordinates and block data
-- block data is in the format of a table returned by the turtle.inspect() function
Graph = {}

-- below are some Graph functions
-- graph initialization function
function Graph:initialize_graph()
    self.vertices = {}
end
-- given x, y, z coordinates returns formatted string for vertex key
local function create_vertex_key(x, y, z)
    return string.format("%d,%d,%d", x, y, z)
end
-- adds a vertex given x, y, z coordinates and blockdata
-- returns true if worked, nil otherwise
function Graph:add_vertex(x, y, z, data)
    local key = create_vertex_key(x, y, z)
    if not self.vertices[key] then
        self.vertices[key] = {
            x = x,
            y = y,
            z = z,
            data = data,
            edges = {}
        }
        return true
    else
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Attemped to add already existing vertex: (" .. x .. ", " .. y .. ", " .. z .. ")\n")
        file:write("-> existing block: {" .. self.vertices[key].data.name .. "}\n")
        file:write("-> new? block: {" .. data.name .. "}\n")
        file:close()
        return nil
    end
end
-- removes a vertex given x, y, z coordinates
-- returns true if worked, nil otherwise
function Graph:remove_vertex(x, y, z)
    local key = create_vertex_key(x, y, z)
    if self.vertices[key] then
        -- remove edges connected to this vertex
        for adjacent in pairs(self.vertices[key].edges) do
            self.vertices[adjacent].edges[key] = nil
        end
        -- now remove self from graph's vertices list
        self.vertices[key] = nil
        return true
    else
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Attemped to remove vertex that does not exist: (" .. key .. ")\n")
        file:close()
        return nil
    end
end
-- add an edge given two sets of (x, y, z) coordinates
-- returns true if worked, nil otherwise
function Graph:add_edge(x1, y1, z1, x2, y2, z2)
    local key1 = create_vertex_key(x1, y1, z1)
    local key2 = create_vertex_key(x2, y2, z2)
    if self.vertices[key1] and self.vertices[key2] then
        self.vertices[key1].edges[key2] = true
        self.vertices[key2].edges[key1] = true
        return true
    else
        -- one or both of the vertices does not exist
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Attemped to add edge between two vertices. One or both does not exist\n")
        file:write("-> key1: (" .. key1 .. ")\n")
        file:write("-> key2: (" .. key2 .. ")\n")
        if not self.vertices[key1] then
            file:write("-> key1 does not exist\n")
        end
        if not self.vertices[key2] then
            file:write("-> key2 does not exist\n")
        end
        file:close()
        return nil
    end
end
-- removes an edge given two sets of (x, y, z) coordinates
-- returns true if worked, nil otherwise
function Graph:remove_edge(x1, y1, z1, x2, y2, z2)
    local key1 = create_vertex_key(x1, y1, z1)
    local key2 = create_vertex_key(x2, y2, z2)
    if self.vertices[key1] and self.vertices[key2] then
        self.vertices[key1].edges[key2] = nil
        self.vertices[key2].edges[key1] = nil
        return true
    else
        -- one or both of the vertices does not exist
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Attemped to remove edge between two vertices. One or both does not exist\n")
        file:write("-> key1: (" .. key1 .. ")\n")
        file:write("-> key2: (" .. key2 .. ")\n")
        if not self.vertices[key1] then
            file:write("-> key1 does not exist\n")
        end
        if not self.vertices[key2] then
            file:write("-> key2 does not exist\n")
        end
        file:close()
        return nil
    end
end
-- estimate distance between two points using manhattan distance
-- used for the a* algorithm
local function manhattan_distance(x1, y1, z1, x2, y2, z2)
    return math.abs(x2 - x1) + math.abs(y2 - y1) + math.abs(z2 - z1)
end
function Graph:a_star(start_x, start_y, start_z, goal_x, goal_y, goal_z)
    local start_key = create_vertex_key(start_x, start_y, start_z)
    local goal_key = create_vertex_key(goal_x, goal_y, goal_z)

    -- check to make sure start and goal vertices exist
    if not self.vertices[start_key] or self.vertices[goal_key] then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Attemped to find distance between two vertices. One or both does not exist\n")
        file:write("-> start_key: (" .. start_key .. ")\n")
        file:write("-> goal_key: (" .. goal_key .. ")\n")
        if not self.vertices[start_key] then
            file:write("-> start_key does not exist\n")
        end
        if not self.vertices[goal_key] then
            file:write("-> goal_key does not exist\n")
        end
        file:close()
        return nil
    end
    -- at this point we know both vertices exist
    local open_set = { [start_key] = true }
    local came_from = {}
    local g_score = { [start_key] = 0 }
    local f_score = { [start_key] = manhattan_distance(start_x, start_y, start_z, goal_x, goal_y, goal_z) }

    while next(open_set) do
        -- Find the node in open_set with the lowest f_score
        local current_key, current_f = nil, math.huge
        for key in pairs(open_set) do
            if f_score[key] and f_score[key] < current_f then
                current_key, current_f = key, f_score[key]
            end
        end

        -- Check if we reached the goal
        if current_key == goal_key then
            -- Reconstruct the path
            local path = {}
            while current_key do
                table.insert(path, 1, current_key)
                current_key = came_from[current_key]
            end
            return path
        end

        open_set[current_key] = nil

        local current_vertex = self.vertices[current_key]
        for neighbor_key in pairs(current_vertex.edges) do
            local neighbor_vertex = self.vertices[neighbor_key]
            local non_solid_block = false
            if neighbor_vertex.data.name == "minecraft:air" then
                non_solid_block = true
            elseif neighbor_vertex.data.name == "minecraft:water" then
                non_solid_block = true
            elseif neighbor_vertex.data.name == "minecraft:lava" then
                non_solid_block = true
            end
            if non_solid_block then
                local tentative_g_score = g_score[current_key] + 1 -- All edges have the same weight of 1

                if not g_score[neighbor_key] or tentative_g_score < g_score[neighbor_key] then
                    came_from[neighbor_key] = current_key
                    g_score[neighbor_key] = tentative_g_score
                    f_score[neighbor_key] = tentative_g_score + manhattan_distance(
                        self.vertices[neighbor_key].x, self.vertices[neighbor_key].y, self.vertices[neighbor_key].z,
                        goal_x, goal_y, goal_z
                    )
                    open_set[neighbor_key] = true
                end
            end
        end
    end
    return nil -- No path found
end
--wrapper function for gps.locate()
--returns x, y, z if successful
--returns nil, nil, nil if unsuccesful and writes error to output_file
function locate()
    local x = nil
    local y = nil
    local z = nil
    x, y, z = gps.locate()
    if not x or not y or not z then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Failed to locate turtle. Check GPS constellation\n")
        file:close()
        return nil, nil, nil
    end
    return x, y, z
end
--wrapper function for turtle.inspect and its variations
--returns the result of the turtle.inspect function and also saves the data to the graph
--direction is "forward", "up", or "down"
function inspect(direction, graph)
    local inspect_success = nil
    local inspect_data = nil
    local inspect_x, inspect_y, inspect_z = nil
    local turtle_x, turtle_y, turtle_z = locate()
    if not turtle_x or not turtle_y or not turtle_z then
        return nil, nil
    end
    if direction == "forward" then
        inspect_success, inspect_data = turtle.inspect()
        if turtle_direction == "south" then
            inspect_x = turtle_x
            inspect_y = turtle_y
            inspect_z = turtle_z + 1
        elseif turtle_direction == "north" then
            inspect_x = turtle_x
            inspect_y = turtle_y
            inspect_z = turtle_z - 1
        elseif turtle_direction == "east" then
            inspect_x = turtle_x + 1
            inspect_y = turtle_y
            inspect_z = turtle_z
        elseif turtle_direction == "west" then
            inspect_x = turtle_x - 1
            inspect_y = turtle_y
            inspect_z = turtle_z
        end
    elseif direction == "up" then
        inspect_success, inspect_data = turtle.inspectUp()
        inspect_x = turtle_x
        inspect_y = turtle_y + 1
        inspect_z = turtle_z
    elseif direction == "down" then
        inspect_success, inspect_data = turtle.inspectDown()
        inspect_x = turtle_x
        inspect_y = turtle_y - 1
        inspect_z = turtle_z
    end
    --block other than air
    if inspect_success then
        graph:add_vertex(inspect_x, inspect_y, inspect_z, inspect_data)
    else -- air block
        inspect_data = {
            ["name"] = "minecraft:air",
            ["tags"] = nil,
            ["state"] = nil
        }
        graph:add_vertex(inspect_x, inspect_y, inspect_z, inspect_data)
    end
    return inspect_success, inspect_data
end

--function to check for fuel
--refuels if out of fuel
--returns true if turtle has fuel or was able to refuel
--shutsdown the computer if out of fuel
function checkAndRefuel()
    if turtle.getFuelLevel() == 0 then
        -- Select the slot with coal
        for slot = 1, 16 do
            if turtle.getItemCount(slot) > 0 then
                turtle.select(slot)
                if turtle.refuel(1) then
                    return true
                end
            end
        end
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("No fuel found!\n")
        file:close()
        os.shutdown()
        return false
    end
    return true
end

--wrapper function for turtle.forward() and the other movement functions
--direction can be "forward", "back", "up", or "down"
--returns true or false if the move was successfully completed
--if turtle could not move, writes reason it could not move to output_file
function move(direction)
    if not checkAndRefuel() then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Failed to move due to lack of fuel\n")
        file:close()
        return false
    end
    local move_success, move_data = nil
    if direction == "forward" then
        move_success, move_data = turtle.forward()
    elseif direction == "back" then
        move_success, move_data = turtle.back()
    elseif direction == "up" then
        move_success, move_data = turtle.up()
    elseif direction == "down" then
        move_success, move_data = turtle.down()
    end
    if not move_success then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Failed to move due to:\n")
        file:write("-> " .. move_date .. "\n")
        file:close()
    end
    return move_success
end

--wrapper function for turtle.turnLeft() and turtle.turnRight()
--stores current direction in global variable turtle_direction
--returns true or false if the turtle could successfully turn
--if the turtle could not turn then writes the reason why to output_file
--direction can be "left" or "right"
--if turtle_direction is nil, does not modify it.
function turn(direction)
    local turn_success = nil
    local turn_data = nil
    if direction == "left" then
        turn_success, turn_data = turtle.turnLeft()
        if turn_success then
            if turtle_direction == "north" then
                turtle_direction = "west"
            elseif turtle_direction == "west" then
                turtle_direction = "south"
            elseif turtle_direction == "south" then
                turtle_direction = "east"
            elseif turtle_direction == "east" then
                turtle_direction = "north"
            end
        end
    elseif direction == "right" then
        turn_success, turn_data = turtle.turnRight()
        if turn_success then
            if turtle_direction == "north" then
                turtle_direction = "east"
            elseif turtle_direction == "east" then
                turtle_direction = "south"
            elseif turtle_direction == "south" then
                turtle_direction = "west"
            elseif turtle_direction == "west" then
                turtle_direction = "north"
            end
        end
    end
    if not turn_success then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Failed to turn\n")
        file:write("-> direction: " .. direction .. "\n")
        file:write("-> reason: " .. turn_data .. "\n")
        file:close()
        return false
    end
    return true
end

--determines what direction the turtle is facing
--modifies the global turtle_direction variable
--returns true or false if successful
--sets global turtle_direction variable to nil if any issues occur
--does not preserve direction the turtle was facing from before this function was called
function determine_direction()
    turtle_direction = nil
    local x1, y1, z1 = locate()
    local x2, y2, z2
    local move_direction
    if not x1 or not y1 or not z1 then
        return false
    end
    --test which direction we are able to move in
    local turn_left_count = 0
    while turtle.detect() do
        turn_left_count = turn_left_count + 1
        if not turn("left") then
            return false
        end
        if turn_left_count > 3 then
            --no air blocks immediately around the turtle
            write_date_time(output_file)
            local file = io.open(output_file, "a")
            file:write("Unable to determine direction in determine_direction()\n")
            file:write("-> no air blocks surrounding the turtle\n")
            file:close()
            return false
        end
    end
    if move("forward") then
        x2, y2, z2 = locate()
        if not x2 or not y2 or not z2 then
            turtle_direction = nil
            return false
        end
        if not move("back") then
            write_date_time(output_file)
            local file = io.open(output_file, "a")
            file:write("Failed to correct position after calling determine_direction()\n")
            file:close()
            return false
        end
    else
        --unable to move
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Unable to determine direction in determine_direction()\n")
        file:write("-> not able to move AFTER determining valid move direction\n")
        file:close()
        return false
    end
    -- successfully completed the moves, now we can calculate the direction
    if z2 > z1 then
        turtle_direction = "south"
    elseif z1 < z2 then
        turtle_direction = "north"
    elseif x2 > x1 then
        turtle_direction = "east"
    elseif x1 < x2 then
        turtle_direction = "west"
    else
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Unable to determine direction in determine_direction()\n")
        file:write("-> turtle was unable to move for some unknown reason\n")
        file:close()
        return false
    end
    return true
end

--creates a .nft image file for 1 layer of the graph
--input is the graph and the y value for the layer to be generated
--outputs to the graph_image.nft file
--returns true or false if successful
function generate_graph_image(graph, y)
    local monitor = peripheral.find("monitor")
    local width, height = monitor.getSize()
    local center_x, _, center_z = locate()
    if not center_x or not center_z then
        write_date_time(output_file)
        local file = io.open(output_file, "a")
        file:write("Unable to locate turtle during generate_graph_image()\n")
        file:close()
        return false
    end
    local image_file = io.open("graph_image.nft", "w")
    local start_image_x, start_image_z
    local end_image_x, end_image_z
    start_image_x = center_x - math.floor(width / 2)
    start_image_z = center_z - math.floor(height / 2)
    end_image_x = start_image_x + width
    end_image_z = start_image_z + height
    local key = nil
    local block = nil
    for h = start_image_z, end_image_z do
        for w = start_image_x, end_image_x do
            key = create_vertex_key(w, y, h)
            if graph.vertices[key] then
                --we have data on this block
                block = graph.vertices[key]
                if block.data.name == "minecraft:air" then
                    image_file:write("8")
                elseif block.data.name == "minecraft:lava" then
                    image_file:write("e")
                elseif block.data.name == "minecraft:water" then
                    image_file:write("b")
                else
                    image_file:write("7")
                end
            else
                image_file:write("0")
            end
        end
        image_file:write("\n")
    end
    image_file:close()
    return true
end

--example usage of the graph and also the graph image
local graph = {}
setmetatable(graph, {__index = Graph})
graph:initialize_graph()

local block_types = {"minecraft:air", "minecraft:stone", "minecraft:lava", "minecraft:water"}
math.randomseed(os.time())

-- generate 60 x 40 vertices
local block_data_file = io.open("block_data_file", "w")
local temp_x, temp_y, temp_z = locate()
if not temp_x or not temp_y or not temp_z then
    block_data_file:close()
    return
end

for i = temp_x - 30, temp_x + 30 do
    for j = temp_z - 20, temp_z + 20 do
        local block_type = block_types[math.random(#block_types)]
        local block_data = {
            ["name"] = block_type,
            ["tags"] = nil,
            ["state"] = nil
        }
        graph:add_vertex(i, 0, j, block_data)
        local coordinate_string = create_vertex_key(i, 0, j)
        block_data_file:write("(" .. coordinate_string .. "): " .. block_type .. "\n")
    end
end
block_data_file:close()
generate_graph_image(graph, 0)