Skip to content

Instantly share code, notes, and snippets.

@MrChickenRocket
Created July 31, 2022 04:25
Show Gist options
  • Save MrChickenRocket/4ff34c8a4b786e15a25c47f2bba1bb3d to your computer and use it in GitHub Desktop.
Save MrChickenRocket/4ff34c8a4b786e15a25c47f2bba1bb3d to your computer and use it in GitHub Desktop.
Relatively well optimized Astar for luau (uses a kinda clever priority queue to avoid searching the open list for best f)
local module = {}
local INF = 1/0
function dist ( x1, y1, x2, y2 )
return math.sqrt ( math.pow ( x2 - x1, 2 ) + math.pow ( y2 - y1, 2 ) )
end
function heuristic_cost_estimate ( nodeA, nodeB )
return dist ( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) * 2000
end
function not_in_open ( set, theNode )
for _, record in ipairs ( set ) do
if record.node == theNode then
return false
end
end
return true
end
function not_in(set, node)
return set[node] == nil
end
function remove_open_node ( set, theNode )
set[theNode] = nil
end
function unwind_path ( flat_path, map, current_node )
if map [ current_node ] then
table.insert ( flat_path, 1, map [ current_node ] )
return unwind_path ( flat_path, map, map [ current_node ] )
else
return flat_path
end
end
function debugNode(node)
local part = Instance.new("Part")
part.Size = Vector3.new(1,1,1)
part.Position = Vector3.new(3 + node.x * 6 , 3, 3 + node.y * 6)
part.Anchored = true
part.Color = Color3.new(1,1,1)
part.Parent = game.Workspace
end
function module:Astar( start, goal, nodes, maxComplexity)
local closedset = {}
local openset = {}
local came_from = {}
local g_score = {}
g_score [ start ] = 0
table.insert(openset,
{
fscore = g_score [ start ] + heuristic_cost_estimate ( start, goal ),
node = start
}
)
local workCounter = 0
while next(openset) ~= nil do
local c = #openset --index of the last element
local currentRecord = openset[c]
local currentNode = currentRecord.node
workCounter += 1
if (workCounter > maxComplexity) then
--print("path too complex")
return nil
end
if currentNode == goal then
local path = unwind_path ( {}, came_from, currentNode )
table.insert ( path, goal )
--print("work", workCounter)
return path
end
table.remove(openset,c)
closedset[currentNode] = 1
local neighbors = currentNode.connections
for _, neighborConnection in pairs ( neighbors ) do
local node = neighborConnection.n
if not_in ( closedset, node) then
local tentative_g_score = g_score [ currentNode ] + neighborConnection.cost
if not_in_open ( openset, node ) or tentative_g_score < g_score [ node ] then
came_from [ node ] = currentNode
g_score [ node ] = tentative_g_score
local fscore = tentative_g_score + heuristic_cost_estimate ( node, goal )
--add the node
--Upgrade idea: Do a sorted insert?
local opensetcount = #openset
--these are basically the same thing but small optimizations
if (opensetcount == 0 or openset[opensetcount].fscore >= fscore ) then
--append to end
table.insert(openset, {
fscore = fscore,
node = node,
})
elseif (openset[1].fscore <= fscore) then
--append to start
table.insert(openset,1, {
fscore = fscore,
node = node,
})
else
local insertPoint = #openset + 1
for counter = 1, #openset do
if (openset[counter].fscore < fscore) then
insertPoint = counter
break
end
end
table.insert(openset, insertPoint,{
fscore = fscore,
node = node,
})
end
end
end
end
end
return nil -- no valid path
end
function module:Path(start, goal, nodes, maxComplexity)
local resPath = module:Astar(start, goal, nodes, maxComplexity)
return resPath
end
return module
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment