Guidance on building a custom native tree container.

Hey all, I am building a behavior tree for DOTS. This is my first time making a custom container for real, and I think I got it, but could someone give it a quick look over and tell me if you see any problems? Thank you!

I am aware there aren't any safety checks I took them out for readability.

Code (CSharp):

1. [StructLayout( LayoutKind.Sequential )]
2. public unsafe struct NativeBehaviourTree : IDisposable
3. {
4.     [NativeDisableUnsafePtrRestriction] internal void* tree_buffer;
5.     [NativeDisableUnsafePtrRestriction] internal void* action_buffer;
6.  
7.     internal Allocator allocatorLabel;
8.  
9.     public NativeBehaviourTree( Allocator allocator , NativeArray<BehaviourNode> nodes , NativeArray<FunctionPointer<BehaviourTreeAction>> actions )
10.     {
11.         long treeSize = UnsafeUtility.SizeOf<BehaviourNode>() * ( long ) nodes.Length;
12.         long actionSize = UnsafeUtility.SizeOf<FunctionPointer<BehaviourTreeAction>>() * ( long ) actions.Length;
13.  
14.         tree_buffer = UnsafeUtility.Malloc( treeSize , UnsafeUtility.AlignOf<BehaviourNode>() , allocator );
15.         action_buffer = UnsafeUtility.Malloc( actionSize , UnsafeUtility.AlignOf<FunctionPointer<BehaviourTreeAction>>() , allocator );
16.  
17.         allocatorLabel = allocator;
18.  
19.         BuildTree( nodes , actions );
20.     }
21.  
22.     private void BuildTree( NativeArray<BehaviourNode> nodes , NativeArray<FunctionPointer<BehaviourTreeAction>> actions )
23.     {
24.         for ( int i = 0; i < nodes.Length; i++ )
25.             UnsafeUtility.WriteArrayElement( tree_buffer , i , nodes[ i ] );
26.         for ( int i = 0; i < actions.Length; i++ )
27.             UnsafeUtility.WriteArrayElement( action_buffer , i , actions[ i ] );
28.     }
29.  
30.     public void EvaluateTree( ref AgentData data )
31.     {
32.         NodeState state = NodeState.FAILURE;
33.  
34.         do
35.         {
36.             state = EvaluateNode( *( ( BehaviourNode* ) tree_buffer ) , ref data );
37.         }
38.         while ( state != NodeState.RUNNING );
39.     }
40.     private NodeState EvaluateNode( BehaviourNode node , ref AgentData data )
41.     {
42.         switch ( node.Type )
43.         {
44.             case NodeType.SELECTOR:
45.                 return EvaluateSelector( node , ref data );
46.             case NodeType.SEQUENCE:
47.                 return EvaluateSequence( node , ref data );
48.             case NodeType.LEAF:
49.                 return EvaluateLeaf( node , ref data );
50.             default:
51.                 return NodeState.FAILURE;
52.         }
53.     }
54.     private NodeState EvaluateSequence( BehaviourNode node , ref AgentData data )
55.     {
56.         bool isAnyNodeRunning = false;
57.  
58.         for ( int i = 0; i < node.NumberOfChildren; i++ )
59.         {
60.             switch ( EvaluateNode( *( ( BehaviourNode* ) tree_buffer + node.FirstChildIndex + i ) , ref data ) )
61.             {
62.                 case NodeState.RUNNING:
63.                     isAnyNodeRunning = true;
64.                     break;
65.                 case NodeState.SUCCESS:
66.                     break;
67.                 case NodeState.FAILURE:
68.                     return NodeState.FAILURE;
69.             }
70.         }
71.  
72.         return isAnyNodeRunning ? NodeState.RUNNING : NodeState.SUCCESS;
73.     }
74.     private NodeState EvaluateSelector( BehaviourNode node , ref AgentData data )
75.     {
76.         for ( int i = 0; i < node.NumberOfChildren; i++ )
77.         {
78.             switch ( EvaluateNode( *( ( BehaviourNode* ) tree_buffer + node.FirstChildIndex + i ) , ref data ) )
79.             {
80.                 case NodeState.RUNNING:
81.                     return NodeState.RUNNING;
82.                 case NodeState.SUCCESS:
83.                     return NodeState.SUCCESS;
84.                 case NodeState.FAILURE:
85.                     break;
86.             }
87.         }
88.  
89.         return NodeState.FAILURE;
90.     }
91.     private NodeState EvaluateLeaf( BehaviourNode node , ref AgentData data )
92.     {
93.         return UnsafeUtility.ReadArrayElement<FunctionPointer<BehaviourTreeAction>>( action_buffer , node.FirstChildIndex ).Invoke( ref data );
94.     }
95.  
96.     public void Dispose()
97.     {
98.         UnsafeUtility.Free( tree_buffer , allocatorLabel );
99.         UnsafeUtility.Free( action_buffer , allocatorLabel );
100.         tree_buffer = null;
101.         action_buffer = null;
102.     }
103. }

 

This looks like an Unsafe container, not a NativeContainer. NativeContainers have attributes, atomic safety handles, and dispose sentinels.

 

