我有大量的物体（球，一开始）在空间中一步一步地移动，不能重叠。目前，我每移动一步都会检查是否与其他对象发生冲突不过，我想到了一个看似简单的解决方案，但在这种情况下似乎没有出现，我想知道为什么。
为什么不简单地保留所有对象的两个集合（二维的，或三维的3个），分别按x和y（和z）坐标排序，并且在每次移动时查找每个维度中给定距离（此处为球直径）内的所有其他对象，并仅对这两个（或全部3个）结果集中的对象执行实际碰撞检查？
我知道这只适用于大小相等的对象，但也可以使用两倍的集合，按每个对象在每个维度的（1）最高（2）最低坐标排序与从O（n）“成对检查”到“Several”或“四叉树/八叉树”相比，这不起作用，或改进明显较少的原因是什么我认为这些排序集合的更新是一个代价高昂的操作，但是使用TreeSet（我的实现将在Java中）时，它仍然应该明显小于O（n），对吧？
最佳答案
检查两个结果集中有哪些对象涉及查看平面上两个条带中的所有对象这是一个更大的区域，因此涉及更多的对象，而不是四叉树允许您立即缩小到的封闭正方形更多的对象意味着速度较慢。