15

我正在为游戏引擎开发实体组件系统。我的目标之一是使用面向数据的方法来优化数据处理。换句话说，我想遵循宁愿需要数组结构而不是结构数组的准则。但是，我的问题是我还没有找到一种巧妙的方法来为我解决这个问题。

到目前为止，我的想法是系统中的每个组件都负责游戏逻辑的特定部分，比如重力组件负责根据质量、速度等计算每一帧的力，而其他组件负责其他事情。因此，每个组件都对不同的数据集感兴趣。重力组件可能对质量和速度感兴趣，而碰撞组件可能对边界框和位置等感兴趣。

到目前为止，我认为我可以拥有一个数据管理器，它可以为每个属性保存一个数组。假设实体可能具有重量、位置、速度等中的一项或多项，并且它们将具有唯一的 ID。数据管理器中的数据将表示如下，其中每个数字代表一个实体 ID：

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,1,2,3]

如果所有实体都具有每个属性，则此方法效果很好。但是，如果只有实体 0 和 2 具有所有树属性，而其他实体是不移动类型的实体，它们将没有速度，数据将如下所示：

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,2]     //either squash it like this
velocityarray -> [0  ,2  ]     //or leave "empty gaps" to keep alignment

突然间，迭代它并不容易。如果我采用第二种方法，一个只对迭代和操纵速度感兴趣的组件将不得不以某种方式跳过空白间隙。保持数组短的第一种方法在更复杂的情况下也不能很好地工作。假设我有一个具有所有三个属性的实体 0，另一个只有重量和位置的实体 1，以及只有位置和速度的实体 2。最后，最后一个实体 3 只有权重。被压扁的数组看起来像：

weightarray ->   [0,1,3]
positionarray -> [0,1,2]
velocityarray -> [0,2]

另一种方法会留下如下空白：

weightarray ->   [0,1, ,3]
positionarray -> [0,1,2, ]
velocityarray -> [0, ,2, ]

如果您只对迭代只有少数属性的实体集感兴趣，那么这两种情况都不是简单的迭代。例如，给定的组件 X 会对处理具有位置和速度的实体感兴趣。如何提取可迭代数组指针以提供给该组件进行计算？我想给它一个数组，其中元素彼此相邻，但这似乎是不可能的。

我一直在考虑解决方案，例如为每个数组设置一个位字段，描述哪些点是有效的，哪些是间隙，或者一个系统将数据复制到没有孔的临时数组，然后将其提供给组件，以及其他想法，但我认为没有一个是优雅的，并且没有额外的处理开销（例如额外检查数据是否有效，或额外复制数据）。

我在这里问是因为我希望你们中的某些人可能有类似的经验，或者可能有有助于解决这个问题的想法或想法。:) 此外，如果这整个想法是废话并且不可能正确，而您有一个更好的想法，请告诉我。希望这个问题不会太长或太混乱。

谢谢。

4

4 回答 4

12

好问题。但是，据我所知，这个问题没有直接的解决方案。有多种解决方案（您已经提到了其中一些），但我没有看到直接的灵丹妙药解决方案。

我们先来看看目标。目标不是将所有数据放在线性数组中，这只是达到目标的手段。目标是通过最小化缓存未命中来优化性能。就这样。如果您使用 OOP-Objects，您的实体数据将被您不一定需要的数据包围。如果您的体系结构的缓存线大小为 64 字节，而您只需要权重 (float)、位置 (vec3) 和速度 (vec3)，则使用 28 字节，但无论如何都会加载剩余的 36 字节。更糟糕的是，当这 3 个值不在内存中并排或您的数据结构与缓存线边界重叠时，您将加载多个缓存线，仅 28 字节的实际使用数据。

现在，当你这样做几次时，这并不是那么糟糕。即使你这样做一百次，你也几乎不会注意到它。但是，如果您每秒执行数千次，则可能会成为问题。所以进入 DOD，您可以在其中优化缓存利用率，通常在存在线性访问模式的情况下为每个变量创建线性数组。在你的情况下，重量、位置、速度的数组。当您加载一个实体的位置时，您再次加载了 64 字节的数据。但是因为您的位置数据在一个数组中并排放置，所以您不会加载 1 个位置值，而是加载 5 个相邻实体的数据。更新循环的下一次迭代可能需要下一个位置值，该值已经加载到缓存中，依此类推，直到第 6 个实体才需要从主内存加载新数据。

