用于分层组件存储的结构

Question

我已经在脑海里思考了几天这个问题，还没有得到任何令人满意的结论，所以我想我应该向so团队征求他们的意见。对于我正在开发的游戏，我使用了here和here中描述的组件对象模型。它实际上进行得相当顺利，但我目前的存储解决方案被证明是有限的(我只能通过它们的类名或任意的“系列”名称来请求组件)。我想要的是能够请求一个给定的类型，并迭代通过该类型的所有组件或从该类型派生的任何类型。

考虑到这一点，我首先实现了一个简单的RTTI方案，它按顺序通过派生类型存储基类类型。这意味着，比如说，sprite的RTTI将是: component::renderable::sprite。这使我可以简单地通过比较B:的所有元素，即component::renderable::sprite派生自component::renderable，而不是component::timer，来比较类型A是否派生自类型B。简单，有效，并且已经实现。

我现在想要的是一种以表示层次结构的方式存储组件的方法。首先想到的是使用类型作为节点的树，如下所示：

       component
       /       \
  timer         renderable
  /              /      \
shotTimer   sprite      particle

在每个节点上，我将存储该类型的所有组件的列表。这样，通过请求"component:: renderable“节点，我就可以访问所有可呈现的组件，而不管派生类型是什么。问题是我希望能够使用迭代器访问这些组件，这样我就可以这样做：

for_each(renderable.begin(), renderable.end(), renderFunc);

然后从renderable向下遍历整个树。我使用了一个非常丑陋的map/vector/tree节点结构和一个自定义的向前迭代器来跟踪我所在的节点堆栈。然而，在实现的过程中，我觉得肯定有更好、更清晰的方法……我就是想不出一个：

所以问题是:我是不是把事情变得不必要地复杂化了？有没有我遗漏的一些明显的简化，或者我应该使用的预先存在的结构？或者这只是一个与生俱来的复杂问题，我可能已经做得很好了？

感谢您提供的任何意见！

Answer 1

您应该考虑您需要执行以下操作的频率：

• 遍历树中的tree
• add/remove元素
• 您需要多少个对象才能跟踪

哪个频率更高将有助于确定最佳解决方案

也许不是创建一个复杂的树，而是拥有一个所有类型的列表，并为它派生的每个类型添加一个指向对象的指针。如下所示：

map<string,set<componenet *>>  myTypeList

然后，对于类型为component::renderable::sprite的对象

myTypeList["component"].insert(&object);
myTypeList["renderable"].insert(&object);
myTypeList["sprite"].insert(&object);

通过在多个列表中注册每个obejct，可以很容易地对给定类型和子类型的所有对象执行某些操作

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(),renderFunc);

请注意，std::set和我的std::map构造可能不是最佳选择，这取决于您将如何使用它。

或者可能是一种混合方法，只在树中存储类层次结构。

map<string, set<string> > myTypeList;
map<string, set<component *> myObjectList;

myTypeList["component"].insert("component");
myTypeList["component"].insert("renderable");
myTypeList["component"].insert("sprite");
myTypeList["renderable"].insert("renderable");
myTypeList["renderable"].insert("sprite");
myTypeList["sprite"].insert("sprite");

// this isn't quite right, but you get the idea
struct doForList {
    UnaryFunction f;
    doForList(UnaryFunction f): func(f) {};
    operator ()(string typename) { 
       for_each(myTypeList[typename].begin();myTypeList[typename].end(), func);
   }
}

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(), doForList(myFunc))

Answer 2

答案取决于您需要它们的顺序。您几乎可以选择预购、后购和订购。因此，在广度优先和深度优先搜索中有明显的相似之处，一般情况下，你将很难击败它们。

现在，如果您对问题进行了一点限制，有许多老式的算法可以将任意数据的树存储为数组。在FORTRAN时代，我们经常使用它们。其中一个关键的技巧是在索引( A )*2，索引(A)*2+1处存储A的孩子，比如A2和A3。问题是，如果你的树是稀疏的，你就浪费了空间，并且你的树的大小受到数组大小的限制。但是，如果我没记错的话，您可以通过简单的DO循环以广度优先的方式获取元素。

看看Knuth第三卷，里面有一大堆这样的东西。

Answer 3

如果您想查看现有实现的代码，请参阅牛仔编程页面中引用的Game Programming Gems 5文章，其中提供了我们用于组件系统的代码的一些精简版本(我完成了该文章中描述的系统的大部分设计和实现)。

我需要回去重新检查代码，我现在不能这样做，我们没有像你所展示的那样在层次结构中表示事物。尽管组件存在于代码中的类层次结构中，但运行时表示是一个平面列表。组件只是声明了它们实现的接口的列表。用户可以查询接口或具体类型。

因此，在您的示例中，Sprite和Particle将声明它们实现了RENDERABLE接口，如果我们想对所有渲染器执行某些操作，我们只需循环活动组件列表并检查每个组件。从表面上看，它并不是非常有效，但在实践中它是很好的。它不是问题的主要原因是它实际上并不是一个非常常见的操作。例如，诸如可渲染的对象在创建时会将自身添加到渲染场景中，因此全局场景管理器维护其自己的可渲染对象列表，而无需查询组件系统以获取这些对象。类似于物理学和碰撞组件之类的东西。