Deep copy of a NaryTree

I am trying to implement a copy constructor for a BehaviorTree (special case NaryTree). The tree is defined as:
public class BehaviorTree {
private BehaviorTreeNode root;
public BehaviorTree() {
root = new BehaviorTreeNode();
}
public BehaviorTree(BehaviorTree other) {
// Implementation goes here
}
}
public class BehaviorTree {
private BehaviorTreeNode root;
public BehaviorTree() {
root = new BehaviorTreeNode();
}
public BehaviorTree(BehaviorTree other) {
// Implementation goes here
}
}
And the nodes are derived classes of BehaviorTreeNode (BehaviorTreeSequenceNode, BehaviorTreeSelectorNode, BehaviorTreeExecutorNode). The base class is defined as:
public abstract class BehaviorTreeNodeBase
{
protected static int ID;
protected int _id;
public BehaviorTreeNodeBase firstChildNode;
public BehaviorTreeNodeBase siblingNode;

public virtual BehaviorTreeState EvaluateNode(IBehaviorTreeAgent instance) { return BehaviorTreeState.None; }
public abstract void AddNode(BehaviorTreeNodeBase other);

public abstract void RemoveNode(BehaviorTreeNodeBase other);

public int id
{
get { return _id; }
}
}

public class BehaviorTreeNode : BehaviorTreeNodeBase
{
public BehaviorTreeNode() {
_id = ID;
ID++;
}

public BehaviorTreeNode(BehaviorTreeNode other)
{
this._id = other._id;
}

public override void AddNode(BehaviorTreeNodeBase other)
{
//Add child node
}

public override void RemoveNode(BehaviorTreeNodeBase other)
{
//Remove child node
}
}
public abstract class BehaviorTreeNodeBase
{
protected static int ID;
protected int _id;
public BehaviorTreeNodeBase firstChildNode;
public BehaviorTreeNodeBase siblingNode;

public virtual BehaviorTreeState EvaluateNode(IBehaviorTreeAgent instance) { return BehaviorTreeState.None; }
public abstract void AddNode(BehaviorTreeNodeBase other);

public abstract void RemoveNode(BehaviorTreeNodeBase other);

public int id
{
get { return _id; }
}
}

public class BehaviorTreeNode : BehaviorTreeNodeBase
{
public BehaviorTreeNode() {
_id = ID;
ID++;
}

public BehaviorTreeNode(BehaviorTreeNode other)
{
this._id = other._id;
}

public override void AddNode(BehaviorTreeNodeBase other)
{
//Add child node
}

public override void RemoveNode(BehaviorTreeNodeBase other)
{
//Remove child node
}
}
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
canton7
canton74w ago
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 child
ティナ
ティナ4w ago
root = other?.root.Clone();
Stack<(BehaviorTreeNodeBase,BehaviorTreeNodeBase)> s=new();
for(s.Push((root,other.root));s.TryPop( out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
}
root = other?.root.Clone();
Stack<(BehaviorTreeNodeBase,BehaviorTreeNodeBase)> s=new();
for(s.Push((root,other.root));s.TryPop( out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
}
canton7
canton74w ago
You don't know what AddNode / RemoveNode do, and where they store that node 🙂
ティナ
ティナ4w ago
yep it clones the basic tree structure i seen in BehaviorTreeNodeBase only it would be a problem if you have eg
public class Surprise:BehaviorTreeNodeBase{
public BehaviorTreeNodeBase secondChildNode;
}
public class Surprise:BehaviorTreeNodeBase{
public BehaviorTreeNodeBase secondChildNode;
}
Full Spectrum Wulfenite
So I couldn't include the implementation of AddNode/RemoveNode because the post was too long, but they are defined as follows:
public override void AddNode(BehaviorTreeNodeBase other)
{
if (firstChildNode == null)
firstChildNode = other;
else
{
var current = firstChildNode;
while (current != null)
{
current = current.siblingNode;
}
current = other;
}
}

public override void RemoveNode(BehaviorTreeNodeBase other)
{
if (this.firstChildNode != null)
{
if (this.firstChildNode.id == other.id)
{
var temp = this.firstChildNode.siblingNode;
this.firstChildNode = temp;
}
else
{
var current = this.firstChildNode;
var prev = this.firstChildNode;
while (current != null)
{
if (current.id == other.id)
{
prev.siblingNode = current.siblingNode;
break;
}
prev = current;
current = current.siblingNode;
}
}


}
}
public override void AddNode(BehaviorTreeNodeBase other)
{
if (firstChildNode == null)
firstChildNode = other;
else
{
var current = firstChildNode;
while (current != null)
{
current = current.siblingNode;
}
current = other;
}
}

public override void RemoveNode(BehaviorTreeNodeBase other)
{
if (this.firstChildNode != null)
{
if (this.firstChildNode.id == other.id)
{
var temp = this.firstChildNode.siblingNode;
this.firstChildNode = temp;
}
else
{
var current = this.firstChildNode;
var prev = this.firstChildNode;
while (current != null)
{
if (current.id == other.id)
{
prev.siblingNode = current.siblingNode;
break;
}
prev = current;
current = current.siblingNode;
}
}


}
}
canton7
canton74w ago
var current = firstChildNode;
while (current != null)
{
current = current.siblingNode;
}
current = other;
var current = firstChildNode;
while (current != null)
{
current = current.siblingNode;
}
current = other;
I think that's missing something key: you just end up assigning to a local variable a lot
Full Spectrum Wulfenite
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.
ティナ
ティナ4w ago
public abstract class BehaviorTreeNodeBase {
public BehaviorTreeNodeBase firstChildNode;
public BehaviorTreeNodeBase siblingNode;

/// <summary>
/// reconstructs the link to other <see cref="BehaviorTreeNodeBase"/> by copying <paramref name="source"/> with <see cref="CloneSelf"/>, DONT recursive call.
/// </summary>
/// <param name="stack">TODO</param>
public abstract void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack);

/// <summary>
/// clone itself only, dont call <see cref="CloneOthers"/> on any child / sibling
/// </summary>
/// <returns></returns>
public abstract BehaviorTreeNodeBase CloneSelf();
}

public class BehaviorTreeNode:BehaviorTreeNodeBase {
public override void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack) {
siblingNode = source.siblingNode.CloneSelf();
firstChildNode = source.firstChildNode.CloneSelf();
stack.Push((siblingNode, source.siblingNode));
stack.Push((firstChildNode, source.firstChildNode));
}

public override BehaviorTreeNode CloneSelf() {
return new BehaviorTreeNode();
}
}


