在矩形数组中找到重叠的最快方法是什么？

Question

我在业余时间研究“游戏”，几乎纯粹是作为一种学习经验，并且正处于玩家实体与敌方实体之间需要发生碰撞检测的地步。

玩家和所有敌人共享一个基类，Entity，这使他们能够访问x，y，高度和宽度属性。使用这些，我可以为每个实体构建一个矩形，并尝试查找重叠。如果有重叠，则发生碰撞。

所以，与上述逻辑，我们可以假装下列数据是在矩形数组：

X Y HEIGHT WIDTH 
------------------------ 
0 0 25  50 
0 50 25  25 
0 100 25  30 
50 200 25  50 
150 250 25  25 
150 50 25  30 

是什么，以确定是否任何这些实体（矩形）的与相交的最快方式任何其他？简单地遍历数组并将每个元素与其他元素进行比较的性能不够好（O（n^2））。有没有更好的办法？

Answer 1

您想要使用某种空间索引或结构，以便您快速找到彼此靠近的元素。

一个常用的数据结构是quadtree。