data-oriented-design - 如何处理连续分配中的对象删除？

Question

我最近发现了面向数据设计的好处。它看起来非常令人印象深刻。要点之一是按类型和访问对数据进行分组，不是全部放在对象中，而是放在数组中，以防止缓存未命中并进行更好的处理。

所以在游戏中我们仍然有实例，用户可以销毁它们中的任何一个(不仅仅是数组中的最后一个)。我不知道如何有效地处理数组中间的对象删除。

我有一个想法:拥有 isAlive值，但这将对条件数量造成相当大的影响，因为每个对象在处理、绘制、...

另一个想法是移动整个数组以填充必须删除的空间，但这会在删除时消耗大量资源。

人如何在国防部处理这个问题？

所以提出要求:

它必须是数组，以减少 DOD 中描述的缓存未命中

它必须具有快速随机位置对象删除，最大 o(log n)

对象自创建以来就不能移动，因为它们可能在未知的地方被引用，因此会导致程序错误行为

Answer 1

其实很简单，不要使用直接引用。使用一个间接层，例如 ID。例如:

假设您有一个 FooManager 来管理您所有的 Foo“对象”(不是 OOP 意义上的对象，每个 Foo 属性的数组集合)。据我了解，您现在所做的只是返回一个索引。假设 Foo #42 是数据位于所有数组索引 42 处的 Foo。现在您要删除 Foo #42，这会在您的阵列中造成一个洞。您可以移动所有其他数组条目，但 Foo #43 不再指向实际索引 43。

所以我们添加一个 ID 表，而不是返回索引，而是返回一个 ID。当您创建一个新的 Foo 时，您将其数据添加到数组中的第一个空闲索引(假设为 42)。然后生成一个新的未使用的 ID(比如说 1337)。现在你可以更新 ID 表(一个(散列)映射非常适合这个)说 ID 1337 指向索引 42。现在你可以将 ID 1337 返回给调用函数。 (注意调用函数永远不会发现数据实际存储在哪里，这是不相关的信息)

下次需要从另一段代码更新 Foo 时，将使用 ID。因此 FooManager 的 setBar 函数将使用 ID 1337 和新的 Bar 值作为参数调用。 FooManager 在其 ID 表中查找 1337，发现它仍位于索引 42 处，并使用新的 Bar 值更新 Bar 数组索引 42。

现在这是系统获取它的值的地方，让我们删除 Foo 1337。调用 FooManager 的 removeFoo 时，ID 为 1337 作为参数。它查找 1337，它位于索引 42。但是，与此同时，添加了 10 个新的 Foo。所以我们现在可以做的只是将索引42的值替换为52的值，有效地将52移动到42。这在旧系统中会导致一个大问题，但现在我们只需要更新索引表。所以我们查找哪个 ID 指向 52(假设它是 1401)并将其更新为 42。下次有人尝试更新 ID 为 1401 的 Foo 时，它在索引表中查找它并发现它位于索引 42。

所以我们将数据保存在连续内存中，删除只需要非常少的数据复制操作(Foo 的每个属性一个副本)，而 FooManager 的“外部”代码甚至从未意识到发生了什么。它甚至解决了无效引用问题。假设某些代码仍然具有已删除的 1337 ID(悬空引用，这很糟糕!)，当它尝试访问/更改它时，FooManager 查找它，发现 1337 不存在(不再存在)并且可以生成一个很好的干净警告/error 和 callstack，它可以让你直接识别哪些代码仍然有悬空引用!

只有一个缺点，就是在 ID 表中进行了额外的查找。现在哈希表可以非常快，但是每次修改 Foo 对象时它仍然是一个额外的操作。但是，在大多数情况下，从经理外部访问的发生率远低于从经理内部访问的发生率。当您拥有 BulletManager 时，它会在每一帧更新每个项目符号，但访问项目符号以更改/请求某些内容以及调用创建/删除项目符号的可能性较小。
如果情况正好相反，您可能应该更新数据结构以针对这种情况进行优化。再说一次，在这种情况下，数据在内存中的位置不再重要，因此您可以忍受数组中的“漏洞”，甚至使用完全不同的数据布局。