Does Unity support tree data structures?

Scripting
1

I want to use a data structure and introduce artificial intelligence in my game ( game seems like the traditional ‘dots and boxes’ one that we used to play at school with paper and pencils)

first , I need to build a tree looks like the pic bellow .

  1. the big blue circles : first i create the first node which belong to the first object i clicked on ;the three next circles are the adjacent lines that will form a box (if the 4 nodes are created : box is checked )
  2. every node of the blue ones has also 3 nodes '(there’s lines are common for 2 boxes )
  3. I need only three degrees parent ->child->child of child
    I need suggestions for : which type of trees I should use .
    how I mark a node is checked without deleting it because I’ll need it .
    ( I’m thinking about making a counter increasing with the creation of nodes till 4 but how I’ll mark the node )
    help !:frowning:

3018901--225473--Sans titre.jpg

2

Unity uses .NET, and .NET does not offer tree data structures, probably because they tend to be highly data-dependent and there are many ways they can be implemented. However, based on the diagram you’ve posted, a simple List would do the trick. Each node would simply expose another List containing its child nodes. (.NET also has a LinkedList available, but the tradeoff is much slower access for faster add/remove.)

If you need other tree-like functionality (for example, a balanced b-tree), you’ll either have to write it yourself or poke around with Google, there are many freebie tree examples available across the net. Keep in mind Unity is tied to an older version of .NET right now, so avoid anything dependent on .NET 4 or newer.

public class MyNode
{
    public string nodeColor;
    public List<MyNode> childNodes;
}
3

Note that you can’t serialize such a structure using Unity’s serializer (ie. it can’t be a field in a MonoBehaviour) due to the type being infinitely recursive. So you’ll have to save the data to file yourself.

4

There are a lot of ways to represent a tree.

If you use pointers/references, you can’t automatically serialize it (as Baste explained above), but you use custom serialization to store the nodes in a serializable format such as a simple list when serializing. When deserializing, rebuild your tree structure from the list. See this Unity blog post for lots of info about serialization.

However, in your diagram each of the blue nodes is essentially a 3x4 array of child nodes (i.e., 12 nodes). Since you have 3 blue nodes, the whole thing is a 3x3x4 array (i.e., 36 nodes). You can also represent this with a single 36-element array, which is easily serializable since there’s no recursion:

public Node[] nodes = new Node[36];

If you want the first element of the first blue node, look up [0]. If you want the last element of the second blue node, look up [23], etc. You can define properties or functions to do the math for you, making it nicer to look up nodes.

1 Like