performance - 在 2D 游戏的视口(viewport)中有效地检索 Z 排序对象

Question

想象一个具有较大游戏区域的 2D 游戏，比如 10000x10000 像素。现在想象有成千上万的物体散布在这个区域。所有对象都在 Z 顺序列表中，因此每个对象相对于其他每个对象都有明确定义的位置，即使它们相距很远。

假设这个游戏区域有一个视口(viewport)，显示这个游戏区域的 500x500 区域。显然，如果算法是“对于 Z 顺序列表中的每个对象，如果在视口(viewport)内，则渲染它”，那么您将浪费大量时间迭代远在视口(viewport)之外的所有数千个对象。更好的方法是在视口(viewport)附近或内部维护一个按 Z 顺序排列的对象列表。

如果对象和视口(viewport)都在移动，那么维护候选绘制对象的 Z 顺序列表的有效方法是什么？这是针对通用游戏引擎的，因此没有太多其他假设或细节可以添加以利用:问题几乎就是这样。

Answer 1

你不需要保持你的内存布局按 Z 强烈排序。相反，你需要将你的对象存储在一个沿着观察表面定向的空间分区结构中。
一个典型的分区结构，是二维的四叉树。您可以使用二叉树，可以使用网格，也可以使用空间散列方案。您甚至可以混合使用这些技术并将它们相互结合。
没有“最好”之分，但您可以权衡编写代码和维护代码的难易程度。还有你可用的内存。
让我们考虑一下网格，它实现起来最简单，访问速度最快，也最容易遍历。 (遍历就是去邻域单元格的事实)

想象一下，考虑到单元格内容只是一个小对象(如 std::vector 或 c# 列表)，比如 50 字节，您允许自己为网格骨架使用 20MB 的 RAM。对于 10k 像素的正方形表面，您将拥有:

sqrt(20*1024*1024 / 50) = 647

一维有 647 个单元格，因此 10k/647 = 15 像素宽的单元格。
仍然很小，所以我想完全可以接受。例如，您可以调整数字以获得 512 像素的单元格。当几个单元格适合视口(viewport)时，它应该是一个很好的适合。

然后，通过将左上角除以单元格的大小和结果的底板，可以很容易地确定视口(viewport)激活了哪些单元格，这会直接在单元格中为您提供索引。 (前提是您的视口(viewport)空间和网格空间都从 0,0 开始。否则您需要偏移)
最后取右下角，确定单元格的网格坐标；您可以在最小值和最大值之间执行双循环(x 和 y)以迭代激活的单元格。
在处理一个单元格时，您可以通过遍历您之前存放的对象列表来绘制它包含的对象。

当心跨越 2 个或更多单元格的对象。您需要做出选择，或者只存储一次，但随后您的搜索算法将始终需要知道该区域中最大元素的大小，并搜索相邻单元格的列表(通过尽可能远地搜索确保至少覆盖这个最大元素的大小)。
或者，您可以多次存储它(我喜欢的方式)，并且只需确保在迭代单元格时，每帧只处理一次对象。这可以通过在对象结构中(作为可变成员)使用帧 ID 轻松实现。

同样的逻辑适用于更灵活的分区，如二叉树。

我的引擎中都提供了实现，请查看代码，它可能会帮助您了解详细信息:http://sourceforge.net/projects/carnage-engine/

关于 Z 排序的最后的话，如果每个 Z 有多个内存存储，那么您已经进行了空间分区，只是没有沿着好的轴。
这可以称为分层。
作为优化，您可以做的不是在您的单元格中存储对象列表，您可以存储(有序的)对象的 maps 并且它们的键是它们的 Z，因此迭代将沿着Z.