Complex tree data structure

Question

I'm working on an items system for a game that we're making similar to the old classical Resident evil titles. Currently, I'm implementing items combining, where you combine different items with each other to get something new. Complications come from the fact that there exist items that have more than one level of transformation, and more than one mate for each level. Allow me to clarify, let's assume that we have a green, red and blue herbs. You can't combine red+blue, however you can combine G+B you'd get something like a GreenBlueHerb, or G+R to get GreenRedHerb, now if you combine either of these results to a blue herb, you'd get a GreyHerb. As you see from this example, there are 2 levels of transformation for the green herb, for it to reach the first level, there are two possible mates, (red|blue), from that point going to level two, there's only one mate (blue).

So I came up with an interesting tree, covering all possibilities going down nLevels, not just 2, the more the levels the more complex the tree, have a look at this example of 3 levels, the triangle shape you see in the middle represents an item, and the other colored shapes around it represents possible mates for it to reach the next level:

There's a lot of different combinations, I could first combine my item with the blue one, then the red, then the green, or green, then red, then blue, etc. To reach my final level. I came up with this tree representing all the possible combinations:

(Numbers to the right are the #levels, to the left are the #nodes at each level) But as you can see, it's redundant. If you look at the end nodes they should all be one, because they're all leading to the same final result, which is G+R+B. There are actually 7 possible states in total for this situation, here is the right tree:

This makes a lot of sense, notice the huge difference on the number of nodes.

Now my question is, what is the right data structure for this? - I'm pretty sure there's no built-in one for this, so I'm gonna have to make my own custom one, which I actually did, and manage to get it working but with a problem. (One thing worth mentioning is that I'm getting the nodes information from an XML file, by information I mean the itemRequired to reach a node/level and what's gonna be the name of my item at that node, ex: for the green herb to reach the RedGreenHerb state, it 'requires' a RedHerb, when that combination happens, the name "GreenHerb" will change to "RedGreenHerb" and if you're wondering what happens to the RedHerb, it just disappears, I don't need it anymore), here are my data structures:

public struct TransData
{
    public TransData(string transItemName, string itemRequired)
    {
        this.transItemName = transItemName;
        this.itemRequired = itemRequired;
    }
    public string transItemName;
    public string itemRequired;
}

public class TransNode
{
    public List<TransNode> nodes = new List<TransNode>();
    public TransData data;
    public TransNode(TransNode node): this(node.data.transItemName, node.data.itemRequired) { }
    public TransNode(string itemName, string itemRequired)
    {
       data = new TransData(itemName, itemRequired);
    }
}

public class TransLevel
{
    public List<TransNode> nodes = new List<TransNode>();
    public TransNode NextNode { get { return nodes[cnt++ % nodes.Count]; } }
    int cnt;
}

public class TransTree
{    
    public TransTree(string itemName)
    {
        this.itemName = itemName;
    }
    public string itemName;
    public TransNode[] nodes;
    public List <TransLevel> levels = new List<TransLevel>();
    // other stuff...
}

Let me explain: The TransTree is actually the base node, which has the item's name at start (GreenHerb for ex), the tree has a number of levels (the lines in black you see in the pictures), each level has a number of nodes, each node carries with it a new item data and a number of nodes to point to as well (children nodes). Now you might be asking what is the need to put a list of nodes in the TransTree class? - I will answer that after I show you how I'm getting the data from my XML file:

public TransTree GetTransItemData(string itemName)
{
    var doc = new XmlDocument();
    var tree = new TransTree(itemName);
    doc.LoadXml(databasePath.text);

    var itemNode = doc.DocumentElement.ChildNodes[GetIndex(itemName)];
    int nLevels = itemNode.ChildNodes.Count;
    for (int i = 0; i < nLevels; i++) {
       var levelNode = itemNode.ChildNodes[i];
       tree.levels.Add(new TransLevel());
       int nPaths = levelNode.ChildNodes.Count;
       for (int j = 0; j < nPaths; j++) {
            var pathNode = levelNode.ChildNodes[j];
        string newName = pathNode.SelectSingleNode("NewName").InnerText;
        string itemRequired = pathNode.SelectSingleNode("ItemRequired").InnerText;
        tree.levels[i].nodes.Add(new TransNode(newName, itemRequired));
       }
    }
    tree.ConnectNodes(); // pretend these two
    tree.RemoveLevels(); // lines don't exist for now
    return tree;

}

Here's an XML sample to make everything clear: ItemName->Level->Path (which is nothing but a node)->Path data

<IOUTransformableItemsDatabaseManager>
  <GreenHerb>
    <Level_0>
      <Path_0>
        <NewName>RedGreenHerb</NewName>
        <ItemRequired>RedHerb</ItemRequired>
      </Path_0>
      <Path_1>
        <NewName>BlueGreenHerb</NewName>
        <ItemRequired>BlueHerb</ItemRequired>
      </Path_1>
    </Level_0>
    <Level_1>
      <Path_0>
        <NewName>GreyHerb</NewName>
        <ItemRequired>BlueHerb</ItemRequired>
      </Path_0>
    </Level_1>
  </GreenHerb>
</IOUTransformableItemsDatabaseManager>

Now the problem with doing it like that, is that the nodes aren't connected with each other, so what, what does that imply? Well, if an item takes a certain path to a certain level, then we certainly don't need to keep storing the other paths, which it didn't take, so why keeping them in memory? (there's no transforming back, once you take a path, that's it you're obliged to follow that path, and never look back) What I would like to have, is when I take out a node, all the rest of nodes under it will fall as well, which makes sense, but currently the way I'm doing it so far is something like this:

