How to store tree structure data in DOTS?

Unity Engine
, ,
1

I am developing a game that requires a tree structure for family relationships.
I know that children for example can be stored using DynamicBuffer, but trying to store siblings creates a lot of redundant data (10 children, each with another 9 siblings),it costs O(n2), which doesn’t feel like a good solution.

2

Another way is too add components that keeps an entity relationship to others like Parent, Child, or Sibling.

3

I think it depends on your need.

Need something super-fast for bursted jobs? Custom structs with unmanaged data could work.
Need something simple that involves Entities? Entities with Dynamic Buffers + Relationship components could work.
Need something super-flexible? A managed component with regular C# tree-like data could work.

Can you elaborate on your need: “tree structure for family relationships”?

4

thanks for your reply.
there’s hundreds of characters in my game. Everyone is an entity with CharacterComponent and so on.
now I want to write AI for them. For example: every adult will search a parterner and propose to him or her. Obviously, you can’t propose to your mother or sister or aunt, so I need the relation of between every two characters.

In OOP, It may be a clan tree which has all family’s referecne, Once I get two node, I can calculate the relation between them. But I don’t know how to store the tree struct in DOTS.

It’s easy to store children in DynamicBuffer cause everyone has only one father and one mother. So I can use ChildBufferElement to store children’s entity in father and mother.(however it stored twice). but many character has serveral silibings, I can’t store all silbings for every character. It’s a huge waste of memory.

5

Thanks for the info.
I think the path you’re on is pretty good. You can store Mother/Father/Children on every entity. Then if you need to know your siblings, or your aunt, or your grandma, etc. you can collect them dynamically by navigating the Mother/Father/Children data.

If you have performance issues related to certain queries (e.g siblings are queried every frame) you could chose to cache their results somewhere, at the expense of memory.

If navigating Mother/Father/Children with ComponentLookup is too slow (which should be already pretty fast), you could store the data like this:

public struct Character
{
    public Entity Entity;
    public int MotherIndex;
    public int FatherIndex;
    public int ChildrenBegin; // index in Children array
    public int ChildrenCount;
}

public struct RelationshipStore
{
    public NativeArray<Character> Characters;
    public NativeArray<int> Children;
}

I’ll assume this is slightly faster than ComponentLookup. You could also replace Character’s ints with void* pointers for extra speed, but that might be overkill. NB: Although faster to read, this structure is probably slower to modify.

6

It’s a good solution,I’ll try it.Thank you very much!

1 Like