local function by_priority(a, b)
	return a[2] < b[2]
end

local function get_path(node, came_from)
	local path = {}
	while node do
		table.insert(path, 1, node)
		node = came_from[node]
	end
	return path
end

local function astar(origin, target, get_neighbors, is_good_node, get_cost, get_heuristic, pass_path)
	assert(origin and target and type(get_neighbors) == "function" and type(is_good_node) == "function" and type(get_cost) == "function" and type(get_heuristic) == "function", "Incorrect Arguments To A* Pathfinder")

	local frontier, came_from, known_cost = {{origin, 0}}, {[origin] = false}, {[origin] = 0}

	while frontier[1] do
		local current_node = table.remove(frontier, 1)[1]
		if is_good_node(current_node) then
			local current_path = pass_path and get_path(current_node, came_from)

			if current_node == target then
				return current_path or get_path(current_node, came_from)
			end

			for _, neighbor in ipairs(get_neighbors(current_node, current_path)) do
				local new_path = pass_path and {[#current_path + 1] = neighbor, unpack(current_path)}
				local new_cost = known_cost[current_node] + get_cost(current_node, neighbor, new_path)
				if (not known_cost[neighbor]) or (new_cost < known_cost[neighbor]) then
					table.insert(frontier, {neighbor, new_cost + get_heuristic(target, neighbor, new_path)})
					came_from[neighbor] = current_node
					known_cost[neighbor] = new_cost
				end
			end
		end
		table.sort(frontier, by_priority)
	end

	return false
end

return astar

