我在业余时间做一个“游戏”，几乎纯粹是作为一种学习体验，并且在玩家实体和敌人实体之间需要发生碰撞检测的时候。
玩家和所有敌人共享一个基类 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/