14

我正在开发一款具有相当大的方形 2d 游戏区域的游戏。游戏区没有瓷砖，有边界（没有环绕）。我试图弄清楚如何最好地划分这个世界以提高碰撞检测的性能。我不想检查每个实体是否与所有其他实体发生碰撞，我只想检查附近的实体是否有碰撞和避障。

我对这个游戏世界有一些特别的担忧……

  • 我希望能够同时使用游戏世界中的大量实体。但是，有 % 的实体不会与相同类型的实体发生冲突。例如射弹不会与其他射弹发生碰撞。

  • 我希望能够使用大范围的实体大小。我希望最小的实体和最大的实体之间有很大的尺寸差异。

  • 游戏世界中很少有静态或不动的实体。

我有兴趣使用类似于此处答案中描述的内容：Quadtree vs Red-Black tree for a game in C++?

我担心的是世界的树细分能够如何处理实体中的大尺寸差异？要为较小的实体划分足够多的世界，较大的实体将需要占据大量区域，我担心这将如何影响系统的性能。

我的另一个主要问题是如何正确更新被占用区域的列表。由于有很多移动的实体，而且有一些非常大，似乎将世界划分为跟踪哪些实体占据哪些区域会产生大量开销。

我主要在寻找任何有助于减少碰撞检测和避障计算的好算法或想法。

4

5 回答 5

7

如果我是你，我会从实现一个简单的 BSP（二进制空间分区）树开始。由于您在 2D 中工作，因此绑定框检查非常快。你基本上需要三个类：CBspTree、CBspNode 和 CBspCut（不是真的需要）

  1. CBspTree 有一个 CBspNode 类的根节点实例
  2. CBspNode 有一个 CBspCut 实例
  3. CBspCut 象征你如何将一个集合切割成两个不相交的集合。这可以通过引入多态性（例如 CBspCutX 或 CBspCutY 或其他一些切割线）巧妙地解决。CBspCut 也有两个 CBspNode

与分裂世界的接口将通过树类，如果您想用四叉树替换 BSP 解决方案，在此之上再创建一层可能是一个非常好的主意。一旦你掌握了窍门。但根据我的经验，BSP 就可以了。

如何在树中存储项目有不同的策略。我的意思是，您可以选择在每个节点中拥有例如某种容器，其中包含对占据该区域的对象的引用。这意味着（正如您问自己的那样）大项目将占用许多叶子，即会有很多对大对象的引用，而非常小的项目将出现在单个叶子上。

根据我的经验，这并没有那么大的影响。当然这很重要，但你必须做一些测试来检查它是否真的是一个问题。您只需将这些项目留在树中的分支节点上即可解决此问题，即您不会将它们存储在“叶级”上。这意味着您将在遍历树时快速找到这些对象。

当涉及到你的第一个问题。如果您只打算将此细分用于碰撞测试而没有其他用途，我建议永远不会碰撞的东西永远不要插入到树中。例如，正如您所说的导弹，不能与另一枚导弹相撞。这意味着您甚至不必将导弹存储在树中。

但是，您可能还想将 bsp 用于其他事情，您没有指定但请记住这一点（例如使用鼠标选择对象）。否则，我建议您将所有内容存储在 bsp 中，然后再解决冲突。只需询问某个区域中对象列表的 bsp 以获取一组有限的可能碰撞候选对象并在此之后执行检查（假设对象知道它们可以与什么碰撞，或其他一些外部机制）。

如果要加快速度，还需要处理合并和拆分，即当从树中删除事物时，很多节点将变为空，或者某个节点级别以下的项目数将减少到某个合并阈值以下. 然后，您想将两个子树合并为一个包含所有项目的节点。将项目插入世界时会发生拆分。因此，当项目的数量超过某个分割阈值时，您会引入一个新的切割，它将世界一分为二。这些合并和拆分阈值应该是两个常量，您可以使用它们来调整树的效率。

合并和拆分主要用于保持树的平衡，并确保它根据其规范尽可能高效地工作。这确实是您需要担心的。将事物从一个位置移动并因此更新树的速度很快。但是在合并和拆分方面，如果您过于频繁地进行合并和拆分，可能会变得昂贵。

