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

Question

我正在编写一个游戏,其中大量对象将在平铺2D地图的区域上具有"区域效果".

所需功能:

• 这些区域效果中的一些可能重叠并影响相同的区块
• 必须能够非常有效地访问任何给定图块的效果列表
• 区域效果可以具有任意形状,但通常具有"距离引起效果的物体最多X个瓦片"的形式,其中X是一个小整数,通常为1-10
• 区域效果将经常变化,例如,当对象移动到地图上的不同位置时
• 地图可能很大(例如1000*1000个瓷砖)

什么数据结构最适合这个？

Answer 1

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

• 当创建新效果时，它将存储在全局效果列表中（不一定是全局变量，只是适用于整个游戏或当前游戏地图的东西）
• 它计算它影响的图块，并根据效果存储这些图块的列表
• 每个图块都会收到新效果的通知，并将引用存储在每个图块列表中（在 C++ 中，我将使用 std::vector 来实现此目的，它具有连续存储，而不是链接列表）
• 结束效果是通过迭代感兴趣的图块并在销毁它之前删除对其的引用来处理的
• 移动它或更改其形状是通过如上所述删除引用、执行更改计算、然后在现在受影响的图块中重新附加引用来处理的
• 您还应该进行仅调试不变检查，该检查会迭代整个地图并验证效果中的图块列表是否与引用它的地图中的图块完全匹配。