因此，DOD 的目标不是使用线性数组，而是通过将在（大约）同时访问的数据相邻地放置在内存中来最大化缓存利用率。如果您几乎总是同时访问 3 个变量，则不需要为每个变量创建 3 个数组，您可以轻松地创建一个仅包含这 3 个值的结构并创建这些结构的数组。最佳解决方案始终取决于您使用数据的方式。如果您的访问模式是线性的，但您并不总是使用所有变量，请使用单独的线性数组。如果您的访问模式更不规则，但您总是同时使用所有变量，请将它们放在一个结构中并创建这些结构的数组。

因此，您的答案很简短：这完全取决于您的数据使用情况。这就是我不能直接回答你的问题的原因。我可以给你一些关于如何处理你的数据的想法，你可以自己决定哪个对你的情况最有用（如果有的话），或者你可以调整/混合它们。

您可以将访问最多的数据保存在一个连续的数组中。例如，位置经常被许多不同的组件使用，因此它是连续数组的主要候选者。另一方面，重量仅由重力组件使用，因此此处可能存在间隙。您已经针对最常用的情况进行了优化，并且对于不经常使用的数据将获得较低的性能。尽管如此，由于多种原因，我不是该解决方案的忠实拥护者：它仍然效率低下，您将加载太多空数据，#特定组件/#总实体的比率越低，它变得越糟糕。如果只有八分之一的实体具有重力分量，并且这些实体均匀分布在整个数组中，则每次更新仍然会出现一次缓存未命中。它还假设所有实体都有一个位置（或任何公共变量），它' 很难添加和删除实体，它既不灵活又丑陋（无论如何，恕我直言）。不过，这可能是最简单的解决方案。

解决这个问题的另一种方法是使用索引。组件的每个数组都将被打包，但是还有两个额外的数组，一个从组件数组索引中获取实体 id，第二个从实体 id 获取组件数组索引。假设位置由所有实体共享，而重量和速度仅由重力使用。您现在可以遍历打包的重量和速度数组，并获取/设置相应的位置，您可以获取 GravityIndex -> entityID 值，转到 Position 组件，使用它的 entityID -> positionIndex 来获取正确的索引位置数组。优点是您的重量和速度访问将不再给您缓存未命中，但如果 #gravity components / #position components 之间的比率较低，您仍然会获得位置的缓存未命中。您还可以获得额外的 2 个数组查找，但在大多数情况下，一个 16 位无符号整数索引应该足够了，因此这些数组将很好地适合缓存，这意味着在大多数情况下这可能不是一个非常昂贵的操作。不过，配置文件配置文件可以确保这一点！

第三种选择是数据复制。现在，我很确定在重力组件的情况下这不值得付出努力，我认为它在计算量大的情况下更有趣，但无论如何让我们以它为例。在这种情况下，重力组件有 3 个用于重量、速度和位置的打包数组。它还具有与您在第二个选项中看到的类似的索引表。当您开始 Gravity 组件更新时，您首先使用示例 2 中的索引表从 Position 组件中的原始位置数组更新位置数组。现在您有 3 个打包数组，您可以使用最大缓存进行线性计算利用率。完成后，使用索引表将位置复制回原始位置组件。现在，这不会 如果您将第二个选项用于 Gravity 之类的东西，它不会比第二个选项更快（实际上可能更慢），因为您只读取和写入一次位置。但是，假设您有一个组件，其中实体相互交互，每个更新传递都需要多次读取和写入，这可能会更快。尽管如此，一切都取决于访问模式。

我要提到的最后一个选项是基于变更的系统。您可以轻松地将其改编为消息传递系统之类的东西。在这种情况下，您只更新已更改的数据。在您的 Gravity 组件中，大多数物体将毫无变化地躺在地板上，但少数物体正在下落。Gravity 组件具有用于位置、速度、重量的打包数组。如果在更新循环期间更新了职位，则将实体 ID 和新职位添加到更改列表中。完成后，您将这些更改发送到任何其他保持位置值的组件。同样的原理，如果任何其他组件（例如，播放器控制组件）更改位置，它将发送更改实体的新位置，Gravity 组件可以侦听并仅更新其位置数组中的那些位置。你' 将像前面的示例一样复制大量数据，但不是在每个更新周期重新读取所有数据，而是仅在数据更改时更新数据。在少量数据实际更改每一帧的情况下非常有用，但如果大量数据更改可能会变得无效。

