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

我在业余时间做一个“游戏”，几乎纯粹是作为一种学习体验，并且在玩家实体和敌人实体之间需要发生碰撞检测的时候。

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

因此，根据上面的逻辑，我们可以假设以下数据位于 Rectangles 数组中:

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))。有没有更好的办法？

最佳答案

您希望使用某种空间索引或结构来快速查找彼此靠近的元素。

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

关于java - 在矩形数组中查找重叠的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13423488/