c# - 复杂的树数据结构

Question

我正在为我们正在制作的一款游戏的项目系统工作，该系统类似于古老的经典生化危机游戏。目前，我正在实现项目组合，您可以将不同的项目相互组合以获得新的东西。复杂性来自这样一个事实，即存在具有多个转换级别的项目，并且每个级别都有多个配对。请允许我澄清一下，让我们假设我们有绿色、红色和蓝色的药草。你不能结合 red+blue，但是你可以结合 G+B，你会得到类似GreenBlueHerb或 G+R 得到GreenRedHerb的东西，现在如果你将这些结果中的任何一个结合到蓝色药草中，你会得到一颗灰草. 正如你从这个例子中看到的，绿色药草有 2 级转化，要达到第一级，有两个可能的伴侣，（红色|蓝色），从那个点到第二级，只有一个伴侣（蓝色的）。

所以我想出了一个有趣的树，它涵盖了nLevels的所有可能性，而不仅仅是 2，级别越多树越复杂，看看这个 3 级别的例子，你在中间看到的三角形代表一个项目，它周围的其他颜色形状代表它可能达到下一个级别的伙伴：

有很多不同的组合，我可以先将我的项目与蓝色的组合，然后是红色，然后是绿色，或者绿色，然后是红色，然后是蓝色，等等。达到我的最终水平。我想出了代表所有可能组合的这棵树：

（右侧的数字是#levels，左侧是每个级别的#nodes）但是正如您所看到的，它是多余的。如果您查看末端节点，它们应该都是一个，因为它们都导致相同的最终结果，即 G+R+B。这种情况实际上总共有 7 种可能的状态，这里是正确的树：

这很有意义，请注意节点数量的巨大差异。

现在我的问题是，什么是正确的数据结构？- 我很确定没有内置的，所以我将不得不制作我自己的自定义一个，我实际上做了，并设法让它工作但有一个问题。（值得一提的是，我正在从 XML 文件中获取节点信息，信息是指达到节点/级别的itemRequired以及该节点上我的项目的名称，例如：对于绿色药草要达到RedGreenHerb状态，它“需要”一个RedHerb，当这种组合发生时，名称“ GreenHerb ”将更改为“ RedGreenHerb ”，如果您想知道RedHerb会发生什么，它就消失了，我不再需要它了），这是我的数据结构：

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...
}

让我解释一下：TransTree实际上是基础节点，它在开始时具有项目的名称（例如 GreenHerb），树有许多级别（您在图片中看到的黑色线条），每个级别都有许多节点，每个节点都带有一个新的项目数据和一些要指向的节点（子节点）。现在您可能会问在类中放置节点列表有什么需要TransTree？- 在我向您展示如何从我的 XML 文件中获取数据后，我会回答这个问题：

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;

}

这是一个 XML 示例，可以让一切变得清晰：ItemName->Level->Path（只不过是一个节点）->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>

现在这样做的问题是，节点之间没有相互连接，那又如何，这意味着什么？好吧，如果一个项目通过某个路径到达某个级别，那么我们当然不需要继续存储它没有采用的其他路径，那么为什么要将它们保存在内存中呢？（没有变回，一旦你走了一条路，就是你有义务沿着那条路走，永远不要回头）我想要的，是当我取出一个节点时，它下面的所有其余节点也会下降，这是有道理的，但目前我目前的做法是这样的：

正如你所看到的，节点没有连接，它们是关卡！这意味着，我目前无法以取出所有子节点的方式取出节点。（在没有节点连接的情况下这样做非常困难，并且会大大降低性能）这让我们：

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

我先连接节点，然后删除关卡？为什么，因为如果我不这样做，那么每个节点都有两个对它的引用，一个来自其父节点，另一个来自当前级别。现在ConnectNode实际上是针对我展示的长树，而不是针对具有 7 个状态的优化树：

    // 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));
            }
        }
   }

这最终是我想在我的另一棵树上拥有的，但我不知道如何去做。我想连接节点并形成我展示的第二棵树，这比 4 级相对简单，我什至无法连接绘画中的节点！（当我尝试了 4 个级别时）

如果你盯着它看，你会发现它与二进制数有一些相似之处，这是我的二进制形式的树：

001
010
100
011
101
110
111

每个“1”代表一个实际项目，“0”表示空。从我的树中，'001'=Blue，'010'=Green，'100'=Red，'011' 表示 Green+Blue，...'111'=Grey（最终级别）

所以现在我得到了解释，首先：我的方法正确吗？如果不是，那是什么？如果是这样，那么我可以使用/制作的数据结构是什么？如果我想出的数据结构在他们的位置，我如何将数据从 XML 文件存储到我的数据结构中，以便将节点连接在一起，这样每当我取出一个节点时，它就会取出它的子节点用它？

