我正在 Android 上编写这个游戏，我有一堆角色四处走动，相互碰撞。一切正常，但是当我同时在屏幕上传递一定数量的字符时，应用程序的性能会受到严重影响。我做了我的测试并且绘图并没有导致低帧率，它是碰撞检测的算法，因为每次他们移动时，他们都必须检查他们对所有其他角色的位置。所以目前我只是为每个角色循环遍历它们。有没有办法改善这一点？在我不知道的大量对象上进行碰撞检测是否有性能技巧？
问问题
1314 次
4 回答
3
是的，有一种基于第一个宽相和第二个窄相碰撞检测的技术。
我将引用Mario Zechner 的《Beginning Android Games 》中的一些段落。
宽相：在这个阶段，我们试图找出哪些物体可能发生碰撞。想象一下，有 100 个物体可以相互碰撞。如果我们选择天真地测试每个对象与其他对象，我们需要执行 100 * 100 / 2 重叠测试。这种朴素的重叠测试方法具有 O(n^2) 渐近复杂度，这意味着它需要 n^2 步才能完成（实际上它只完成了一半的步骤，但渐近复杂度忽略了任何常数）。在一个好的、非暴力的广泛阶段，我们试图找出哪些对象对实际上有碰撞的危险。不会检查其他对（例如，两个相距太远而不会发生碰撞的对象）。我们可以通过这种方式减少计算负载，因为窄相测试通常非常昂贵。
窄阶段：一旦我们知道哪些对象对可能发生碰撞，我们通过对其边界形状进行重叠测试来测试它们是否真的发生碰撞。
广义阶段包括将世界划分为大单元，形成某种网格。每个细胞都有完全相同的大小，整个世界都被细胞覆盖。如果两个对象不在同一个单元格中，则不需要这两个对象的窄阶段。
再次引用：
我们需要做的就是以下几点：
根据我们的物理和控制器步骤更新世界上的所有对象。
根据对象的位置更新每个对象的每个边界形状的位置。我们当然也可以在这里包括方向和比例。
根据其边界形状找出每个对象包含在哪个或哪些单元格中，并将其添加到这些单元格中包含的对象列表中。
检查碰撞，但仅限于可以碰撞的对象对之间（例如，Goombas 不会与其他 Goombas 碰撞）并且在同一个单元格中。
这被称为空间哈希网格广泛阶段，并且非常容易实现。我们必须定义的第一件事是每个单元格的大小。这在很大程度上取决于我们用于游戏世界的规模和单位。
它还取决于您使用的边界形状。字符周围的简单矩形或圆形及其欧几里得距离是一件容易计算的事情，但更精细的形状（包括“头部”、“腿部”等细节，几乎没有额外的边界形状）将在计算上花费更多计算。
于 2012-11-21T04:12:37.027 回答
0
如果所有对象都可以自由移动到屏幕的任何部分，那么您能做的最好的就是您的O(n^2)算法。您可以通过意识到当您检查对象 A 是否与对象 B 碰撞时，您可以通过一个常数因子来改进它，那么您不必稍后检查对象 B 是否与对象 A 碰撞。
于 2012-11-21T03:53:49.910 回答
0
将每个字符包围在一个固定大小的正方形内。在检查字符碰撞之前，请检查它们所在的方块是否发生碰撞。当且仅当方块发生碰撞时，角色才有可能发生碰撞。现在检查正方形碰撞很容易，因为您只需比较 x 和 y 坐标。
于 2012-11-21T05:58:20.307 回答
0
正如 Federico 所建议的那样，划分为宽阶段和窄阶段只有在您的碰撞检测算法很昂贵时才有帮助，即它不是一个简单的边界框。
幸运的是还有其他选择。
您可以尝试使用碰撞遮罩技术。由于您似乎不受渲染速度的限制，因此将每个对象的边界框渲染到隐藏位图中。在渲染下一个对象之前，检查其边界框四个角的像素，看看它们是否已经被写入。您甚至可以为每个对象使用不同的颜色，以便颜色告诉您与哪个对象发生碰撞。
另一个流行的技巧是不要在每一帧都进行所有碰撞检查。例如，像超级马里奥兄弟这样的游戏实际上每隔一帧检查玩家和敌人之间的碰撞。您可以做一个更高级的版本，以循环方式检查所有对象，每帧尽可能多地检查。当事情变得繁忙时，每个对象可能只会每隔一个甚至每三帧检查一次，但玩家不太可能注意到。如果您的对象没有移动得如此之快以至于它们可以通过彼此只有一帧的碰撞，则此方法效果最佳。
于 2019-06-06T08:42:29.643 回答