A-Star Support

[SanderKofficial]

Adding A*(A-Star) Alghoritm support. For much deeper complex code.

We need a solution to make this easier to implement within our nodes or graphs.

Sample of an A* in usage within Lua.

-- Define a graph (adjacency list)
local graph = {
    A = {B = 1, C = 4},
    B = {A = 1, D = 5},
    C = {A = 4, D = 1},
    D = {B = 5, C = 1}
}

-- Heuristic function (example: Euclidean distance)
local heuristic = {
    A = 5,
    B = 3,
    C = 2,
    D = 0
}

-- A* Algorithm
function astar(start, goal)
    local openSet = {start}
    local cameFrom = {}
    local gScore = { [start] = 0 }
    local fScore = { [start] = heuristic[start] }

    while #openSet > 0 do
        local current = getLowestFScoreNode(openSet, fScore)
        if current == goal then
            return reconstructPath(cameFrom, current)
        end

        table.remove(openSet, findIndex(openSet, current))

        for neighbor, cost in pairs(graph[current]) do
            local tentativeGScore = gScore[current] + cost
            if not gScore[neighbor] or tentativeGScore < gScore[neighbor] then
                cameFrom[neighbor] = current
                gScore[neighbor] = tentativeGScore
                fScore[neighbor] = gScore[neighbor] + heuristic[neighbor]

                if not contains(openSet, neighbor) then
                    table.insert(openSet, neighbor)
                end
            end
        end
    end

    return nil  -- No path found
end

-- Helper functions
function getLowestFScoreNode(set, scores)
    local lowestScore = math.huge
    local lowestNode
    for _, node in ipairs(set) do
        local score = scores[node]
        if score < lowestScore then
            lowestScore = score
            lowestNode = node
        end
    end
    return lowestNode
end

function findIndex(array, value)
    for i, v in ipairs(array) do
        if v == value then
            return i
        end
    end
    return nil
end

function contains(array, value)
    for _, v in ipairs(array) do
        if v == value then
            return true
        end
    end
    return false
end

function reconstructPath(cameFrom, current)
    local path = {current}
    while cameFrom[current] do
        current = cameFrom[current]
        table.insert(path, 1, current)
    end
    return path
end

-- Example usage
local path = astar("A", "D")
print("Path:", table.concat(path, " -> "))