避免O(n^2)复杂度的碰撞检测算法

Question

我正在开发一个简单的基于瓦片的2D游戏。我有一张地图，上面布满了可以与瓦片和其他物体进行交互的对象。检测物体与瓦片之间的碰撞非常容易，可以使用线性复杂度对所有物体进行检测。但现在我需要检测物体之间的碰撞，并且我必须检查每个物体与其他每个物体之间的碰撞，这会导致平方复杂度。

我想避免平方复杂度。是否有任何众所周知的方法来减少物体之间的碰撞检测调用？是否有任何数据结构（例如BSP树），易于维护并允许一次拒绝多个碰撞。

例如，关卡中的对象总数约为500，其中大约50个对象同时出现在屏幕上...

谢谢！

- SadSido

---

你想要所有物体的碰撞检测还是只针对可见物体？ - Nick Dandoulakis

嗯，还不确定。我认为我可以忽略屏幕外的物体之间的碰撞。 - SadSido

在这种情况下，您可以仅收集可见对象并对它们进行碰撞检测。仍然具有O(n^2)的时间复杂度。 - Nick Dandoulakis

Answer 1

为什么不让瓷砖存储有关占用它们的对象的信息？然后，每当将对象移动到新瓷砖时，可以通过查看该瓷砖是否已包含另一个对象来检测碰撞。这几乎没有成本。

- Peladao

---

这不错，你也可以在这样的地图上运行A*算法。但请注意，这可能会导致错误和其他限制，例如，如果您想在一个格子上放置多个对象或类似的事情。它还会导致所有对象都必须适合一个格子的限制，否则处理2x1格子对象等将变得复杂。 - InsertNickHere

听起来不错... 无论如何，对象可以同时占据多个瓷砖，也可以仅占据瓷砖的一部分（比瓷砖小的对象）。 - SadSido

顺便问一下，我应该遍历所有的瓷砖吗？看看它们是否共享某些对象？对象同时移动，因此一个对象正在进入瓷砖，另一个对象正在离开这个瓷砖，我该如何处理？ - SadSido

@SadSido 只需处理对象的移动。当一个对象想要占据一个新瓷砖时，它应该锁定瓷砖对象，然后查看它是否已被另一个对象占据。如果是，则碰撞，如果不是，则将其添加到瓷砖中并解锁瓷砖，以便其他对象可以尝试占据它。（当一个对象离开一个瓷砖时，它当然应该从瓷砖对象中删除自己） - Peladao

我正在考虑将我的游戏关卡分割成各自的区域（也称为“房间”），并仅在房间内检测物体之间的碰撞。这样做仍然需要n^2次碰撞检测，但是由于一个房间中只有较少的物体，所以n会减少。并且，只有玩家可以从一个房间移动到另一个房间，所有的NPC都将在一个房间内巡逻... - SadSido

Answer 2

你可以使用四叉树来划分空间，减少需要检查碰撞的物体数量。 查看这篇文章-四叉树演示。 或者这篇文章-二维碰撞检测。 还有这个-四叉树（含源码）。 乍一看，维护树可能需要大量的CPU计算能力，但它也显著地减少了检查次数（请参见第一个链接中的演示）。

- Matěj Zábský

---

还要注意的是，实际运行时的开销在处理许多对象之前是相当小的。真正的问题是它增加了很多代码复杂性。如果对象的大小与瓷砖的大小相近，则 Peladao 的解决方案可能更适合这种情况。 - Walter Mundt

Answer 3

你的游戏已经有了与游戏玩法相关的瓦片地图的概念。你可以将这个瓦片地图用于碰撞检测，或者在你的游戏场景上覆盖一个二级网格，专门用于精灵跟踪和碰撞检测。

在你的网格中，每个精灵占据一个或多个瓦片。精灵知道它占据的瓦片，而瓦片知道哪些精灵占据它。当一个精灵移动时，你只需要检查它所占据的瓦片内的碰撞。这意味着除非精灵靠得足够近以占据相同的瓦片，否则根本不需要进行任何碰撞检测，即使是这样，你也只需要检查彼此靠近的精灵之间的碰撞。

如果你的游戏玩法经常会让精灵聚集在一起，你可能需要将你的网格实现为四叉树，以允许每个瓦片被细分并防止太多的精灵占据同一个网格瓦片。

此外，根据你的实现方式，你可能需要使用稍大的边界框来确定瓦片占用情况，以便在精灵的碰撞边界接触之前，确保它们重叠并占据同一个瓦片。

- tylerl