I took out handles and sentinels for this post because it's bloated and ugly. I was just looking to see if I am using the unsafe utility and pointers right, or if I am breaking some rules.

 

Sorry, I didn't read that part carefully enough.

Nothing obvious sticks out to me, although if I am missing something it wouldn't be the first time.

One improvement might be to use pointers to the specific BehaviorNode and FunctionPointer<BehaviorTreeAction> as fields instead of using void*. That will save you some casts and make it easier to detect mistakes.

 

Containers need to add something new and be reusable over a large enough set of problems, or they don't really make sense. They create more duplication then the value they add which mostly serves to create more bugs and more code to maintain. What you have here could done better/simpler leveraging existing collections and not being a container.

And you have to factor in the cost of maintaining them using current api's. They completely refactored their allocators for example. What you have will likely continue to work for some time I would guess, but it's not using the latest api's in this area.

There has been a lot of dubious advice on the forums about what custom containers are good for. Which is I think forgivable to some extent given there wasn't a really clear direction from Unity at first. But there is now if you take the time to look. Look at what Unity themselves do is IMO the best guide.

 

This is actually a fair point. From the looks of it, this could just be a struct containing two NativeArrays. You don't have to use a NativeContainer if you are just looking to encapsulate the data structure semantically. You can even see Unity wrap containers if you look at HeapString.

 

Yep, way simpler. I don't know why I had such an urge to put it into a custom container.. Thanks this really helped!

Code (CSharp):

1. public struct BehaviourTree
2. {
3.     private NativeArray<BehaviourNode> nodes;
4.     private NativeArray<FunctionPointer<BehaviourTreeAction>> actions;
5.  
6.     public BehaviourTree( List<BehaviourNode> _nodes , List<FunctionPointer<BehaviourTreeAction>> _actions )
7.     {
8.         nodes = _nodes.ToNativeArray( Allocator.Persistent );
9.         actions = _actions.ToNativeArray( Allocator.Persistent );
10.     }
11.     public void Destroy()
12.     {
13.         nodes.Dispose();
14.         actions.Dispose();
15.     }
16.  
17.     public void EvaluateTree( ref AgentData data )
18.     {
19.         NodeState state = NodeState.FAILURE;
20.  
21.         do
22.         {
23.             state = EvaluateNode( nodes[ 0 ] , ref data );
24.         }
25.         while ( state != NodeState.RUNNING );
26.     }
27.  
28.     private NodeState EvaluateNode( BehaviourNode node , ref AgentData data )
29.     {
30.         switch ( node.Type )
31.         {
32.             case NodeType.SELECTOR:
33.                 return EvaluateSelector( node , ref data );
34.             case NodeType.SEQUENCE:
35.                 return EvaluateSequence( node , ref data );
36.             case NodeType.LEAF:
37.                 return EvaluateLeaf( node , ref data );
38.             default:
39.                 return NodeState.FAILURE;
40.         }
41.     }
42.     private NodeState EvaluateSequence( BehaviourNode node , ref AgentData data )
43.     {
44.         bool isAnyNodeRunning = false;
45.  
46.         for ( int i = 0; i < node.NumberOfChildren; i++ )
47.         {
48.             switch ( EvaluateNode( nodes[ node.FirstChildIndex + i ] , ref data ) )
49.             {
50.                 case NodeState.RUNNING:
51.                     isAnyNodeRunning = true;
52.                     break;
53.                 case NodeState.SUCCESS:
54.                     break;
55.                 case NodeState.FAILURE:
56.                     return NodeState.FAILURE;
57.             }
58.         }
59.  
60.         return isAnyNodeRunning ? NodeState.RUNNING : NodeState.SUCCESS;
61.     }
62.     private NodeState EvaluateSelector( BehaviourNode node , ref AgentData data )
63.     {
64.         for ( int i = 0; i < node.NumberOfChildren; i++ )
65.         {
66.             switch ( EvaluateNode( nodes[ node.FirstChildIndex + i ] , ref data ) )
67.             {
68.                 case NodeState.RUNNING:
69.                     return NodeState.RUNNING;
70.                 case NodeState.SUCCESS:
71.                     return NodeState.SUCCESS;
72.                 case NodeState.FAILURE:
73.                     break;
74.             }
75.         }
76.  
77.         return NodeState.FAILURE;
78.     }
79.     private NodeState EvaluateLeaf( BehaviourNode node , ref AgentData data )
80.     {
81.         return actions[ node.FirstChildIndex ].Invoke( ref data );
82.     }
83. }

 

This is excellent advice, on a subject where there’s not enough.

Sometimes optimization is also a valid reason. I’ve had two isolated cases in which using existing Native Containers would have worked, but our tests showed that a hand-built Native Collection did the same thing, but faster. They were faster because we could be specific about data types, about the exact shape of the data that we needed, etc. In one case, we were able to format the data in a specific order as it was being added to the collection, which let us skip an entire job step that would have come after all producers were done adding.

So in those cases, our Native Collections weren’t doing something new, nor were they very reusable. But 9 times out of 10, that’s probably a bad idea, and you’ll end up adding some problem you won’t detect for months. …I hope we didn’t…