Recursion with Structs

Unity Engine
,
1

Hello eveyone, I am trying to create hierarchical tree inside a DOTS Job. My struct layout for the nodes of the tree look like this:

    public unsafe struct Node
    {
        public float3 position;
        public Node* left;
        public Node* right;
    }

And in my struct tree:

public unsafe struct Tree
{
    public Node* _root;
}

The thing that has really gotten me stuck is I was trying to create an array with my struts so I was trying to use NativeArray<Node*> (which you cant do) so then I was trying to use UnsafeUtility with a void* but it is really wonky. You cant use Node* as a type for UnsafeUtility.Malloc and its just a train wreck.

//Node* array
void* _open = UnsafeUtility.Malloc(Count * UnsafeUtility.SizeOf(typeof(IntPtr)), 4, Allocator.Persistent);

I was trying to use this method but it seems things get dereferenced / are null e.g. float3 position is somehow not referenced when I use (Node*)UnsafeUtility.ReadArrayElement(_open, index);

If anyone has some more elegant ideas or If I am just doing this completely wrong any input would be nice!

2

Make a struct called NodeWrapper which stores a Node* as a field with [NativeDisableUnsafePtrRestriction]. Then it should work in NativeArray fine.

1 Like
3

Its that easy! Thanks you!

4

Use index(int) as reference instead of pointer, then it will work with NativeList. pointer will be lost when List reallocate on capacity change. index will work.

1 Like
5

What exactly do you mean by using index(int) as reference instead of pointer.

6 
public struct Tree
{
    public struct Node
    {
        public float3 position;
        public int leftIndex;
        public int rightIndex;
    }

    public NativeList<Node> Nodes;

    public Node GetLeft(Node p) => Nodes[p.leftIndex];
    public Node GetRight(Node p) => Nodes[p.rightIndex];
    public Node Root => Nodes[0];
    public Node this[int i]=>Nodes[i];
}
7

Your tree has only 2 children for each Node. so it is a binary tree. So you don’t need to store any reference. parent/child index can be calculated very easily.
BinaryTree Source

        public struct BinaryTree<T> where T : unmanaged
        {
            public BinaryTree(T rootValue, Allocator allocator, int initialCapacity = 7)
            {
                Nodes = new NativeList<Node>(initialCapacity, allocator);
                Nodes.Add(new Node() { Value = rootValue });
            }

            public struct Node
            {
                public T Value;
            }

            public NativeList<Node> Nodes;

            public int RootIndex => 0;
            public Node Root => Nodes[0];
            public Node this[int i] => Nodes[i];

            public int GetLeftChildIndex(int nodeIndex) => (nodeIndex << 1) + 1;
            public int GetRightChildIndex(int nodeIndex) => (nodeIndex << 1) + 2;
            public int GetParentIndex(int nodeIndex) => (nodeIndex - 1) >> 1;

            public Node GetLeftChild(int nodeIndex) => Nodes[GetLeftChildIndex(nodeIndex)];
            public Node GetRightChild(int nodeIndex) => Nodes[GetRightChildIndex(nodeIndex)];
            public Node GetParent(int nodeIndex) => Nodes[GetParentIndex(nodeIndex)];

            public bool TryGetLeftChild(int nodeIndex, out Node c)
            {
                var cId = GetLeftChildIndex(nodeIndex);
                if (math.asuint(cId) < Nodes.Length)
                {
                    c = Nodes[cId];
                    return true;
                }
                c = default;
                return false;
            }

            public bool TryGetRightChild(int nodeIndex, out Node c)
            {
                var cId = GetRightChildIndex(nodeIndex);
                if (math.asuint(cId) < Nodes.Length)
                {
                    c = Nodes[cId];
                    return true;
                }
                c = default;
                return false;
            }

            public bool TryGetParent(int nodeIndex, out Node p)
            {
                var pID = GetRightChildIndex(nodeIndex);
                if (math.asuint(pID) < Nodes.Length)
                {
                    p = Nodes[pID];
                    return true;
                }
                p = default;
                return false;
            }

            public void PushLeftChild(int nodeIndex, Node n)
            {
                var cId = GetLeftChildIndex(nodeIndex);
                Nodes.Resize(cId, NativeArrayOptions.ClearMemory);
                Nodes[cId] = n;
            }

            public void PushRightChild(int nodeIndex, Node n)
            {
                var cId = GetRightChildIndex(nodeIndex);
                Nodes.Resize(cId, NativeArrayOptions.ClearMemory);
                Nodes[cId] = n;
            }
        }

There could be bug. I just made the tree from algorithm concept. You may want to test it before using.

If the tree is not balanced (left/right branch of any node filled with equal child count).
There will be gaps (Nodes filled with default value (all memory zeroed))

this can be extended to any fixed branch count tree. but power of two branch count runs fastest. as index can be calculated by shift operator <</>>.

2 Likes
8

Wow thanks for the response, this was a lot of help! Could I put this inside a job even though it has a NativeList inside it?

9

Yes