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

Question

7

在我的2D游戏中，我有静态和动态的物体。可能会有多个相机。我的问题是：确定与当前相机视图矩形相交的对象。

目前，我只是迭代所有现有的对象（无论是动态还是静态），并在它们上执行与相机视图矩形的AABB检查。这对于非常动态的对象似乎是可接受的，但对于静态对象而言就不一样了，因为可能有成千上万个静态对象（静态级别几何图形分散在整个场景中）。

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

四叉树

这是我考虑的第一件事，但问题是它会强制我的场景具有固定的大小。（对于静态对象来说是可接受的，但对于动态对象则不行）

动态AABB树

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

空间哈希

对我来说主要问题是，如果你将相机缩小很多，就需要查询大量的大部分不存在的空间哈希桶，导致性能低下。

总的来说，我对解决这个问题的良好方案的标准如下：

- 动态大小：解决方案不能限制场景大小，或需要进行重复计算以调整大小 - 良好的查询性能（针对相机） - 对非常动态的对象有良好的支持：处理具有不断变化的位置的对象所需的计算应该很好：

在我的游戏中，每次最多可容纳的动态对象数量可能是5000。考虑到它们每一帧都会改变位置，是否存在一种数据结构比每一帧比较对象的AABB与相机更快，考虑到频繁的插入和删除操作？

- Hamilton

“Fixed size” 是什么意思？ - user703016

@Cicada：当你创建四叉树时，需要为根节点设置一个大小。更改根节点大小是昂贵的，因为它涉及到重建整个树，如果只是一些小对象离开了根节点区域，你可能不想这样做。我认为这就是他所说的“固定大小”。 - lamas

1

为什么空间哈希对你来说不够好？我知道至少有两种空间填充曲线及其6个变体可能会有用。我最喜欢的是希尔伯特曲线。你能解释一下你的问题吗？我已经更正了我的答案，因为我知道的1条曲线非常难制作（摩尔曲线）。 - Micromega

@Cicada：也许他指的是树的高度？但这并不是固定的。 - Micromega

Jitamaro：他的意思是根节点的大小，我确定。 - lamas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dmitry Sapelnikov · Accepted Answer

不要试图找到万能的解决方案。只需将场景分成动态和静态部分，并针对它们使用不同的算法。

遍布整个场景的静态地形

如果你的场景非常稀疏，你可以将其分成多个岛屿，即创建一个“密度良好”的场景部分列表。