在我的 2D 游戏中,我有静态和动态对象。可以有多个摄像头。我的问题:确定与当前相机的视图矩形相交的对象。
目前,我只是遍历所有现有对象(不关心动态或静态)并使用相机视图对它们进行 AABB 检查。这对于非常动态的对象似乎是可以接受的,但对于静态对象则不然,因为静态对象可能有成千上万个(静态关卡几何体散布在整个场景中)。
我研究了多种可以解决我的问题的数据结构:
- 四叉树
这是我考虑的第一件事,但问题是它会迫使我的场景具有固定大小。(静态对象可以接受,动态对象不行)
- 动态 AABB 树
看起来不错,但是对于许多动态对象来说,重新平衡它的开销似乎太大了。
- 空间哈希
对我来说,这里的主要问题是,如果你用相机缩小很多,必须查询大量几乎不存在的空间哈希桶,导致性能低下。
一般来说,我对这个问题的良好解决方案的标准是:
动态大小:该解决方案不得导致场景大小受到限制,或需要大量重新计算以调整大小
良好的查询性能(针对相机)
对动态对象的良好支持:处理位置不断变化的对象所需的计算应该很好:
在我的游戏中,动态对象的最大合理数量可能是 5000。考虑到它们每帧都会改变它们的位置。考虑到频繁的插入和删除,是否有比每帧将对象的 AABB 与相机进行比较更快的数据结构?