重叠空间区域的有效数据结构

Question

我正在编写一个游戏，其中大量的对象会在平铺的2D地图区域内具有"区域效果"。

所需功能:

• 一些区域效果可能会重叠并影响同一块平铺
• 必须能够非常高效地访问给定平铺的效果列表
• 区域效果可以具有任意形状，但通常是“距离引起效果的对象X个平铺以内”，其中X是一个小整数，通常为1-10
• 区域效果将经常更改，例如当对象移动到地图上不同位置时
• 地图可能很大（例如1000x1000平铺）

什么数据结构最适合这种情况？

- mikera

Answer 1

如果您的确有很多同时发生的区域效果，并且它们具有任意形状，我会这样做：

• 创建新效果时，将其存储在全局效果列表中（可以不是全局变量，而是适用于整个游戏或当前游戏地图的任何东西）
• 计算受影响的图块并将其存储在效果的图块列表中
• 通知每个受影响的图块，将其引用存储在每个图块的列表中（在C ++中，我会使用std :: vector来进行存储，这是一些连续存储的内容，而不是链表）
• 结束效果时，通过迭代遍历感兴趣的图块并删除对其的引用来处理它，然后销毁它
• 移动或更改其形状，通过按上述方式删除引用，执行更改计算，然后重新附加到现在受影响的图块中
• 您还应该拥有一个仅限于调试的不变量检查，以遍历整个地图并验证效果中图块的列表完全匹配引用它的地图中图块的列表。

- Kylotan

---

谢谢Kylotan - 这似乎是保证快速访问的最“全面”的方法。我认为我可能会采用类似于四叉树的方法来进行每个瓦片的存储，并且可能会使用某种聪明的缓存来避免大量的列表复制。 - mikera

我不理解你从四叉树中获得了什么好处：瓦片地图通常（按定义）是从位置到瓦片的二维哈希表。只有在没有这样快速查找系统时（例如连续的世界，而不是平铺的世界），您通常才需要四叉树。 - Kylotan

Answer 2

通常这取决于您地图的密度。

如果您知道每个瓷砖（或大部分瓷砖）至少包含一个效果，则应使用常规网格-简单的2D瓷砖数组。

如果您的地图填充不足，有很多空瓷砖，则使用一些空间索引，如四叉树、R树或BSP树是有意义的。

- Peter Popov

---

好的想法 - 我猜地图大概有10-20%被区域效应覆盖，因此采用空间索引类型的方法可能更好。 - mikera

一个空间索引允许你不浪费内存来存储未使用的瓦片。但请注意，大多数这样的索引都是设计用于存储静态数据的。根据我理解，在你的情况下，所有“影响区域”都可以沿着地图移动，所以你需要一直重建/更新空间索引。这可能会导致显著的开销。 - Peter Popov

Answer 3

通常使用BSP树（或四叉树或八叉树）。

- msw

---

那么，您会在节点中放置什么来表示区域效果，以支持高效的查询和更新呢？ - mikera

Answer 4

一些不依赖于高级计算机科学的暴力解决方案：

1000 x 1000 不太大，只有一个兆。计算机有吉字节。您可以拥有一个二维数组。每个字节中的每个位都可以是“区域类型”。更大的“受影响区域”可以是另一个位。如果您有合理数量的不同区域类型，则仍然可以使用多字节位掩码。如果这变得荒谬，您可以使数组元素成为重叠区域类型对象列表的指针。但是，这样会失去效率。

您还可以实现稀疏数组-使用哈希表键入坐标（例如，键= 1000 * x + y）-但这会慢很多倍。

当然，如果您不介意编写高级计算机科学方式，它们通常会更好地工作！

- FastAl

---

将会有大量的效果类型，所以它可能需要一些列表。但是，存在一个潜在问题，即单个“最多10个方块之外”的效果可能需要生成或更新441个不同的列表……？ - mikera

Answer 5

如果你已知每个区域效果的最大范围，你可以使用一个数据结构来存储实际源，只有优化了普通2D碰撞测试。

然后，在检查瓷砖上的效果时，只需检查（碰撞检测样式，针对您的数据结构进行优化）所有最大范围内的效果源，然后应用定义的测试函数（例如，如果区域是圆形，则检查距离是否小于常数；如果是正方形，则检查x和y距离是否各自在常数范围内）。

如果你有少量（<10）的效果“场”形状，甚至可以为每种效果场类型进行唯一的碰撞检测，在它们预先计算的最大范围内。

- Justin L.