所以没有银弹。有很多选择。最佳解决方案完全取决于您的情况、您的数据以及您处理该数据的方式。也许我给出的例子都不适合你，也许所有的例子都适合你。并非每个组件都必须以相同的方式工作，有些可能使用更改/消息系统，而另一些则使用索引选项。请记住，尽管如果您需要性能，许多 DOD 性能指南都很棒，但它仅在某些情况下有用。DOD 不是总是使用数组，也不是总是最大化缓存利用率，你应该只在真正重要的地方这样做。配置文件配置文件。了解您的数据。了解您的数据访问模式。了解您的（缓存）架构。如果你做了所有这些，当你推理时，解决方案就会变得很明显:)

希望这可以帮助！

于 2013-03-14T18:07:05.960 回答
7

该解决方案实际上是接受您可以优化的程度存在限制。

解决gap问题只会引入以下内容：

  • If 语句（分支）处理数据异常（缺少组件的实体）。
  • 引入漏洞意味着您也可以随机迭代列表。国防部的强大之处在于，所有数据都按照处理方式紧密打包和排序。

你可能想做的事：

创建针对不同系统/案例优化的不同列表。每帧：仅将需要它的实体（具有该特定组件）的属性从一个系统复制到另一个系统。

具有以下简化列表及其属性：

  • 刚体（力、速度、变换）
  • 碰撞（边界框，变换）
  • 可绘制（texture_id，shader_id，变换）
  • 刚体到碰撞（刚体索引，碰撞索引）
  • 碰撞到刚体（碰撞索引，刚体索引）
  • 刚体到可绘制（刚体索引，可绘制索引）

ETC...

对于流程/作业，您可能需要以下内容：

  • RigidbodyApplyForces(...)，对速度施加力（例如重力）
  • RigidbodyIntegrate(...)，将速度应用于变换。
  • RigidbodyToCollision(...)，仅针对具有碰撞组件的实体将刚体变换复制到碰撞变换。“rigidbody_to_collision”列表包含应该将哪个刚体 ID 复制到哪个碰撞 ID 的索引。这使碰撞列表保持紧密。
  • RigidbodyToDrawable(...)，将刚体变换复制到具有绘制组件的实体的可绘制变换。“rigidbody_to_drawable”列表包含应该将哪个刚体 ID 复制到哪个可绘制 ID 的索引。这使 drawabkl 列表保持紧密。
  • CollisionUpdateBoundingBoxes(...)，使用新的变换更新边界框。
  • CollisionRecalculateHashgrid(...)，使用边界框更新 hashgrid。您可能希望在多个帧上执行此操作以分配负载。
  • CollisionBroadphaseResolve(...)，使用 hashgrid 等计算可能的碰撞......
  • CollisionMidphaseResolve(...)，使用broadphase等的边界框计算碰撞......
  • CollisionNarrowphaseResolve(...)，使用中相等的多边形计算碰撞......
  • CollisionToRigidbody(...)，将碰撞物体的反作用力添加到刚体力。“collision_to_rigidbody”列表包含从哪个碰撞 ID 将力添加到哪个刚体 ID 的索引。您还可以创建另一个名为“reactive_forces_to_be_added”的列表。您可以使用它来延迟添加力。
  • RenderDrawable(...)，将可绘制对象渲染到屏幕（渲染器只是简化了）。

当然，您将需要更多的流程/工作。您可能想要对可绘制对象进行遮挡和排序，在物理和可绘制对象之间添加一个变换图系统（请参阅 Sony 演示文稿，了解您如何执行此操作）等。作业的执行可以分布在多个内核上执行。当一切都只是一个列表时，这很容易，因为它们可以分为多个列表。

在创建实体时，组件数据也将一起创建并以相同的顺序存储。这意味着列表将大部分保持相同的顺序。

在“将对象复制到对象”过程中。如果跳过孔确实成为一个问题，您总是可以创建一个“重新排序对象”过程，该过程将在每一帧结束时分布在多个帧上，将对象重新排序为最佳顺序。需要最少跳过孔的顺序。跳过漏洞是为了让所有列表尽可能紧凑而付出的代价，并且还允许以将要处理的方式对其进行排序。

