基于网格的粒子系统优化

Question

我在Java中实现了一个类似于这一个的游戏，目前我发现我碰到的粒子数量上限为80K。我的棋盘是一个二维数组的“粒子”对象的引用，每个对象必须更新每一个帧。不同类型的“粒子”有不同的行为，它们可能会随风或邻近粒子等环境条件的变化而移动或改变其状态。

一些可能生效的“规则”：

• 如果熔岩型粒子与水型粒子相邻，两者都会消失，熔岩将被黑云石所取代。
• 如果气体粒子与熔岩、火焰、琥珀等粒子相邻，它就会点燃，并产生火灾和烟雾。
• 如果有足够数量的尘埃颗粒堆积在一起，那么处于较低水平的尘埃粒子，就会像在压力下一样，变成沉积岩。

我到处搜索，没有找到任何算法或数据结构，似乎特别适合加速这项任务。似乎某种回忆录可能有用吗？四叉树在这里有用吗？我见过他们在康威的“生命游戏”中使用了哈希姆算法。或者，我不能做太多的事情来提高速度吗？

Answer 1

哈希生活原则上是可行的，但有两个原因可以解释为什么你不能像康威生活那样从它中得到更多的东西。

首先，它依赖于反复出现的模式。你拥有的细胞状态越多，飞机的结构也就越少，你就会遇到更少的缓存命中，你就会遇到更多的蛮力。

第二，正如另一张海报所指出的，涉及非局部效应的规则要么意味着原语(在Conway Life 4x4中)将需要更大一些，这样您就可以在8x8或16x16或任何大小保证在n/2时间内正确计算中间部分时放弃分而治之。由于国家的多样性，情况变得更加糟糕。在Conway Life中，通常会预先计算所有4x4网格，至少有几乎所有相关的网格都在缓存中。在两个州中，只有65536个4x4网格(现代平台上只有花生)，而只有3个网格只有43046721个。如果您必须拥有8x8原语，那么它很快就会变得非常大，并且超出了任何实际的存储。

因此，原始状态越大，你拥有的状态越多，这很快就变得不现实了。

解决原始尺寸的一种方法是让岩石规则传播压力。因此，Rock+n (n表示压力)在下一代成为Rock+(n+1)，如果它有Rock+m，而m>=n在它上面。在某个门槛处，它变成了沉积岩。

这意味着细胞仍然只依赖于它们的近邻，但也会使状态的数量增加。

如果给出的例子中有像“鸟”这样的单元格类型，而且速度不能保持在最小(例如-1，0-1，在任何方向)，那么你就完全崩溃了。即便如此，这些规则的混乱性质可能也会使这些领域的缓存命中小得离谱。

如果你的规则不能像康威生活那样导致稳定的状态(或重复的循环)，那么回忆录的回报将是有限的，除非你的飞机基本上是空的。

Answer 2

我不清楚您的问题，但我认为cuda或OpenGL (一般GPU编程)可以轻松处理ref链接：https://dan-ball.jp/en/javagame/dust/

Answer 3

为此，我使用固定的NxN网格，主要是因为每个帧周围移动的点太多，无法从四叉树的递归细分特性中获益。在这种情况下，具有适当调优数据表示和内存布局的简单的数据结构可以在世界上产生所有的不同。

我在这里要做的主要事情是避免将每个粒子建模为一个对象。它应该是原始数据，就像一些普通的旧数据，如floats或int。您希望能够使用连续的保证空间局部性的顺序处理，而不需要支付填充的成本和每个类实例的8字节开销。把冷场和热田分开。

例如，你不一定需要知道粒子的颜色来移动它并应用物理。因此，您不希望这里有一个AoS表示，在连续的物理传递过程中，它必须将粒子的颜色加载到缓存线中，而不是使用它。尽可能多地将与缓存一起使用的相关内存插入缓存行，方法是将其与特定传递的无关内存分离。

网格中的每个单元格应该只将一个索引存储到一个粒子中，每个粒子存储一个指向单元格中下一个粒子的索引(一个单链列表，但一个侵入式的索引，它不需要分配节点，只需要将索引用于数组)。-1可以用来表示列表的末尾和空单元格。

要查找感兴趣的粒子之间的碰撞，请查看与您正在测试的粒子相同的单元格，您可以并行地这样做，其中每个线程处理一个或多个粒子单元格。

NxN网格应该是非常精细的，因为每帧都有运动粒子的船载。使用您创建的单元格来找到最适合您输入大小的单元格。你甚至可能有多个网格。如果某些粒子不相互作用，就不要把它们放在同一个网格中。这里不要担心网格的内存使用情况。如果每个网格单元只是为单元格中的第一个粒子存储一个32位索引，那么200x200网格只需要160 32，每个粒子的32位next索引开销。

几年前，我在C中做了一些类似的事情，使用了上面的技术(但没有演示游戏那样有趣的粒子交互)，它可以处理大约10百万个粒子，直到它开始运行到30 FPS以下，在只有两个核心的旧硬件上。它确实使用了C以及SIMD和多线程，但是我认为如果您这样做的话，您可以在Java中得到一个非常快速的解决方案，同时处理大量的粒子。

数据结构：

​

当粒子从一个细胞移动到另一个细胞时，你所做的就是操纵几个整数将它们从一个细胞移动到另一个细胞。单元格不“拥有内存”，也不分配任何内存。它们只是32位的指数。

要弄清楚粒子所占据的细胞，只需：

cell_x = (int)(particle_x[particle_index] / cell_size)
cell_y = (int)(particle_y[particle_index] / cell_size)
cell_index = cell_y * num_cols + cell_x

..。相对于穿越树结构，当粒子在周围移动时，再平衡树结构要便宜得多。