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

Question

我正在写一个游戏，其中大量的对象将在平铺的2D地图的区域上产生“区域效果”。

所需的功能：

• 其中一些地区的影响可能会重叠，影响同瓦
• 它必须能够非常有效地访问效果列表对于任何给定瓦
• 该地区的影响可以具有任意形状，但通常形式为“达到X个瓷砖与造成该效果的物体的距离”，其中X是小整数，通常为1-10个面积效果将经常变化，例如，作为对象被移动到不同的位置在地图上
• 地图可能是潜在的巨大（例如，1000 * 1000瓦）

什么数据结构将最适合呢？

Answer 1

提供你真的有很多的区域效应同时发生，那他们将有任意的形状，我会做这种方式：创建一个新的效果时，

• ，它是 存储的在效果 全局列表（不一定是一个全局变量， 只是一些适用于 整个游戏或当前游戏地图）
• 它计算其平铺 它影响，并存储对这些瓷砖的列表效果
• 每个那些瓦片是 通知的新的效果，和 存储参考回到它在一个 每瓦片列表（在C++中我会使用一个 的std ::矢量这一点，一些与 相连存储，而不是一个连结 列表）
• 结束的效果是通过 迭代感兴趣的瓷砖并且将其除去的引用，破坏它
• 之前移动它，或改变其形状处理，通过去除 的参考文献为已处理上面，执行更改计算， 然后重新添加现在受影响的瓦片中的引用
• 您还应该有一个仅用于调试的不变检查，它会遍历整个地图的 ，并验证效果 中的切片列表是否与引用它的地图中的切片完全匹配。

Answer 2

通常BSP-Trees（或quadtrees或octrees）。

Answer 3

一些蛮力解决方案，不靠花哨的计算机科学：

1000×1000是不是太大 - 只是一个MEG。电脑有Gigs。你可以有一个2D数组。字节中的每一位都可以是'区域类型'。更大的'受影响的地区'可能是另一回事。如果您拥有合理数量的不同类型的区域，则仍然可以使用多字节位掩码。如果这变得荒谬可以使数组元素指向重叠区域类型对象列表。但那你就失去了效率。

你也可以实现一个稀疏数组 - 使用散列表中的键（例如，key = 1000 * x + y） - 但是这会慢很多倍。

如果当然如果你不介意编码花哨的计算机科学方式，他们通常会更好！

Answer 4

通常取决于地图的密度。

如果您知道每个瓷砖（或瓷砖的主要部分）至少包含一个效果，则应使用常规栅格 - 简单的二维瓷砖阵列。

如果您的地图无法填充且存在大量空白切片，则可以使用类似四叉树或R树或BSP树的spatial indexes。

Answer 5

如果您已知每个区域效果的最大范围，则可以使用您选择的数据结构并存储实际来源，这只针对正常2D碰撞测试进行了优化。

然后，当检查瓷砖上的效果时，只需在最大范围内检查所有效果源（碰撞检测样式，针对您的数据结构进行优化），然后应用定义的测试功能（例如，一个圆圈，检查距离是否小于一个常数;如果它是一个正方形，检查x和y距离是否都在一个常数内）。

如果你有一个很小的（< 10）大小的效果“场”形状，你甚至可以在其预先计算的最大范围内为每个效果场类型做一次独特的碰撞检测。