The tree is an acyclic binary tree. It’s composed of node objects that have a list of connections to link objects (at most 3), and link objects that have a list of connections to node objects (always 2). I am trying to construct a list of possible paths to other nodes that can be reached given a fuel budget and a fuel cost on each link. What it is supposed to do is go through each non-backtracking connection of a node, and spawn a new route and thread to investigate that, leaving the current one to end at that node and thus create a list of routes to every node in the reachable area. When executed, the list of end destinations are valid but many of the paths that are constructed to get to them are wrong, going down other branches in the tree that are extraneous or entirely outside of the reachable area bounded by the fuel budget as well as jumping between nodes that aren’t directly connected. There seems to be some pattern in the errors, when going down from the root of some branches of the tree the path goes down every offshoot in order first instead of going in a straight line, and when going up the tree the path tends to go further out and make triangle shapes, often landing somewhere other than the listed destination. I have already checked the link and node connections themselves to see if they are assigned properly, and they are. What am I getting wrong?
Route class definition
var origin:Node var destination:Node var totaldV:float var totalt:float var dVBudget:float var tBudget:float var tdVRatio:float var links:Array var nodes:Array func duplicate_values(originator:Route): origin = originator.origin destination = originator.destination totaldV = originator.totaldV totalt = originator.totalt dVBudget = originator.dVBudget tBudget = originator.tBudget tdVRatio = originator.tdVRatio nodes = originator.nodes links = originator.links func _init(originator_route): if originator_route != null: duplicate_values(originator_route)
Tree traversal algorithm
var routes:Array onready var root = get_node("..") func traverse(current_node:Node, previous_route:Route): if previous_route == null: # Starts off the recursion by providing an initial node previous_route = Route.new(null) previous_route.origin = current_node previous_route.nodes.append(previous_route.origin) previous_route.dVBudget = 2000 previous_route.totaldV = 0 for link in current_node.connections: if (previous_route.totaldV + link.dV < previous_route.dVBudget && !IsBacktracking(previous_route, LinkDestination(link, current_node))): # If there is enough fuel and the link isn't backtracking, go through it. var working_route:Route = Route.new(previous_route) # Copy the previous route to make the new route routes.append(working_route) working_route.destination = LinkDestination(link, current_node) working_route.totaldV += link.dV working_route.totalt += link.t working_route.links.append(link) working_route.nodes.append(working_route.destination) traverse(working_route.destination, working_route) DisplayRoutes() root.get_parent().pathSelectionFlag = true # UI control boolean func IsBacktracking(route:Route, destinationNode:Node) -> bool: for nodeI in route.nodes: if (destinationNode == nodeI): return true return false func LinkDestination(link:Node, originNode:Node) -> Node: # Finds the node on the other side of a link for nodeI in link.connections: if (nodeI != originNode): return nodeI return originNode