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