我正在编写一个游戏，其中大量对象将在平铺 2D 地图的区域上产生“区域效果”。
所需功能：
- 其中一些区域效果可能会重叠并影响同一个图块
- 必须可以非常有效地访问任何给定图块的效果列表
- 区域效果可以具有任意形状，但通常采用“距导致效果的对象最多 X 瓦片距离”的形式，其中 X 是一个小整数，通常为 1-10
- 区域效果会经常变化，例如当对象移动到地图上的不同位置时
- 地图可能很大（例如 1000*1000 瓦片）
什么数据结构最适合这个？
问问题
519 次
5 回答
2
通常这取决于地图的密度。
如果您知道每个图块（或图块的主要部分）至少包含一种效果，您应该使用常规网格——简单的二维图块数组。
如果您的地图填充得很少并且有很多空图块，那么使用一些空间索引（如四叉树或 R-tree 或 BSP-trees）是有意义的。
于 2010-06-28T20:25:30.640 回答
2
如果您确实确实同时发生了很多区域效果，并且它们将具有任意形状，我会这样做：
- 创建新效果时，它会存储在全局效果列表中（不一定是全局变量，只是适用于整个游戏或当前游戏地图的东西）
- 它计算它影响的图块，并根据效果存储这些图块的列表
- 每个图块都会收到新效果的通知，并将对它的引用存储在每个图块列表中（在 C++ 中，我会为此使用 std::vector，具有连续存储的东西，而不是链表）
- 结束效果是通过遍历感兴趣的图块并删除对它的引用来处理的，然后再销毁它
- 移动它或改变它的形状，是通过删除上面的引用来处理的，执行更改计算，然后在现在受影响的图块中重新附加引用
- 您还应该有一个仅用于调试的不变量检查，它会遍历整个地图并验证效果中的瓦片列表是否与地图中引用它的瓦片完全匹配。
于 2010-06-29T10:18:24.940 回答
1
一些不依赖花哨的计算机科学的蛮力解决方案：
1000 x 1000 不是太大 - 只是一个兆。电脑有演出。你可以有一个二维数组。字节中的每一位都可以是一种“区域类型”。更大的“受影响区域”可能是另一个。如果您有合理数量的不同类型的区域，您仍然可以使用多字节位掩码。如果这变得荒谬，您可以使数组元素指针指向重叠区域类型对象的列表。但是你会失去效率。
您还可以实现一个稀疏数组 - 使用一个哈希表键（例如，键 = 1000*x+y） - 但这要慢很多倍。
当然，如果您不介意编写花哨的计算机科学方法，它们通常会更好地工作！
于 2010-06-28T20:08:41.660 回答
1
如果您知道每个区域效果的最大范围，则可以使用您选择的数据结构并仅存储实际源，该源已针对正常的 2D 碰撞测试进行了优化。
然后，在检查图块上的效果时，只需检查最大范围内的所有效果源（碰撞检测样式，针对您的数据结构进行了优化），然后应用定义的测试函数（例如，如果区域是圆形，检查如果距离小于一个常数；如果它是一个正方形，检查 x 和 y 距离是否都在一个常数内）。
如果您有少量 (<10) 的效果“场”形状，您甚至可以在其预先计算的最大范围内对每种效果场类型进行独特的碰撞检测。
于 2010-06-29T07:29:31.087 回答