As you can see the nodes are not connected, what's holding them is the levels! which means that, there is no way for me currently to take out a node, in a way that it takes out all its child nodes. (Doing it without the fact that nodes are connected is really tough and a will degrade performance a lot) Which brings us to:

tree.ConnectNodes(); 
tree.RemoveLevels();

I first connect the nodes, and then remove the levels? why, because if I don't, then each node has two references to it, one from its parent node and other from the current level. Now ConnectNode is actually for the long tree I showed, and not for the optimized one that has 7 states:

    // this is an overloaded version I use inside a for loop in ConnectNodes()
    private void ConnectNodes(int level1, int level2)
    {
        int level1_nNodes = levels[level1].nodes.Count;
        int level2_nNodes = levels[level2].nodes.Count;

        // the result of the division gives us the number of nodes in level2,
        // that should connect to each node in level1. 12/4 = 3, means that each
        // node from level1 will connect to 3 nodes from level2;
        int nNdsToAtch = level2_nNodes / level1_nNodes;
        for (int i = 0, j = 0; i < level2_nNodes; j++)
        {
            var level1_nextNode = levels[level1].nodes[j];
            for (int cnt = 0; cnt < nNdsToAtch; cnt++, i++)
            {
                var level2_nextNode = levels[level2].nodes[i];
                level1_nextNode.nodes.Add(new TransNode(level2_nextNode));
            }
        }
   }

This is ultimately what I want to have on my other tree, but I don't know how to. I want to connect the nodes and form the 2nd tree I showed, which is relatively simpler than 4 levels for ex, I couldn't even connect the nodes in paint! (when I tried 4 levels)

If you stare at it, you'll find some resemblance to binary numbers, here's my tree in a binary form:

001
010
100
011
101
110
111

Each '1' represents an actual item, '0' means empty. From my tree, '001'=Blue, '010'=Green, '100'=Red, '011' means Green+Blue, ... '111'=Grey (final level)

So now I got everything explained, first: is my approach correct? If not then what is? If so, then what is the data structure I could use/make to achieve this? and if the data structures I came up with are in their place, how can I store the data from the XML file to my data structure in a way that, connects the nodes together so whenever I take out a node it takes out its children nodes with it?

Thanks a lot in advance for your help and patience :)

EDIT: Interesting to note that, this whole system is for items that occur only once throughout the game (gets picked up once). This is why whenever I take a path, I remove it from memeory, and also whenever I pick up an item, I remove its entry from the database because I won't encounter it again.

EDIT: Please note that I don't only represent my items via just strings, they have a lot of other properties. But in this situation I only care about their names, that's why I'm dealing with strings.

Answer 1

What I don't like in this solution :

• Simple solutions is best solutions
• Difficult to maintain since your xml is based on a graph.
• Don't really take advantage of OOP
• Source of bugs
• Probable use of Reflection for small problems (I say small because if your do a such game you'll face far more difficults problems ;) ). This implies unnecessary complexity.

What I like in this solution :

• You have just perfectly understood the problem. Each item have a list of transormations with some other objects. Now the problem is how to represent (and not store) it

What i would have do (juste IMHO, your solution is good, too) : use OOP in a node-only point of view. So your tree will become a state machine (as you were speaking about path ;) ) if you want to attach that to a data structure.

public class InventoryObject
{
    protected Dictionnary<Type, InventoryObject> _combinations = new Dictionnary<Type, InventoryObject>();

    public InventoryObject() {}       

    public InventoryObject Combine(InventoryObject o)
    {
       foreach (var c in _combinations)
          if (typeof(o) == c.Key)
            return c.Value

       throw new Exception("These objects aren't combinable");
    }
}

public class BlueHerb : InventoryObject
{
    public Herb()
    {
       _combinations.Add(RedHerb, new BlueRedHerb());
       _combinations.Add(GreenHerb, new BlueGreenHerb());
    }
}

public class BlueRedHerb: InventoryObject
{
    public BlueRedHerb()
    {
       _combinations.Add(GreenHerb, new GreyHerb());
    }
}

Then just call BlueHerb.Combine(myRedHerb); to get the result. You can also do BlueHerb.Combine(myStone); and easily debug.

I try to keep my example as simple as possible. A lot of modifications can be done in order to light up the code (a class Herb, a class CombinedHerb, use LINQ queries, etc...)