非常感谢您的帮助和耐心:)

编辑：有趣的是，整个系统适用于在整个游戏中仅出现一次的物品（被拾取一次）。这就是为什么每当我选择一条路径时，我都会将它从内存中删除，而且每当我拿起一个项目时，我都会从数据库中删除它的条目，因为我不会再遇到它了。

编辑：请注意，我不仅通过字符串表示我的项目，它们还有很多其他属性。但在这种情况下，我只关心他们的名字，这就是我处理字符串的原因。

Answer 1

好的，终于在摆弄并盯着整个系统几个小时之后，我昨天想出了一个想法，我实现了它，它运行得很好:) 我刚刚在 3 级转换上对其进行了测试，它就像魔法。（图片只显示一个组合，但我向你保证，所有组合都有效）

请允许我分享我的解决方案。我必须对我以前的系统进行一些调整，我将首先说明这些调整是什么，然后我为什么要进行每个调整。

• 我更改了存储在每个节点上的数据。在我以前的方法中，我让每个节点都依赖于前一个节点，现在，节点要求直接来自根。

这是结构现在的样子：

public struct TransData
{
    public TransData(string itemName, List <string> itemsRequired)
    {
        this.itemName = itemName;
        this.itemsRequired = itemsRequired;
    }
    public string itemName;
    public List <string> itemsRequired;
}

节点构造函数：

public TransNode(string itemName, List <string> itemsRequired)
{
    data = new TransData(itemName, itemsRequired);
}

现在如何处理需求的示例：

Necklace L.1_A: Requires BlueGem
Necklace L.1_B: Requires GreenGem
Necklace L.1_C: Requires RedGem
Necklace L.2_A: Requires BlueGem AND GreenGem
Necklace L.2_B: Requires GreenGem AND RedGem
Necklace L.2_C: Requires RedGem AND BlueGem
Necklace L.3_A: Requires RedGem AND BlueGem AND GreenGem

XML 现在是：

<IOUTransformableItemsDatabaseManager>
    <Necklace>
        <Level_0>
            <Path_0>
                <NewName>RedNecklace</NewName>
                <ItemsRequired>
                    <Item_0>Red</Item_0>
                </ItemsRequired>
            </Path_0>
            <Path_1>
                        .......
            </Level_0>
        <Level_1>
            <Path_0>
                <NewName>RedGreenNecklace</NewName>
                <ItemsRequired>
                    <Item_0>Red</Item_0>
                    <Item_1>Green</Item_1>
                </ItemsRequired>
            </Path_0>
            <Path_1>
                  .....
        </Level_1>
        <Level_2>
            <Path_0>
                <NewName>RedGreenBlueNecklace</NewName>
                <ItemsRequired>
                    <Item_0>Red</Item_0>
                    <Item_1>Green</Item_1>
                    <Item_2>Blue</Item_2>
                </ItemsRequired>
            </Path_0>
        </Level_2>
    </Necklace>
</IOUTransformableItemsDatabaseManager>

• 我在树中添加了一个root节点，并删除了nodes它的列表，这更有意义。之前nodes的列表现在等于root.nodes

这是树现在的样子：

public class TransTree
{
    //public string itemName;
    //public List <TransNode> nodes;
    public List <TransLevel> levels = new List<TransLevel>();
    public TransNode root { private set; get; }
    public TransTree(string itemName)
    {
    //  this.itemName = itemName;
        root = new TransNode(itemName, null);
    }
}

• 现在，我为什么要进行第一次更改？（要求）因为这让我可以在节点之间进行一些通信，这反过来又让我最终以我想要的方式连接它们（它们在我的 Q 上面的 7 状态树中连接的方式） 如何？- 在我的项链示例中，L.1_A 和 L.2_A 之间有什么联系？答案是，L.1_A 具有 L.2_A 的要求之一，即 BlueGem，它们都有共同点，这使我们得出结论：

每当中间相隔一层的两个节点有共同点时，上一层的节点应该指向上一层

所以我所做的只是遍历一个级别中的所有节点，并将该级别中的每个节点与下一级中的每个节点进行比较，如果第一级中的节点有一个要求下一级中的节点有，那就是一个连接：

public void ConnectNodes()
{
   for (int i = 0; i < levels.Count - 1; i++)
       ConnectNodes(i, i + 1);
   ConnectRoot();
}
private void ConnectNodes(int level1, int level2)
{
    int level1_nNodes = levels[level1].nodes.Count;
    int level2_nNodes = levels[level2].nodes.Count;
    for (int i = 0; i < level1_nNodes; i++)
    {
        var node1 = levels[level1].nodes[i];
        for (int j = 0; j < level2_nNodes; j++)
        {
            var node2 = levels[level2].nodes[j];
            foreach (var itemReq in node1.data.itemsRequired)
            {
                if (node2.data.itemsRequired.Contains(itemReq))
                {
                    node1.nodes.Add(node2);
                    break;
                }
            }
        }
     }
}