public class BehaviorTree {
private BehaviorTreeNode root;
public BehaviorTree() {
root = new BehaviorTreeNode();
}
public BehaviorTree(BehaviorTree other) {
root = other?.root.CloneSelf();
Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> s = new();
for(s.Push((root, other.root));s.TryPop(out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.CloneOthers(p.Item2, s);
}
}
}
public abstract class BehaviorTreeNodeBase {
public BehaviorTreeNodeBase firstChildNode;
public BehaviorTreeNodeBase siblingNode;

/// <summary>
/// reconstructs the link to other <see cref="BehaviorTreeNodeBase"/> by copying <paramref name="source"/> with <see cref="CloneSelf"/>, DONT recursive call.
/// </summary>
/// <param name="stack">TODO</param>
public abstract void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack);

/// <summary>
/// clone itself only, dont call <see cref="CloneOthers"/> on any child / sibling
/// </summary>
/// <returns></returns>
public abstract BehaviorTreeNodeBase CloneSelf();
}

public class BehaviorTreeNode:BehaviorTreeNodeBase {
public override void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack) {
siblingNode = source.siblingNode.CloneSelf();
firstChildNode = source.firstChildNode.CloneSelf();
stack.Push((siblingNode, source.siblingNode));
stack.Push((firstChildNode, source.firstChildNode));
}

public override BehaviorTreeNode CloneSelf() {
return new BehaviorTreeNode();
}
}


