c++ - 避免与 1 :N relationship in entity-component-system 相关的缓存未命中

Question

如何避免实体组件系统 (ECS) 中与 1:N(pirateship-cannon)关系相关的缓存缺失？

例如，一艘PirateShip可以拥有1-100门大炮。 (1:N)
每门大炮都可以随时自由地分离/附加到任何海盗船上。

对于一些reasons 、 PirateShip 和 Cannon 应该是实体。

内存图

在第一个时间步中，当逐渐创建ship/cannon时，ECS内存看起来非常好:-

图像注释:

• 左 = 低地址，右 = 高地址
• 虽然看起来有间隙，但 ShipCom 和 CannonCom 实际上是紧凑数组。

从ship访问cannon信息非常快，反之亦然(伪代码):-

Ptr<ShipCom> shipCom=....;
EntityPtr ship =  shipCom;  //implicitly conversion
Array<EntityPtr> cannons = getAllCannonFromShip(ship);
for(auto cannon: cannons){
    Ptr<CannonCom> cannonCom=cannon;
    //cannonCom-> .... 
}

问题

在后面的时间步长中，一些船/大炮被随机创建/摧毁。
因此，Entity、ShipCom 和 CannonCom 数组周围存在间隙散射。
当我想要分配它们时，我将从池中获取一个随机内存块。

EntityPtr ship = .....  (an old existing ship)
EntityPtr cannon = createNewEntity(); 
Ptr<CannonCom> cannonCom= createNew<CannonCom>(cannon);
attach_Pirate_Cannon(ship,cannon);    
//^ ship entity and cannon tend to have very different (far-away) address 

因此，上面的“非常快”的代码就变成了最底层的代码。 (我介绍过。)

(编辑)我相信底层缓存未命中也会发生在同一艘船内的大炮之间的不同地址。

例如(@是炮塔组件的地址)，

• ShipA 有 turret@01 到 turret@49
• ShipB 有 turret@50 到 turret@99

在后面的时间步中，如果将 turret@99 移动到 ShipA，它将是:-

• ShipA 具有 turret@01 到 turret@49 + turret@99(内存跳转)
• ShipB 有 turret@50 到 turret@98

问题

减少常用关系中的缓存缺失的设计模式/C++ 魔法是什么？

更多信息:

• 在实际情况中，存在大量的 1:1 和 1:N 关系。某种关系专门将某种类型的组件绑定(bind)到某种类型的组件。
• 例如，relation_Pirate_Cannon = (ShipCom:CannonCom)、relation_physical_graphic = (PhysicCom:GraphicCom)
• 只有部分关系经常是“间接”的。
• 当前架构对 Entity/ShipCom/CannonCom 的数量没有限制。
  我不想在程序开始时限制它。
• 我更喜欢不会使游戏逻辑编码变得更加困难的改进。

我想到的第一个解决方案是启用迁移，但我相信这是最后的手段。

Answer 1

一个可能的解决方案是添加另一层间接层。它会减慢速度，但有助于保持阵列紧凑，并有助于加快整个速度。分析是了解它是否真的有帮助的唯一方法。

话虽如此，该怎么做？
Here是对稀疏集的简要介绍，值得先阅读它，以便更好地理解我所说的内容。

不要在同一数组中的项目之间创建关系，而是使用指向的第二个数组。
我们将这两个数组称为“reverse”和“direct”:

• reverse 通过实体标识符(一个数字，因此只是数组中的索引)进行访问。每个槽都在direct数组中包含一个索引。
• direct 被访问，嗯...直接，每个槽都包含实体标识符(即访问反向数组的索引)和实际组件。

每当您添加大炮时，都会获取其实体标识符和direct数组中的第一个空闲槽。设置slot.entity与您的实体标识符并输入 reverse[entity]插槽的索引。每当您删除某些内容时，请复制direct数组中的最后一个元素以保持其紧凑并调整索引以使关系保持不变。
飞船会将索引存储到外部数组(反向)，以便您可以自由地在内部数组中来回切换内容(直接)。

优点和缺点是什么？
好吧，每当您通过外部数组访问大炮时，由于额外的间接层，您都会有一个额外的跳转。无论如何，只要您成功地保持较低的这种方式访问​​次数，并且访问系统中的直接数组，您就有一个紧凑的数组可供迭代，并且缓存未命中次数最少。