我应该如何安排在四叉树中引用的组件的存储?

我喜欢Unity的实体组件系统方法,我正在做类似的工作。 不过,我不知道我应该在哪里和如何存储组件。

一个简单的答案是: “将组件存储在相应的系统中” – 这是合乎逻辑的(如果不是处理器系统,还有谁对组件感兴趣)和caching友好(连续内存,所以遍历集合/可能会导致更less的caching缺失)。

但是这种方法有两个主要的问题。 其实只有一个产生另一个。 生成的问题更简单,我从这开始:

Behaviour (也就是自定义用户脚本)组件可以被添加到GameObject (也就是实体)中。 Behaviour必须能够获得添加到此对象的其他组件(类似于Unity的MonoBehaviour)。 然而,对象不直接存储任何组件,所以我们必须从相应的系统中查询组件。 在一个简单的世界里,这个查询只能在创建所需的组件之后才能完成,因为它的地址在实际删除之前不会改变。 这样, Behaviour组件可以查询其构造函数/初始化函数中的其他组件,每个人都很高兴。 但是如果其他组件的地址可以改变呢? 其实这是这个问题的根源,它是由下一个产生的:

将组件存储在数组中可以是一件好事,因为它是内存(总线)友好的。 然而,在某些情况下,这并不理想。 当我有一个空间分区树(QuadTree现在)。 我有两个select:

1)

我只能在QuadTree中保持“全局”连续数组表示和存储指针。 但是,这样当我查询属于QuadTree节点的组件并迭代结果时,会引入caching未命中(在内存中来回跳转)。

 // pseudo-code // "global" storage pool<RigidBody> rigidBodies; pool<Mesh> meshes; // etc. QuadTreeNode { // only pointers to the "global" array elements vector<RigidBody*> rigidBodies; vector<Mesh*> meshes; } 

2)

我可以使用基于节点的组件数组,这意味着迭代更加caching友好。 但是当组件必须移动到不同的QuadTree节点时,它必须从当前节点中删除,并且必须复制到新节点。 这意味着组件的内存地址被改变,这也会产生我的第一个问题(不能只查询一次,因为地址可以改变)。

 // pseudo-code // not-partitioned components pool<Behavior> QuadTreeNode { // these are not pointers, but the actual data pool<RigidBody> rigidBodies; pool<Mesh> meshes; } 

我可能select第一个解决scheme,因为cache-miss可能比常量remove-copy和query操作(至less对于“移动”组件)要less得多。

但是,我感兴趣的是对组件的更好的表示/存储,这对caching友好和操作友好。

我会建议第一个解决scheme,但使用指标而不是指针。 如果你调整/重新分配数组(或C ++中的std::vector ),指针仍然会失效,除非你使用展开/模数(或右移位和按位AND)的展开块进行随机访问,如果你顺序访问64位指针而不是32位索引,那么64位也会导致更多的caching未命中,例如

但是,如果四叉树变化很大,则可以通过基数对存储在树叶处的索引进行基数sorting,使四叉树遍历更加caching友好。