public class BehaviorTree {
private BehaviorTreeNode root;
public BehaviorTree() {
root = new BehaviorTreeNode();
}
public BehaviorTree(BehaviorTree other) {
root = other?.root.CloneSelf();
Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> s = new();
for(s.Push((root, other.root));s.TryPop(out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.CloneOthers(p.Item2, s);
}
}
}
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 important
canton7
canton74w ago
Right, but once you get to the end, you don't do anything with it!
Full Spectrum Wulfenite
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.
canton7
canton74w ago
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:
var current = firstChildNode;
current = null;
current = other;
var current = firstChildNode;
current = null;
current = other;
Or just:
var current = other;
var current = other;
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 all
Full Spectrum Wulfenite
But 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?
canton7
canton74w ago
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**
MODiX
MODiX4w ago
canton7
REPL Result: Success
var test = new Test();

var current = test.s;
Console.WriteLine(current);

current = "Bar";
Console.WriteLine(test.s);
Console.WriteLine(current);

class Test
{
public string s = "Foo";
}
var test = new Test();

var current = test.s;
Console.WriteLine(current);

current = "Bar";
Console.WriteLine(test.s);
Console.WriteLine(current);

class Test
{
public string s = "Foo";
}
Console Output
Foo
Foo
Bar
Foo
Foo
Bar
Compile: 458.247ms | Execution: 39.601ms | React with ❌ to remove this embed.
Full Spectrum Wulfenite
Alright, so if I were to modify the while loop to be
while(current.siblingNode !=null) {
current = current.siblingNode;
}
current.siblingNode = other;
while(current.siblingNode !=null) {
current = current.siblingNode;
}
current.siblingNode = other;
That would then result in current being the last node, and assigning other to its siblingNode would be assigned?
canton7
canton74w ago
That should work
Full Spectrum Wulfenite
Can you walk me through this code? I am having a hard time following it.
ティナ
ティナ4w ago
still here?
Full Spectrum Wulfenite
I am now.
ティナ
ティナ4w ago
the original version
root = other?.root.Clone();
Stack<(BehaviorTreeNodeBase,BehaviorTreeNodeBase)> s=new();
for(s.Push((root,other.root));s.TryPop( out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
}
root = other?.root.Clone();
Stack<(BehaviorTreeNodeBase,BehaviorTreeNodeBase)> s=new();
for(s.Push((root,other.root));s.TryPop( out (BehaviorTreeNodeBase, BehaviorTreeNodeBase) p);) {
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
}
but i put the part
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
p.Item1.firstChildNode=p.Item2.firstChildNode.Clone();
p.Item1.siblingNode=p.Item2.siblingNode.Clone();

s.Push((p.Item1.firstChildNode,p.Item2.firstChildNode));
s.Push((p.Item1.siblingNode,p.Item2.siblingNode));
to the virtual method
public override void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack) {
siblingNode = source.siblingNode.CloneSelf();
firstChildNode = source.firstChildNode.CloneSelf();
stack.Push((siblingNode, source.siblingNode));
stack.Push((firstChildNode, source.firstChildNode));
}
public override void CloneOthers(BehaviorTreeNodeBase source, Stack<(BehaviorTreeNodeBase, BehaviorTreeNodeBase)> stack) {
siblingNode = source.siblingNode.CloneSelf();
firstChildNode = source.firstChildNode.CloneSelf();
stack.Push((siblingNode, source.siblingNode));
stack.Push((firstChildNode, source.firstChildNode));
}
so that each sub type can handle the clone (through dynamic dispatch) without written a big switch pattern matching in the for loop above
Full Spectrum Wulfenite
So 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?
ティナ
ティナ4w ago
iterative post order dfs
public void TreeNode Clone(){
TreeNode cloned=new();
cloned.first=this.first.Clone(); // note that cloned.first is assigneed before the method leave
cloned.second=this.first.second();
return cloned;
}
public void TreeNode Clone(){
TreeNode cloned=new();
cloned.first=this.first.Clone(); // note that cloned.first is assigneed before the method leave
cloned.second=this.first.second();
return cloned;
}
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 modify
Full Spectrum Wulfenite
Gotcha. 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.
public BehaviorTree(BehaviorTree other)
{
var queue = new List<BehaviorTreeNode>();
queue.Add(other.root);

while (queue.Count > 0) {
var temp = queue[0];
// copy to this tree
queue.RemoveAt(0);
var current = temp.firstChildNode;

while(current != null)
{
queue.Add((BehaviorTreeNode)current);
current = current.siblingNode;
}
}
}
public BehaviorTree(BehaviorTree other)
{
var queue = new List<BehaviorTreeNode>();
queue.Add(other.root);

while (queue.Count > 0) {
var temp = queue[0];
// copy to this tree
queue.RemoveAt(0);
var current = temp.firstChildNode;

while(current != null)
{
queue.Add((BehaviorTreeNode)current);
current = current.siblingNode;
}
}
}
I modified the search to use a tuple instead and I think it will work:
public BehaviorTree(BehaviorTree other)
{
var queue = new List<(BehaviorTreeNode, BehaviorTreeNode)>();


this.root = new BehaviorTreeNode(other.root);
queue.Add((other.root, this.root));
BehaviorTreeNode header = this.root;

while (queue.Count > 0) {
var temp = queue[0];


queue.RemoveAt(0);
var current = temp.Item1.firstChildNode;

while(current != null)
{

var child = new BehaviorTreeNode((BehaviorTreeNode)current);
temp.Item2.AddNode(child);
queue.Add(((BehaviorTreeNode)current, child));
current = current.siblingNode;
}
}
}
public BehaviorTree(BehaviorTree other)
{
var queue = new List<(BehaviorTreeNode, BehaviorTreeNode)>();


this.root = new BehaviorTreeNode(other.root);
queue.Add((other.root, this.root));
BehaviorTreeNode header = this.root;

while (queue.Count > 0) {
var temp = queue[0];


queue.RemoveAt(0);
var current = temp.Item1.firstChildNode;

while(current != null)
{

var child = new BehaviorTreeNode((BehaviorTreeNode)current);
temp.Item2.AddNode(child);
queue.Add(((BehaviorTreeNode)current, child));
current = current.siblingNode;
}
}
}
viceroypenguin
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 Wulfenite
Full Spectrum Wulfenite
I 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.
viceroypenguin
unnecessary separation of type then. if they all inherit from BehaviorTreeNode, then why should base and node be separate types?
Full Spectrum Wulfenite
Because when I initially put it together I had though that abstract classes could only have abstract methods. I can refactor it easily enough.
viceroypenguin
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?
viceroypenguin
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
Full Spectrum Wulfenite
But doesn't that act like a pointer to the last valid node in the sequence?
canton7
canton74w ago
Didn't we already have exactly this conversation earlier?
Full Spectrum Wulfenite
Yeah, and I thought the solution was solved?
MODiX
MODiX4w ago
Full Spectrum Wulfenite
Alright, so if I were to modify the while loop to be
while(current.siblingNode !=null) {
current = current.siblingNode;
}
current.siblingNode = other;
while(current.siblingNode !=null) {
current = current.siblingNode;
}
current.siblingNode = other;
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.
viceroypenguin
this is the correct version. it is not what @Full Spectrum Wulfenite uploaded though
Full Spectrum Wulfenite
public override void AddNode(BehaviorTreeNodeBase other)
{
if (firstChildNode == null)
firstChildNode = other;
else
{
var current = firstChildNode;
while (current.siblingNode != null)
{
current = current.siblingNode;
}
current.siblingNode = other;
}
this.childCount++;
}
public override void AddNode(BehaviorTreeNodeBase other)
{
if (firstChildNode == null)
firstChildNode = other;
else
{
var current = firstChildNode;
while (current.siblingNode != null)
{
current = current.siblingNode;
}
current.siblingNode = other;
}
this.childCount++;
}
viceroypenguin
that's not what you have uploaded
Full Spectrum Wulfenite
Ah, I forgot to push There we go Apologies.
viceroypenguin
ok, @Full Spectrum Wulfenite. here's what you need...
public abstract class BehaviorTreeNode
{
protected abstract BehaviorTreeNode CloneSelf();
public BehaviorTreeNode Clone()
{
var clone = CloneSelf();
clone.firstChildNode = firstChildNode?.Clone();
clone.siblingNode = siblingNode?.Clone();
return clone;
}
}

public class BehaviorTreeSequencerNode : BehaviorTreeNode
{
public BehaviorTreeSequencerNode(){ this.id = ID++; }
private BehaviorTreeSequencerNode(BehaviorTreeSequencerNode other)
{
this.id = other.id;
}

protected override BehaviorTreeNode CloneSelf() =>
new BehaviorTreeSequencerNode(this);
}
public abstract class BehaviorTreeNode
{
protected abstract BehaviorTreeNode CloneSelf();
public BehaviorTreeNode Clone()
{
var clone = CloneSelf();
clone.firstChildNode = firstChildNode?.Clone();
clone.siblingNode = siblingNode?.Clone();
return clone;
}
}

public class BehaviorTreeSequencerNode : BehaviorTreeNode
{
public BehaviorTreeSequencerNode(){ this.id = ID++; }
private BehaviorTreeSequencerNode(BehaviorTreeSequencerNode other)
{
this.id = other.id;
}

protected override BehaviorTreeNode CloneSelf() =>
new BehaviorTreeSequencerNode(this);
}
Full Spectrum Wulfenite
And that takes care of the derived classes being created!
viceroypenguin
now you undrstand why i was baffled at you wanting to do a bfs algo
canton7
canton74w ago
Beware the siblingNode (and firstChildNode?) may be null there
viceroypenguin
good catch; fixed

Did you find this page helpful?