Breadth-First Search option for Node.find_child()

[guilleatm]

Reading the docs, found that Node.find_child() function (old: Node.find_node) performs a Deep-First Search. I thought it could be great having an optional parameter to choose between deep and breadth search. Of course, depending on each project or use case, one of the two options will be more convenient but this way we give the user more control over what it's happening.

[Calinou]

Can you describe your use case for using find_child()? Also, are you running into a performance bottleneck with the current implementation?

[dalexeev]

I think it's not just about performance, but that the two options can give different results. Perhaps this really has some practical meaning (children are more priority than grandchildren).

[guilleatm]

I am not running into a performance bottleneck but in some cases this might help.
I feel that it is more intuitive to think in a deep search when guessing about how find_child works.

More than that, find_child is not meant to be used a lot so it can be used in the _ready function for finding some managers / controllers that you don't now where they are in the tree.

The path for the children inside these manager nodes is usually known, probably the manager is a separated scene and there is no reason to look for deep nodes first.

[SlugFiller]

BFS has a cost, in that it requires keeping the "wavefront" in memory while searching. In real time software, memory allocations need to be kept to a minimum, because allocating memory is an operation that could take any amount of time, based on the amount of allocations made so far.

In other words, without adding skip-links to the nodes (which would be its own additional layer of complexity), BFS would simply be far too costly relative to DFS, and not practical for use in a game engine.

[ivxvm]

@SlugFiller @guilleatm
Instead of BFS, iterative-deepening search can be used.

[SlugFiller]

The issue is that it would revisit the low-depth nodes as many times as the tree is deep. If the tree is wide at the base, but has a very long stringy branch, the performance cost could be massive. We're talking O(n^2) for an operation that should be O(n). So, still not practical in a game engine.