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

我正在开发一个简单的基于图块的 2D 游戏。我有一个关卡，其中填充了可以与图块以及彼此交互的对象。检查与图块地图的碰撞相当容易，并且可以对具有线性复杂度的所有对象完成。但现在我必须检测对象之间的碰撞，现在我必须对照每个其他对象检查每个对象，这会导致平方复杂性。

我想避免平方复杂性。是否有任何众所周知的方法可以减少对象之间的碰撞检测调用。是否有任何易于维护并允许一次拒绝许多冲突的数据结构（可能像 BSP 树）。

例如，关卡中的对象总数约为 500 个，屏幕上一次会看到大约 50 个......

Thanks!

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

这几乎不需要任何成本。