于 2013-03-14T16:12:48.150 回答
5

我依靠两个结构来解决这个问题。希望图表足够清晰（否则我可以添加进一步的解释）：

在此处输入图像描述

稀疏数组允许我们将数据并行关联到另一个数据，而不会从未使用的索引中占用太多内存，也不会降低空间局部性（因为每个块连续存储一堆元素）。

您可能会使用比 512 更小的块大小，因为对于特定的组件类型来说这可能非常大。32 之类的值可能是合理的，或者您可以根据sizeof(ComponentType). 有了这个，您可以将您的组件与您的实体并行关联，而不会从未占用的空间中过多地使用内存，尽管我不那样使用它（我使用垂直类型的表示，但我的系统有很多组件类型 - - 如果你只有几个，你可能只是并行存储所有东西）。

但是，我们在迭代时需要另一个结构来确定哪些索引被占用。在那里我使用了一个分层位集（我非常喜欢并使用这种数据结构，但我不知道它是否有正式名称，因为它只是我在不知道它叫什么的情况下制作的东西）：

在此处输入图像描述

这允许始终按顺序访问被占用的元素（类似于使用排序索引）。这种结构对于顺序迭代来说非常快，因为测试单个位可能表明可以处理一百万个连续元素，而无需检查一百万位或必须将一百万个索引存储和访问到容器中。

作为奖励，它还允许您在最佳情况下设置交集Log(N)/Log(64)（例如：能够在 3-4 次迭代中找到两个包含一百万个元素的密集索引集之间的集合交集）如果您需要快速设置对 ECS 来说通常非常方便的交叉点。

这两个结构是我的 ECS 引擎的支柱。它们非常快，因为我可以处理 200 万个粒子实体（访问两个不同的组件），而无需以略低于 30 FPS 的速度缓存具有两个组件的实体的查询。当然，对于仅 200 万个粒子来说，这只是一个糟糕的帧速率，但这是在将它们表示为具有两个组件（运动和精灵）的完整实体时，粒子系统每帧执行查询，未缓存 - 人们通常永远不会做（最好像一个ParticleEmitter代表给定实体的许多粒子的组件一样使用，而不是使粒子本身成为一个完整的独立实体）。

如果您有兴趣，希望图表足够清晰，可以实现您自己的版本。

于 2017-12-21T03:22:33.953 回答
3

与其解决数据的结构问题，我只想提供关于我过去如何完成此类工作的观点。

游戏引擎有一个负责游戏中各种系统的管理器列表（InputManager、PhysicsManager、RenderManager 等）。

3D 世界中的大多数事物都由一个 Object 类表示，并且每个 Object 可以有任意数量的组件。每个组件负责对象行为的不同方面（RenderComponent、PhysicsComponent 等）。

物理组件负责加载物理网格，并为其提供所有必要的属性，如质量、密度、质心、惯性响应数据等。该组件还存储有关物理模型曾经存在于世界中的信息，例如位置、旋转、线速度、角速度等。

PhysicsManager 了解由任何物理组件加载的每个物理网格，这允许该管理器处理所有与物理相关的任务，例如碰撞检测、发送碰撞消息、进行物理射线投射。

如果我们想要只有少数对象需要的特殊行为，我们将为它创建一个组件，并让该组件操纵速度或摩擦力等数据，这些变化将被 PhysicsManager 看到并在物理模拟中解释。

就数据结构而言，您可以拥有我上面提到的系统并以多种方式对其进行构建。通常，对象保存在 Vector 或 Map 中，组件保存在 Object 上的 Vector 或 List 中。就物理信息而言，PhysicsManager 有一个所有物理对象的列表，可以存储在 Array/Vector 中，PhysicsComponent 有它的位置、速度和其他数据的副本，以便它可以做任何事情需要由物理管理器处理该数据。例如，如果你想改变一个物体的速度，你只需告诉 PhysicsComponent，它会改变它的速度值，然后通知 PhysicsManager。

我在这里更多地谈论对象/组件引擎结构的主题：https ://gamedev.stackexchange.com/a/23578/12611

于 2013-03-13T16:46:16.227 回答