Relatively well optimized Astar for luau (uses a kinda clever priority queue to avoid searching the open list for best f)

astar.lua

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