logo标签列表

如何将2D游戏世界细分以实现更好的碰撞检测

data-structurescollision-detection
14

我正在开发一个游戏，它有一个较大的正方形2D游戏区域。游戏区域是没有瓦片的有界面（没有环绕）。我试图找出如何最好地将这个世界划分，以增加碰撞检测的性能。而不是对所有实体与所有其他实体进行碰撞检测，我只想检查附近的实体是否会碰撞和避让障碍。

我对这个游戏世界有一些特殊的考虑...

  • 我希望能够在游戏世界中同时使用大量实体。然而，一定比例的实体不会与相同类型的实体发生碰撞。例如，弹丸不会与其他弹丸发生碰撞。

  • 我希望能够使用各种尺寸的实体。我希望最小的实体和最大的实体之间有非常大的尺寸差异。

  • 游戏世界中几乎没有静态或不动的实体。

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

我的担忧是，在实体大小差异很大的情况下，树形划分世界能否处理得好？为了将世界划分足够小以适应较小的实体，更大的实体将需要占据大量区域，并且我担心这将如何影响系统的性能。

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

我主要是寻找任何可以帮助减少碰撞检测和避让障碍计算数量的好算法或想法。

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个对象可能是一个批次。完成该批操作后，检查树是否脏，并执行所需的合并和/或拆分操作。
如果您想让我进一步解释，请发布一些评论。
干杯！
5
4
我的担忧是，如果使用树型结构来划分世界地图，如何处理实体之间的规模差异？为了将世界地图细分到足够小的区域以容纳较小的实体，较大的实体将需要占据大量区域，这可能会影响系统的性能。
可以使用四叉树。对于存在于多个区域中的对象，有几种选择：
1. 在两个子节点中都存储该对象，直到最底层。所有内容最终都在叶节点中，但可能会产生大量额外的指针。适用于静态事物。 2. 在区域边界上分割对象，并将每个部分插入其各自的位置。会引起问题，对于许多对象而言定义不清晰。 3. 在树中的最低点存储对象。现在对象集存在于叶节点和非叶节点中，但每个对象在树中只有一个指针。这对于将要移动的对象可能是最好的选择。
顺便提一下，你使用四叉树的原因是因为它非常容易使用。相对于某些BSP实现，您不需要基于启发式创建。它简单而可行。
我的另一个主要关注点是如何正确地更新被占用的区域列表。由于有很多移动实体，其中一些非常大，似乎划分世界地图将会给跟踪哪些实体占用了哪些区域带来大量开销。
是的，每次实体移动时，将其放置在正确的位置上会有开销，并且可能会很大。但这样做的整个目的是，在碰撞代码中要做更少的工作。即使您添加了树遍历和更新的开销，它也应该比仅使用树所消除的开销小得多。
显然，取决于对象数量、游戏世界大小等等，权衡可能不值得。通常结果是成功的，但没有尝试过就难以知道。
2
有很多方法。我建议设定一些具体的目标（例如，每秒进行x次碰撞测试，最小实体与最大实体之间比率为y），并进行一些原型制作，找到实现这些目标的最简单方法。你可能会惊讶于获得所需的成果所需的工作量很少。（或者根据你的情况可能需要大量工作。）
许多加速结构（例如，一个好的BSP）需要花费一些时间来设置，因此通常不适用于快速动画。
关于这个主题有很多文献资料，因此花些时间搜索和研究以列出候选方法。模拟它们并进行性能分析。
1

我会考虑在游戏区域上覆盖一个粗略的网格来形成一个二维哈希。如果网格至少与最大实体的大小相同，那么您只需要检查9个网格方块以进行碰撞检测，这比管理四叉树或任意BSP树要简单得多。确定您所在的粗略网格方块的开销通常只需2个算术操作，当检测到更改时，网格只需从一个方块的列表中删除一个引用/ID/指针，并将其添加到另一个方块。

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接