网站搜索

javascript - 有没有更好的数据结构用于存储组件及其相关实体？

我正在用 Javascript（具体来说是 Typescript）编写一个小型的实体组件系统（ECS），目前它可以运行，但我想知道它是否可以在底层更高效。ECS 的工作方式是实体基本上只是组件的集合。所以，一个玩家实体可能有一个 HealthComponent、PositionComponent、SpriteComponent 等组件。然后你可以创建一个 RenderingSystem，它查询所有拥有 PositionComponent 和 SpriteComponent 的实体，然后进行渲染。像这样：

for (let entity of scene.query(CT.Position, CT.Sprite) {
  // draw entity
}

为了在查询时提高效率，而不是每次都遍历场景中的每个实体来查看它是否具有 Position 组件和 Sprite 组件，我们所做的是在第一次查询调用后缓存它，然后保持更新，这样每次查询调用时就可以直接返回实体列表，而不必每次都先遍历所有实体的完整列表。

所以，作为一个例子，缓存可能看起来像这样：

{ "6,1,20" => Map(1) }
{ "2,3,1,6" => Map(1) }
{ "2,3" => Map(31) }
{ "9" => Map(5) }
{ "2,8" => Map(5) }
{ "29,24,2" => Map(5) }

// etc..

这些数字指的是枚举值的数值，例如 CT.Position、CT.Sprite 等。在这个例子中，CT.Position 是 2，CT.Sprite 是 3，并且有 31 个实体拥有这两个组件。因此，当查询拥有这两个组件的所有实体时，我们可以直接返回该实体列表，而不是每次都重新计算。

这一切都可以工作，但效率不是很高，因为将一个实体添加（以及移除！）到场景中是一个 O(n) 操作，同时还涉及大量的字符串拆分和拼接。你需要遍历缓存中的每一项，以查看该实体的组件列表是否被该条目包含。

有没有办法将这个改进得更接近 O(log n)，或者最好是 O(1)？请让我知道这是否完全清楚，或者是否有任何需要澄清的细节。

这是一个 Typescript Playground URL 重现示例的链接

答案＃1

我预计缓存中的查询数量会相当少，因为每个查询都会单独与处理结果的一堆代码关联起来。因此，遍历查询列表并对每个查询执行一些操作不会那么昂贵，但如果在添加或删除大量实体时遇到问题，那确实是可以解决的。

首先，你用于表示组件类型子集的字符串确实相当低效。有很多替代方法。也许可以尝试类似这样的方式:

  1. 首先，为每种组件类型分配一个整数（你已经做过了）
  2. 按整数对子集中的组件类型进行排序
  3. 使用每个整数作为字符来构建字符串

这种表示方式不算太花哨，但它允许你使用 charCodeAt() 快速获取子集中的组件类型，并且你可以通过同时遍历两个字符串来测试子集，或者在遍历一个字符串的同时在另一个字符串中进行二分查找。

然而，真正的改进将来自于按照实体所呈现的组件类型子集对其进行分组。有很多方法。我认为像这样的方式对你会有效：

  • 对于每个实体，预先计算其组件类型子集字符串
  • 对于正在使用的每个子集，维护与该子集匹配的缓存查询列表。只有在引入新查询或新子集时，才需要修改此列表。
  • 当添加或移除一个实体时，获取其子集的查询，并将其直接添加到结果中或从结果中移除。
  • 当你得到一个新查询时，为它匹配的子集创建一个集合，将其添加到这些子集的查询列表中，并检查每个实体以查看它的子集是否包含在匹配集合中。

答案＃2

好的，我认为我对这个有一个初步的答案，因为它似乎在工作，但代码对我来说非常复杂，因此我不确定这是否真的在工作，还是仅仅看起来在工作而实际上是坏的。

所以，对于这个解决方案，我想保持查询性能，因为每个系统在每次帧更新时都会调用查询，所以它的执行频率比实体的创建/删除高 1000 倍。目前，查询通过首先检查缓存是否包含此组件映射，作为一种摊销的 O(1) 算法来工作。如果缓存中没有，它会创建与该组件分组（原型）关联的实体列表，然后以后该列表会从缓存中获取。缓存总是保持最新状态。

我问题中的关键是，虽然拥有 O(1) 查询操作很好，但更希望添加和移除操作更高效，因为它们是 O(n*k) 的，其中 n 是不同查询操作的数量（缓存的成员数），k 是实体中组件的数量。也就是说，每当一个实体被创建或销毁时，程序都必须遍历缓存中的每一项，并检查该实体是否应该属于该查询操作。如果是，就将其添加到该集合中；如果不是，则将其移除。

我今天早上想到的主意是实现另一个缓存/映射。也就是说，原始缓存是从查询组件列表（原型）映射到持有这些组件的实体集合。例如：

{ "6,1,20" => Set(1) }
{ "2,3,1,6" => Set(1) }
{ "2,3" => Set(31) }

假设 2 指的是 PositionComponent，而 3 指的是 SpriteComponent。这意味着所有包含这两个组件的实体都可以在那 31 个实体的集合中找到。

所以，我对最初问题的暂定解决方案是也建立一个映射，其中组件列表对应它们所属于的所有缓存条目。也就是说，假设我们有一个实体，其组件如下：1, 2, 3, 6, 25。那么它在这个缓存中的对应条目将如下所示：

1,2,3,6,25 => [ "2,3,1,6", "2,3" ]

第一次构建该原型（组件列表）的实体时，该列表是手动创建的。然而，之后它只是被维护。然后，每当有请求创建该原型的实体时，我们可以简单地查询这个缓存，以确定需要修改哪些缓存条目。

这样，与其必须遍历整个缓存，然后再遍历每个缓存项以确定它是否应该成为成员，不如我们简单地查询我们的二级缓存以确定它是哪些缓存条目的成员。所以，我认为摊销复杂度从 O(n*k) 缩小到了 O(c)，其中 c 是它所属的缓存条目数量。