这可以通过引入某种惰性合并和拆分系统来避免，即您有某种脏标记或修改计数。批处理所有可以批处理的操作，即移动 10 个对象并插入 5 个可能是一个批处理。完成这批操作后，您检查树是否脏，然后执行所需的合并和/或拆分操作。

如果您希望我进一步解释，请发表一些评论。

干杯！

编辑

树中有很多东西可以优化。但如您所知，过早优化是万恶之源。所以从简单开始。例如，您可以创建一些通用的回调系统，以便在遍历树时使用。这样，您不必查询树以获取与绑定框“问题”匹配的对象列表，而是可以遍历树并在每次遇到某些东西时执行该回调。“如果我提供的这个绑定框与您相交，则使用这些参数执行此回调”

于 2009-05-22T22:11:18.547 回答
5

您绝对想从 gamedev.net 中查看此碰撞检测资源列表。它充满了游戏开发约定的资源。

除了碰撞检测之外，请检查他们的文章和资源的完整列表。

于 2009-05-22T20:27:17.053 回答
4

我担心的是世界的树细分能够如何处理实体中的大尺寸差异？要为较小的实体划分足够多的世界，较大的实体将需要占据大量区域，我担心这将如何影响系统的性能。

使用四叉树。对于存在于多个区域的对象，您有几个选项：

  • 将对象存储在两个分支中，一直向下。一切都以叶节点结束，但您最终可能会得到大量额外的指针。可能适用于静态事物。

  • 分割区域边界上的对象并将每个部分插入各自的位置。造成很多痛苦，并且对于很多对象都没有很好的定义。

  • 将对象存储在树中的最低点。一组对象现在存在于叶节点和非叶节点中，但每个对象在树中都有一个指向它的指针。可能最适合要移动的物体。

顺便说一句，您使用四叉树的原因是因为它真的很容易使用。您不会像使用某些 BSP 实现那样进行任何基于启发式的创建。这很简单，它可以完成工作。

我的另一个主要问题是如何正确更新被占用区域的列表。由于有很多移动的实体，而且有一些非常大，似乎将世界划分为跟踪哪些实体占据哪些区域会产生大量开销。

每次移动时，将实体保持在树中的正确位置都会产生开销，是的，这可能很重要。但重点是您在碰撞代码中所做的工作要少得多。即使您通过树遍历和更新添加了一些开销，它也应该比您刚刚使用树删除的开销要小得多。

显然，取决于对象的数量、游戏世界的大小等，这种权衡可能不值得。通常结果会是一场胜利，但如果不这样做就很难知道。

于 2009-05-23T10:21:06.177 回答
2

有很多方法。我建议设置一些特定目标（例如，每秒 x 次碰撞测试，最小实体与最大实体之间的比率为 y），并进行一些原型设计以找到实现这些目标的最简单方法。您可能会惊讶于您只需做很少的工作即可获得所需的东西。（或者可能需要大量工作，具体取决于您的具体情况。）

许多加速结构（例如，一个好的 BSP）可能需要一段时间来建立，因此通常不适合快速动画。

有很多关于这个主题的文献，所以花一些时间搜索和研究以列出候选方法。模拟它们并配置文件。

于 2009-05-22T21:40:45.080 回答
1

我很想在游戏区域上覆盖一个粗网格以形成 2D 散列。如果网格至少是最大实体的大小，那么您只有 9 个网格方格来检查冲突，这比管理四叉树或任意 BSP 树要简单得多。确定您所在的粗网格正方形的开销通常只是 2 次算术运算，当检测到更改时，网格只需从一个正方形的列表中删除一个引用/ID/指针并将其添加到另一个正方形。

将弹丸排除在网格/树/等查找系统之外可以获得进一步的收益 - 因为您可以快速确定弹丸在网格中的位置，您知道要查询哪些网格方块以查找潜在的碰撞对象。如果您依次检查每个射弹与环境的碰撞，则其他实体无需反过来检查与射弹的碰撞。

于 2009-05-26T10:15:05.317 回答