Deep copy of a NaryTree
I am trying to implement a copy constructor for a BehaviorTree (special case NaryTree). The tree is defined as:
And the nodes are derived classes of
BehaviorTreeNode
(BehaviorTreeSequenceNode
, BehaviorTreeSelectorNode
, BehaviorTreeExecutorNode
). The base class is defined as:
I am looking for some direction on how to approach this. I know I could either do an iterative approach using a stack or a queue, or recursive, but I am going back and forth between the two and not sure which would be better for a desktop application.45 Replies
You'll probably have an easier time of it if each node can clone itself and its children (i.e. recursive). If you try and use an explicit stack rather than recursion, you'll end up effectively needing to wire together a cloned tree yourself by walking the original tree
And although copy ctors are normally a good approach, since you have a tree with different types of nodes in it, you're going to have a better time if you have an abstract
Clone
method on BehaviorTreeNodeBase
. Then the parent node can just call child.Clone()
without caring about the concrete type of the childYou don't know what
AddNode
/ RemoveNode
do, and where they store that node 🙂yep it clones the basic tree structure i seen in
BehaviorTreeNodeBase
only
it would be a problem if you have eg
So I couldn't include the implementation of
AddNode
/RemoveNode
because the post was too long, but they are defined as follows:
I think that's missing something key: you just end up assigning to a local variable a lot
Yeah, it was a quick way I thought of to get to the end of the singularly linked list, since the node only keeps track of the sibling node.
now you may have to cast the
source
to the actual type in CloneOthers
, which slightly annoying
btw you can add the node to the front of linked list if order is not importantRight, but once you get to the end, you don't do anything with it!
Unfortunately the order is important as it determines the flow of execution in the
BehaviorTree
Well my thought was that current
acts like a pointer in this context, and when it exits the while loop it will be referencing the null value at the end of the list. So assigning it other
now has it point to the passed in value rather than the null value.You're on the right path, but just stop and think about what your code is doing.
When you exit the
while
loop, current
is null
. It's always null
.
So you can replace that code with:
Or just:
And current
is just a local variable. And if all your method does is create a local variable (and then throw if away when the method returns), it isn't doing anything at allBut isn't
current
a reference to the last node's siblingNode
that is null? And assigning to it would be the same as assigning to the siblingNode
of the last node?No, it holds the location of a
BehaviorTreeNodeBase
, not the location of a variable which points to a BehaviorTreeNodeBase
object
If you know C/C++, it's a BehaviorTreeNodeBase*
not a BehaviorTreeNodeBase**
canton7
REPL Result: Success
Console Output
Compile: 458.247ms | Execution: 39.601ms | React with ❌ to remove this embed.
Alright, so if I were to modify the while loop to be
That would then result in current being the last node, and assigning
other
to its siblingNode
would be assigned?That should work
Can you walk me through this code? I am having a hard time following it.
still here?
I am now.
the original version
but i put the part
to the virtual method
so that each sub type can handle the clone (through dynamic dispatch) without written a big switch pattern matching in the
for
loop aboveSo if I am following, the
for
loop adds the root as the initial value, the increment step tries to pop a tuple that is the source BehaviorTreeNodeBase
and the destination. It then pushes the firstChildNode
and siblingNode
of the newly cloned nodes to the stack and loops back.
Am, I understanding this so far?iterative post order dfs
so you need to keep (push) the
(cloned, this)
pair into the stack and when you pop the stack, you can get back the target node (cloned
) to modifyGotcha. I think my initial approach was a version of bfs, but I couldn't keep track of the linkages between nodes so I just kept spinning my wheels.
I modified the search to use a tuple instead and I think it will work:
why do you have
BehaviorTreeNodeBase
and BehaviorTreeNode
?
are you implementing other types of BehaviorTreeNodeBase
?
also, can multiple threads potentially create nodes at the same time?
@Full Spectrum WulfeniteI separated
BehaviorTreeNodeBase
from BehaviorTreeNode
because the AddNode
and RemoveNode
methods are the same for all types of nodes, while the EvaluateNode
is different for every derived node.
This is the only implementation of BehaviorTreeNodeBase
All other node types (sequencer, selector, and executor) are derived from BehaviorTreeNode
.
It is a single threaded operation.unnecessary separation of type then.
if they all inherit from
BehaviorTreeNode
, then why should base and node be separate types?Because when I initially put it together I had though that
abstract
classes could only have abstract
methods.
I can refactor it easily enough.It is a single threaded operation.ok. then that's fine.
ID++
when ID
is static is immediately a code-smell to me. but if it's single-threaded, then it's less of a concern
it's fine.
i assume public fields are because Unity shit?Correct.
Here is the github:
https://github.com/senrik/BehaviorTreeLite
ah, even better
i'll play with it a bit
your
AddNode
is incorrect...
@Full Spectrum Wulfenite if firstChildNode
is not null, all you're doing is setting a local variable to other
But doesn't that act like a pointer to the last valid node in the sequence?
Didn't we already have exactly this conversation earlier?
Yeah, and I thought the solution was solved?
Full Spectrum Wulfenite
Alright, so if I were to modify the while loop to be
That would then result in current being the last node, and assigning
other
to its siblingNode
would be assigned?Quoted by
<@660066004059029524> from #Deep copy of a NaryTree (click here)
React with ❌ to remove this embed.
this is the correct version. it is not what @Full Spectrum Wulfenite uploaded though

that's not what you have uploaded
Ah, I forgot to push
There we go
Apologies.
ok, @Full Spectrum Wulfenite. here's what you need...
And that takes care of the derived classes being created!
now you undrstand why i was baffled at you wanting to do a bfs algo
Beware the siblingNode (and firstChildNode?) may be null there
good catch; fixed