面向数据访问多个索引数据阵列

Question

我正在为游戏引擎开发实体组件系统.我的目标之一是使用面向数据的方法来实现最佳数据处理.换句话说,我想遵循指导而不是希望结构的结构而不是结构数组.但是,我的问题是我还没有想出一个巧妙的方法来解决这个问题.

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

到目前为止,我想我可以拥有一个数据管理器,每个属性保存一个数组.因此,假设实体可能具有权重,位置,速度等中的一个或多个,并且它们将具有唯一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将对处理具有位置和速度的实体感兴趣.如何提取可迭代的数组指针以使该组件进行计算？我想给它一个数组,其中元素彼此相邻,但这似乎是不可能的.

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

我在这里问,因为我希望你们中的某个人可能有类似的经历,或者可能有想法或想法有助于解决这个问题.:)此外,如果这整个想法是垃圾,不可能正确,你有一个更好的想法,请告诉我.希望这个问题不会太长或太杂乱.

谢谢.

Answer 1

好问题.但是,据我所知,这个问题没有直接解决方案.有多种解决方案(其中一些你提到过),但我没有看到一个直接的银弹解决方案.

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

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

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

所以你的答案是简短的:这完全取决于你的数据使用情况.这就是我无法直接回答你问题的原因.我可以给你一些关于如何处理你的数据的想法,你可以自己决定在你的情况下哪些是最有用的(如果有的话),或者你可以调整/混合它们.

您可以将大多数访问的数据保存在连续数组中.例如,位置经常被许多不同的组件使用,因此它是连续数组的主要候选者.另一方面,重量仅由重力部件使用,因此这里可能存在间隙.您已针对最常用的情况进行了优化,并且对于使用频率较低的数据的性能会降低.不过,出于多种原因,我不是这个解决方案的忠实粉丝:它仍然效率低下,你将加载过多的空数据,#specific components/#total entities的比例越低它就越糟糕.如果8个实体中只有一个具有重力组件,并且这些实体在整个阵列中均匀分布,则每次更新仍会丢失一个缓存.它还假设所有实体都有一个位置(或者是公共变量的任何东西),很难添加和删除实体,它是不灵活的和简单的丑陋(imho无论如何).这可能是最简单的解决方案.

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

第三种选择是数据复制.现在,我很确定在你的Gravity组件的情况下这不值得付出努力,我认为它在计算量很大的情况下更有趣,但我们还是以它为例.在这种情况下,重力组件有3个压缩阵列,用于重量,速度和位置.它也有一个类似于你在第二个选项中看到的索引表.当您开始重力组件更新时,首先使用索引表从位置组件中的原始位置数组更新位置数组,如示例2所示.现在您有3个打包数组,您可以使用线性最大高速缓存进行计算利用.完成后,使用索引表将位置复制回原始位置组件.现在,如果您将它用于像Gravity这样的东西,这将不会比第二个选项更快(实际上可能更慢),因为您只读取和写入一次位置.但是,假设您有一个组件,其中实体彼此交互,每个更新传递需要多次读写,这可能会更快.但仍然取决于访问模式.

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

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

希望这可以帮助!

Answer 2

该解决方案实际上接受了对优化程度的限制.

解决差距问题只会导致以下问题:

• if语句(分支)处理数据异常(缺少组件的实体).
• 引入孔意味着你也可以随机迭代列表.DoD的强大之处在于所有数据都以其处理方式紧密打包和排序.

你可能想做什么:

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

拥有以下简化列表及其属性:

• 刚体(力,速度,变换)
• 碰撞(boundingbox,transform)
• drawable(texture_id,shader_id,transform)
• rigidbody_to_collision(rigidbody_index,collision_index)
• collision_to_rigidbody(collision_index,rigidbody_index)
• rigidbody_to_drawable(rigidbody_index,drawable_index)

等等...

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

• RigidbodyApplyForces(...),将力(例如重力)施加到速度上
• RigidbodyIntegrate(...),将速度应用于变换.
• RigidbodyToCollision(...),copy rigidbody仅转换为具有碰撞组件的实体的碰撞变换."rigidbody_to_collision"列表包含应将刚体ID复制到哪个碰撞ID的索引.这使碰撞列表紧密包装.
• RigidbodyToDrawable(...),copy rigidbody转换为具有绘图组件的实体的可绘制变换."rigidbody_to_drawable"列表包含应将刚体ID复制到哪个可绘制ID的索引.这使得drawabkl列表紧密包装.
• CollisionUpdateBoundingBoxes(...),使用新的变换更新边界框.
• CollisionRecalculateHashgrid(...),使用边界框更新hashgrid.您可能希望执行此划分多个帧以分配负载.
• CollisionBroadphaseResolve(...),使用hashgrid等计算可能的冲突....
• CollisionMidphaseResolve(...),使用边界框为广角等计算碰撞....
• CollisionNarrowphaseResolve(...),使用中期等多边形计算碰撞....
• CollisionToRigidbody(...),将碰撞对象的反作用力添加到刚体力."collision_to_rigidbody"列表包含索引,从该索引中应将力添加到哪个刚体ID.您还可以创建另一个名为"reactive_forces_to_be_added"的列表.您可以使用它来延迟添加力.
• RenderDrawable(...),将drawable渲染到屏幕(渲染器只是简化).

当然,你需要更多的流程/工作.您可能希望对drawable进行遮挡和排序,在物理和drawable之间添加变换图系统(请参阅Sony演示文稿,了解如何执行此操作)等.可以在多个核心上分布执行作业.当一切只是一个列表时,这很容易,因为它们可以分成多个列表.

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

在"复制对象到对象"进程的情况下.如果孔的跳跃确实是成为一个问题,你总是可以创建一个"重新排序对象"的过程,这将在每一帧的末尾,分布在多个帧,重新排序的对象到最优化的顺序.需要最少跳过孔的顺序.跳过孔是为了使所有列表尽可能紧密包装而付出的代价,并且允许按照处理方式对其进行排序.

Answer 3

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

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

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

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

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

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

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

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

Answer 4

我不想解决数据的结构问题，而是想提供一些关于我过去如何完成此类工作的观点。

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

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

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

物理管理器了解任何物理组件加载的每个物理网格，这使得该管理器能够处理所有与物理相关的任务，例如碰撞检测、调度碰撞消息、进行物理射线投射。

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

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

我在这里详细讨论对象/组件引擎结构的主题：https://gamedev.stackexchange.com/a/23578/12611