I found that performance problems caused by this function of pathfinding:
# When called, this method pops the next node off the PQ and examines all
# its edges. The method returns an enumerated value (target_found,
# target_not_found, search_incomplete) indicating the status of the search
func CycleOnce() -> int:
# if the PQ is empty the target has not been found
if PQ.empty():
return TargetNotFound
# get lowest cost node from the queue
var NextClosestNode : int = PQ.Pop()
# put the node on the SPT
shortestPathTree[NextClosestNode] = searchFrontier[NextClosestNode]
# if the target has been found exit
if NextClosestNode == target:
return TargetFound
# now to test all the edges attached to this node
var edges : Dictionary = graph.GetEdgesTo(NextClosestNode)
for edge_key in edges.keys():
var edge = edges[edge_key]
# calculate the heuristic cost from this node to the target (H)
var HCost : float = heuristic.Calculate(graph, target, edge.to)
# calculate the 'real' cost to this node from the source (G)
var GCost : float = gCosts[NextClosestNode] + edge.cost
# if the node has not been added to the frontier, add it and update
# the G and F costs
if (searchFrontier[edge.to] == null):
fCosts[edge.to] = GCost + HCost
gCosts[edge.to] = GCost
PQ.insert(edge.to)
searchFrontier[edge.to] = edge
# if this node is already on the frontier but the cost to get here
# is cheaper than has been found previously, update the node
# costs and frontier accordingly.
elif ((GCost < gCosts[edge.to]) and (shortestPathTree[edge.to] == null)):
fCosts[edge.to] = GCost + HCost
gCosts[edge.to] = GCost
PQ.ChangePriority(edge.to)
searchFrontier[edge.to] = edge
# there are still nodes to explore
return SearchIncomplete
It created a lot of objects and doesn't remove it. What is wrong here?