复杂的树数据结构

Question

我正在制作一个游戏的物品系统,我们正在制作类似于古老的古典居民邪恶游戏.目前,我正在实施项目组合,您可以将不同的项目相互组合以获得新的内容.并发症来自这样的事实:存在具有多个转换级别的项目,并且每个级别具有多个配合.请允许我澄清一下,我们假设我们有绿色,红色和蓝色草药.你不能组合红色+蓝色,但你可以结合G + B你会得到像GreenBlueHerb或G + R来获得GreenRedHerb,现在如果你将这些结果中的任何一个结合到一个蓝色草本,你会得到一个GreyHerb.正如你从这个例子中看到的那样,对于绿色草本有2级转换,因为它达到第一级,有两个可能的配偶,(红色|蓝色),从那一点到第二级,只有一个配偶(蓝色).

所以我提出了一个有趣的树,涵盖了nLevels所有可能性,而不仅仅是2,层越多,树越复杂,看看这个3级的例子,你在中间看到的三角形形状代表一个item,以及它周围的其他颜色形状代表了它达到下一个级别的可能配合:

有很多不同的组合,我可以首先将我的项目与蓝色组合,然后是红色,然后是绿色,或绿色,然后是红色,然后是蓝色等.达到我的最终水平.我想出了代表所有可能组合的树:

(右边的数字是#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实际上是基本节点,它的项目名称在start(GreenHerb为ex),树有多个级别(你在图片中看到的黑色线条),每个级别都有多个节点每个节点携带一个新项目数据和多个指向的节点(子节点).现在你可能会问为什么需要在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'=蓝色,'010'=绿色,'100'=红色,'011'表示绿色+蓝色,...'111'=灰色(最终级别)

所以现在我解释了一切,首先:我的方法是否正确？如果不是那么是什么？如果是这样,那么我可以使用/ make来实现这个目标的数据结构是什么？如果我提出的数据结构在他们的位置,我怎样才能将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);
    }
}

• 现在，我为什么要做出第一个改变？（要求）因为这允许我在节点之间进行一些通信，这反过来又允许我最终以我想要的方式连接它们（它们在 7 状态树中的连接方式 ^ 上面我的 Q ） 如何？- 在我的项链示例中，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);
}

很清楚吧？- 我只是将根节点连接到第一个级别的节点，然后将级别1的节点连接到级别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适当的地方使用它来划分不同框架上的工作（我'我使用Unity3D）

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

感谢所有试图提供帮助并花时间阅读本文的人。——维克斯