避免O（n ^ 2）复杂性进行碰撞检测 [英] Avoid O(n^2) complexity for collision detection

问题描述

我正在开发一个简单的基于图块的2D游戏。我有一个关卡，其中填充了可以与图块以及彼此交互的对象。检查与tilemap的碰撞非常容易，并且可以对具有线性复杂度的所有对象执行此操作。但是现在我必须检测对象之间的碰撞，现在我必须将每个对象与其他每个对象进行检查，这将导致正方形的复杂性。

I am developing a simple tile-based 2D game. I have a level, populated with objects that can interact with the tiles and with each other. Checking collision with the tilemap is rather easy and it can be done for all objects with a linear complexity. But now I have to detect collision between the objects and now I have to check every object against every other object, which results in square complexity.

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

I would like to avoid square complexity. Is there any well-known methods to reduce collision detection calls between objects. Are there any data-structures (like BSP tree maybe), which are easily maintained and allow to reject many collisions at a time.

例如，对象的总数级别约为500，一次可以在屏幕上看到其中的50个...

For example, the total number of objects in the level is around 500, about 50 of them are seen on screen at a time...

谢谢！

推荐答案

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

Why don't you let the tiles store information about what objects occupy them. Then collisions can be detected whenever an object is moved to a new tile, by seeing if that tile already contains another object.

这几乎不会花费任何费用。

This would cost virtually nothing.

这篇关于避免O（n ^ 2）复杂性进行碰撞检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！