注意非常重要的一行：

ConnectRoot();

public void ConnectRoot()
{
    foreach (var node in levels[0].nodes)
       root.nodes.Add(node);
}

很清楚吧？- 我只是将根节点连接到第一层的节点，然后将level1的节点连接到2，将2连接到3等。当然，我必须在清除关卡之前这样做。那没有改变：

// fetching the data from the xml file
    tree.ConnectNodes();
    tree.RemoveLevels();

为什么我要进行第二次更改？（将根节点添加到树中）。好吧，您可以清楚地看到拥有根节点的好处，这更有意义。但是我实现这个根本想法的主要原因是轻松地消除我不会采用的节点。我在我的Q中提到，每当我走一个路径/节点时，同一级别的节点应该没有了，因为就是这样，我已经走了一条路，没有回头路。有了根在手，现在我可以轻松地说：

tree.SetRoot(nodeTakenToTransform);

无需检查我没有采用的节点并将它们清空，只需将树的根更改为我采用的节点，这有额外的好处，可以减轻我将树视为某种链表的负担， （要访问树下的一个节点，我必须通过根，以及根和我要访问的节点之间的关系，最后到达我的目的地） - 每次转换后，根下降一级，我需要的只是现在要访问的是根的节点。

还剩下一个问题。这是我的定制字典中处理项目的方法，当项目转换时，它“通知”字典采取必要的操作（更新其键、值等）

public void Notify_ItemTransformed(TransTree itemTree, TransNode nodeTaken)
{
   var key = new Tuple<string, string>(itemTree.root.data.itemName, nodeTaken.data.itemsRequired[0]);
   itemTree.SetRoot(nodeTaken);
   itemTree.UpdateNodesRequirements(itemTree.root); // take note here
   RemoveKey(key);
   RegisterItem(itemTree);
}

做什么itemTree.UpdateNodesRequirements(itemTree.root)？我的第一个更改引入了一个问题。例如：当我到达 L.1_A 时，我已经拥有BlueGem了吗？否则我不会达到这个水平。但问题是所有节点，在这个级别之后也需要BlueGem，现在仍然需要它，即使我有它！他们不应该要求它，即。BlueGreenNecklace现在应该只需要一个GreenGem - 这就是为什么现在我必须通过从我的新根开始递归地更新这些节点要求：

tree.SetRoot(nodeTaken);
tree.UpdateNodesRequirements(tree.root);

这是方法：

public void UpdateNodesRequirements(TransNode node)
{
    foreach (var n in node.nodes)
    {
        if (n.data.itemsRequired.Contains(root.data.itemsRequired[0]))
            n.data.itemsRequired.Remove(root.data.itemsRequired[0]);
        if (n.nodes != null && n.nodes.Count > 0)
            UpdateNodesRequirements(n);
    }
}

我要说的是，“亲爱的下一级节点，如果您需要我已经拥有的东西，请删除该要求” - 就是这样 :) 希望你喜欢我的文章 XD - 我将在问题的更新中放入我的下一个视频演示它出来了。

性能方面？嗯，有几个地方我可以做一些优化，但现在，用 3 个级别测试它真的很好，一点也不降级。我怀疑我的游戏设计师会想出需要超过 4 个级别的东西，但即使他这样做了，我的代码也应该足够快，如果没有，我可以yield return null在适当的地方使用，将工作划分到不同的帧上（I' m 使用 Unity3D)

我真正喜欢这个解决方案的是它适用于所有类型的转换树，即使它不是对称的，对于 nPaths 和 nLevels :)

感谢任何试图提供帮助并花时间阅读本文的人。-- 烦恼

Answer 2

我不喜欢这个解决方案：

• 简单的解决方案是最好的解决方案
• 由于您的 xml 基于图表，因此难以维护。
• 不要真正利用 OOP
• 错误来源
• 可能Reflection用于小问题（我说小是因为如果你做这样的游戏，你将面临更多困难的问题；））。这意味着不必要的复杂性。

我喜欢这个解决方案：

• 你刚刚完全理解了这个问题。每个项目都有一个与其他一些对象的转换列表。现在的问题是如何表示（而不是存储）它

我会做什么（恕我直言，您的解决方案也很好）：在仅节点的角度使用 OOP。因此，如果您想将树附加到数据结构上，您的树将成为状态机（正如您所说的路径；））。

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());
    }
}

然后只需调用BlueHerb.Combine(myRedHerb);即可获得结果。您也可以BlueHerb.Combine(myStone);轻松地进行调试。

我尽量让我的例子尽可能简单。可以进行很多修改以点亮代码（一个类Herb、一个类CombinedHerb、使用 LINQ 查询等......）