避免碰撞检测O（n^2）的复杂性

Question

我正在开发一个简单的基于磁贴的2D游戏。我有一个关卡，里面填充了可以与对方互动的对象。检查与瓦片地图的冲突是相当容易的，并且可以对线性复杂度的所有对象进行。但是现在我必须检测物体之间的碰撞，现在我必须检查每个物体与其他物体，以确定方块的复杂性。

我想避免方块的复杂性。有没有什么众所周知的方法可以减少物体之间的碰撞检测呼叫。是否有任何数据结构（如BSP树可能），这些数据结构很容易维护，并允许一次拒绝许多冲突。

例如，在层次对象的总人数为500左右，其中约50屏幕上看到在同一时间...

谢谢！

Answer 1

为什么不让瓷砖存储有关物体占据的信息。然后，通过查看该图块是否已经包含另一个对象，只要将对象移动到新图块就可以检测到碰撞。

这几乎没有花费。

Answer 2

可以使用四叉树来划分空间并减少需要检查碰撞的对象数量。

See this article - Quadtree demonstration.

And perhaps this - Collision Detection in Two Dimensions.

Or this - Quadtree (source included)

这似乎是 - 乍看之下 - 这需要大量的CPU功率来维持的树，而且也减少检查次数显著（请参阅第一个链接中的演示）。

Answer 3

你的游戏已经有了游戏相关瓷砖地图的概念。你可以选择这个地图进行碰撞检测，也可以在专门用于精灵跟踪和碰撞检测的场地上叠加一个辅助网格。

在您的网格中，每个精灵都占用一个或多个图块。精灵知道它占据了哪些图块，并且图块知道哪些图块占据了它。当一个精灵移动时，你只需要检查精灵占据的贴图中的冲突。这意味着根本不需要碰撞检测，除非精灵足够靠近以占据相同的瓦片，并且即使这样，您也只需要检查彼此靠近的精灵之间的碰撞。

如果你的游戏是这样的，精灵会经常聚集在一起，你可能要实现你的网格，四叉树，以允许各细分瓷砖和防止过多的精灵占用相同的网格贴砖。

此外，根据您的实施情况，您可能需要使用稍大的边界框来确定瓷砖占用率，而不是用于确定冲突。这样你就可以保证精灵在碰撞边界接触之前会重叠并占据相同的瓦片。