Resolved C# scripting a Family-tree -esque hierachy for classes.

Hey there,

I am having difficulty trying to wrap my head around making something like this: (Purely in terms of data structure, not graphical)


What I am trying to achieve is somekind of data structure where each square is for example a Class Rank with children(?) and parents(?) that are the same type of Class Rank, kind of like GameObjects in the editor hierarchy, except not with gameobjects but with Classes, ScriptableObjects or anything really.

At the same time however each square/class should also be easily editable to hold different types of data (I was thinking maybe ScriptableObjects?)

 

Looks like a basic tree, except can have multiple parents? Looks roughly like this:

class Employee {
public int rank;

public List<Employee> Underlings;
public List<Employee> Bosses; // <- normally this would be only 1 parent

Are you worried about enforcing the exact number of employees at each rank. For example, there must be 3 Capos, and every Gang must have 2 Hench? You could create a separate table for that:

class RankLimits_t {
public int bossCount;
public int underlingCount;
}

RankLimits_t[] RankLimits; // size this to the # of ranks (7)

When you create someone of rank n, you could manually make the Underling and Boss lists of the correct size, leaving nulls for the missing ones.

 

This I got except the Employee class is called Rank (imagine it more like a slot where I can insert a Character class), that naming is less confusing to me but the logic remains the same.

Yes that is the idea.

This I have currently worked into a ScriptableObject RankData, since I want to be easily able to edit the bossCount and underlingCount if I need to rebalance.

The main issue that I am struggling with however is how to keep this orderly within a Family class, do I make one big list of size 56 with all the ranks and then for each entry set the references to the bosses and underlings? I don't like the lack of hierarchy in such a large list.

Or do I make lists for each rank tier?

Or do I make it so that I make for example just the don that creates subordinates, which then create new subordinates etc. And reference each rank by going through the don class? (I find this idea hard to explain, but I am curious if there is a neat and orderly way of doing something like that.)

 

I wrote this very dirty code just now and I feel disgusted by it:
I am not wrong to feel that way am I? (that is, if you can make any sense out of this code)

Code (CSharp):

1.  
2. public class Family
3.     {
4.         public string familyName;
5.         public Color familyColor;
6.         public List<Character> familyMembers = new List<Character>();
7.  
8.  
9.         public RankData[] rankData; //ScriptableObjects array added through inspector
10.  
11.         //Array for each rank tier.
12.         public Rank[] DON;
13.         public Rank[] SOTTOCAPO;
14.         public Rank[] CAPO;
15.         public Rank[] MAFFIA;
16.         public Rank[] GANGLEADER;
17.         public Rank[] GANGSTER;
18.         public Rank[] HENCHMAN;
19.  
20.         public Family(string name, Color color)
21.         {
22.             familyName = name;
23.             familyColor = color;
24.  
25.             CreateFamilyRanks(); // Create the rank layout for the family on family creation.
26.         }
27.  
28.         public class Rank
29.         {
30.             public List<Rank> superiors; //List of superior Ranks
31.             public List<Rank> subordinates; //List of subordinate Ranks
32.  
33.             public Rank()
34.             {
35.  
36.             }
37.         }
38.  
39.         public void CreateFamilyRanks()
40.         {
41.             //Set the size of rank arrays based of how many of each rank are allowed according to their RankData ScriptableObject
42.             DON = new Rank[rankData[0].maxAmount];                  //size = 1
43.             SOTTOCAPO = new Rank[rankData[1].maxAmount];            //size = 1
44.             CAPO = new Rank[rankData[2].maxAmount];                 //size = 3
45.             MAFFIA = new Rank[rankData[3].maxAmount];               //size = 12
46.             GANGLEADER = new Rank[rankData[4].maxAmount];           //size = 3
47.             GANGSTER = new Rank[rankData[5].maxAmount];             //size = 12
48.             HENCHMAN = new Rank[rankData[6].maxAmount];             //size = 24
49.  
50.             //Set the superior and subordinate rank references for each individual rank tier.
51.             SetSuperiorsAndSubordinates(DON,SOTTOCAPO,false);
52.             SetSuperiorsAndSubordinates(SOTTOCAPO, CAPO, false);
53.             SetSuperiorsAndSubordinates(CAPO, MAFFIA, false);
54.             SetSuperiorsAndSubordinates(MAFFIA, GANGLEADER, true);
55.             SetSuperiorsAndSubordinates(GANGLEADER, GANGSTER, false);
56.             SetSuperiorsAndSubordinates(GANGSTER, HENCHMAN, false);
57.         }
58.  
59.         public void SetSuperiorsAndSubordinates(Rank[] superior, Rank[] subordinate, bool reverse)
60.         {
61.             if (!reverse)
62.             {
63.                 for (int sup = 0; sup < superior.Length; sup++)
64.                 {
65.                     for (int sub = sup * (subordinate.Length / superior.Length); sub < (sup + 1) * (subordinate.Length / superior.Length); sub++)
66.                     {
67.                         superior[sup].subordinates.Add(subordinate[sub]);
68.                         subordinate[sub].superiors.Add(superior[sup]);
69.                     }
70.                     //example:
71.                     //capo(sup) = 0 , add maffia(sub) 0,1,2,3 as subordinate
72.                     //capo(sup) = 1 , add maffia(sub) 4,5,6,7 as subordinate
73.                     //capo(sup) = 2 , add maffia(sub) 8,9,10,11 as subordinate
74.                 }
75.             }
76.             else
77.             {
78.                 for (int sub = 0; sub < subordinate.Length; sub++)
79.                 {
80.                     for (int sup = sub * (superior.Length / subordinate.Length); sup < (sub + 1) * (superior.Length / subordinate.Length); sup++)
81.                     {
82.                         superior[sup].subordinates.Add(subordinate[sub]);
83.                         subordinate[sub].superiors.Add(superior[sup]);
84.                     }
85.                     //example:
86.                     //maffia = 0 , add gangleader 0 as subordinate
87.                     //maffia = 1 , add gangleader 0 as subordinate
88.                     //maffia = 2 , add gangleader 0 as subordinate
89.                     //maffia = 3 , add gangleader 0 as subordinate
90.                     //maffia = 4 , add gangleader 1 as subordinate
91.                     //maffia = 5 , add gangleader 1 as subordinate
92.                     //maffia = 6 , add gangleader 1 as subordinate
93.                     //maffia = 7 , add gangleader 1 as subordinate
94.                     //maffia = 8 , add gangleader 2 as subordinate
95.                     //maffia = 9 , add gangleader 2 as subordinate
96.                     //maffia = 10 , add gangleader 2 as subordinate
97.                     //maffia = 11 , add gangleader 2 as subordinate
98.                 }
99.             }
100.         }
101.     }
102.  

 

Having a single size 56 list, then using math to find each item is a real thing. The items don't even need links to their parents and children -- item 12 automatically has item 3 for a parent and 31, 32 and 33 as children (I just made those up). But it seems like a pain here. It's done with binary lists as an extreme space-saving measure.

The thing is, you probably want links to parents and children. Once you have those, a single link to the Boss is all you need in your Family class. Other lists are just for fun. They can't hurt -- just maybe waste some of your time. I'd probably save them until you know what sort of operations you want to perform. But it's pretty much the same way databases make indexes (I think). In principle having extra redundant lists over various properties is just great. Make a list of everyone who's boss is left-handed, if you think you'll need it.

 

Right that makes sense for the most part.

Well... except for that math maybe, since that math would have to create a pattern of parents and children references between all the list items in such a way that it forms the exact same pattern like in the image. That seems like it would not be a short or comprehensible bit of code.

 

You essentially want to implement a non-binary tree via level order traversal. (Keep in mind, it can be any traversal, this is just most likely the easiest one to modify down the line if you want to rebalance stuff)
This should solve most of your issues:
https://www.geeksforgeeks.org/level-order-tree-traversal/

If you've done this before, it should be a piece of cake and the hardest part will be figuring out how to pass the input in a correct, readable manner.

If not, well then good luck. First, I would determine if Capo's will ALWAYS have 4 Maf.'s and similar rules. If yes, then you will be able to pass in the input a bit nicer. If not, then you'll have to figure out which Maf's go under which Capo's.
Once you figure out some of the basic rules for creating the tree, you'll want to go through your input a step at the time and create a node for each Rank. Then, you will connect that Rank with the following Ranks via a tree traversal of your choice.

Basically, determine some of the basic rules, go step by step to create the tree from top to bottom.


Now, if you are concerned about how you are going to access a specific node in that tree, well, you are going to be using a tree traversal of your choice. Is it cheap? Not really? But, unless you have hundreds of Ranks in your tree, it's all good.

 

That seems like it's a great link, unfortunately I can't wrap my head around the terminology (naming convention) they use. For example what they mean by "level", "root", "tree", "node". I can't tell which term is which component of the tree they show in the image. Other than that the code they provide uses symbols that I am not familiar with (* , << , ->). Sorry but I am somewhat of a beginner to intermediate programmer and most of that experience is programming in C# unity (couple of years programming fairly basic structures).

What do you mean with input exactly.

 

Those symbols aren't used in C# (at least, not in the way you are referring to). Once you scroll down to "Implementation" you will see that you can change in which language the code is displayed. Simply switch to C# and it should feel a bit more familiar.

Here you can read a bit more on the data structure itself:
https://www.geeksforgeeks.org/binary-tree-data-structure/
https://www.geeksforgeeks.org/binary-tree-set-1-introduction/

I'm referring to the format in which you pass data to the method that constructs your tree.
Take a look at this link: https://www.geeksforgeeks.org/construct-tree-inorder-level-order-traversals/
You'll notice two variables in the very first code section, "in[]" and "level[]". Here, their input is just an array of integers. In the examples below, you'll see how they use that array to construct the tree. In your case, it might not be an array of integers but an array of classes Rank. If this is really a complex system you are trying to make, you might opt-in to make a custom editor, but if it's just a one-time thing, I wouldn't bother.

 

Trees and recursive tree traversals are normal Com Sci stuff. You can probably find a boring intro to it if the game-oriented one seems funny. Anything with parents and children we call a tree. Think of it as upside-down. The top is the root, everything (including the root) is a node, nodes with no children are leaves, nodes with children are branches. The depth a of node is how far it is down from the root.

Going through a whole tree from the root requires a sneaky trick where a function calls _itself_ on each child, called recursion. Here's a basic Unity "make me and all my kids be red":

Code (CSharp):

1. void makeAllRed(Transform root) {
2.   Renderer rr = root.GetComponnent<Renderer>();
3.   // skip empties:
4.   if(rr!=null) rr.material.color=Color.red;
5.  
6.   // run this same function with each child as the root:
7.   foreach(Transform c in root)
8.     makeAllRed(c); // <-calls ITSELF!! (but on a child, this time)
9. }

It's practically magic the way this crawls down the side, pops back and crawls down the next, no matter how the children are arranged, and touches everything exactly once.

But in your case, you know the exact structure, and the total depth. A recursive tree-traversal is for when you don't: some Capo has 6 Maf, another have none; and some henchmen have sub-henchmen, and of those have sub-sub-henchmen. Plus the way a gang-leader works for 4 Maf's would break it -- what you have is technically not a tree.