2d - 2D 遮挡剔除的最佳解决方案

Question

在我的 2D 游戏中，我有静态和动态对象。可以有多个摄像头。我的问题:确定与当前相机的 View 矩形相交的对象。

目前，我只是简单地遍历所有现有对象(不关心动态或静态)并使用相机 View 对它们进行 AABB 检查。这对于非常动态的对象来说似乎是可以接受的，但对于静态对象来说是可以接受的，因为静态对象可能有数以万计(静态关卡几何体散布在整个场景中)。

我研究了多种可以解决我的问题的数据结构:

四叉树

这是我考虑的第一件事，但问题是它会迫使我的场景具有固定大小。 (静态对象可接受，但动态对象 Not Acceptable )

动态AABB树

看起来不错，但是重新平衡它的开销对于许多动态对象来说似乎太大了。

空间散列

对我来说，这里的主要问题是，如果您用相机进行大量缩小，则必须查询大量几乎不存在的空间哈希桶，从而导致性能降低。

一般来说，我对这个问题的一个好的解决方案的标准是:

动态大小:解决方案不能导致场景大小受限，或者需要大量重新计算来调整大小

良好的查询性能(对于相机)

对非常动态的对象的良好支持:处理位置不断变化的对象所需的计算应该很好:

一次在我的游戏中动态对象的最大合理数量可能是 5000。考虑到它们每一帧都改变它们的位置。考虑到频繁的插入和删除，是否有比每帧将对象的 AABB 与相机进行比较更快的数据结构？

Answer 1

不要试图找到银弹。只需将您的场景分成动态和静态部分，并为它们使用不同的算法。

四叉树显然适用于固定的静态几何
界限。

空间散列非常适合具有相似大小的对象集
(例如粒子系统)。

AFAIK 动态 AABB 树很少用于遮挡剔除，它们的
主要目的是碰撞检测的广泛阶段。

正如你所注意到的，强力剔除对于动态对象来说是正常的
如果他们的数量不是很大。

static level geometry scattered over the whole scene

如果您的场景高度稀疏，您可以将其划分为岛屿，即创建一个具有“良好密度”的场景部分列表。