# Traversing an acyclic binary tree to construct paths from a given starting node, but the paths come out wrong

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 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

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.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


When you do set the arrays, here:

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 # <- here


They are the same array, not a copy. For that you can use Array.duplicate. Which would be like this:

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.duplicate()

• @spacegamer You have two arrays: links and nodes you need to duplicate them, or you end up with the same arrays when you do nodes = originator.nodes and links = originator.links. Aside from that, I'm suggesting to have a duplicate method that returns a new Route, so you don't do var working_route:Route = Route.new(previous_route) but var working_route:Route = previous_route.duplicate() (of course duplicate, would call Route.new internally, and you don't need to put parameters on it). Edit: I'll expand the answer. May 10 '21 at 3:56