题 如何细分2D游戏世界以获得更好的碰撞检测


我正在开发一款具有相当大的方形2d游戏区域的游戏。游戏区域是无框的,有边界(没有缠绕)。我试图找出如何最好地划分这个世界以提高碰撞检测的性能。我不想检查每个实体是否与所有其他实体发生碰撞,而只是检查附近的实体是否存在碰撞和避障。

我对这个游戏世界有一些特别关注......

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

  • 我希望能够使用大量的实体大小。我希望最小的实体和最大的实体之间存在非常大的差异。

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

我有兴趣使用类似于答案中描述的内容: 用C ++游戏的Quadtree vs Red-Black树?

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

我的另一个主要问题是如何正确地保持被占领区列表的最新状态。由于存在大量移动实体和一些非常大的移动实体,看起来分割世界将产生大量开销以跟踪哪些实体占据哪些区域。

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


14
2018-05-22 20:14


起源




答案:


如果我是你,我首先要实现一个简单的BSP(二进制空间分区)树。由于您在2D中工作,因此绑定框检查非常快。你基本上需要三个类:CBspTree,CBspNode和CBspCut(不是真的需要)

  1. CBspTree有一个CBspNode类的根节点实例
  2. CBspNode有一个CBspCut实例
  3. CBspCut象征着你如何在两个不相交的集合中剪切一组。这可以通过引入多态性(例如CBspCutX或CBspCutY或一些其他切割线)而巧妙地解决。 CBspCut还有两个CBspNode

面向分裂世界的界面将通过树类,如果您想用例如BSP解决方案替换BSP解决方案,那么在此基础上再创建一个层是一个非常好的主意。四叉树。一旦你掌握了它。但根据我的经验,BSP会做得很好。

有关如何在树中存储项目的不同策略。我的意思是你可以选择例如每个节点中的某种容器,包含对占用该区域的对象的引用。这意味着(正如你在问自己)大型物品将占据许多叶子,即将有许多对大型物体的引用,并且非常小的物品将出现在单个叶子上。

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

谈到你的第一个问题。如果你只是将这个细分用于碰撞测试而没有别的,我建议永远不会碰撞的东西永远不会插入到树中。例如,如你所说的导弹不能与另一枚导弹发生碰撞。这意味着你甚至不必将导弹存放在树上。

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

如果你想加快速度,你还需要照顾好 合并 和 分裂即,当从树中移除事物时,许多节点将变空或者某个节点级别之下的项目数量将减少到某个合并阈值以下。然后,您希望将两个子树合并为一个包含所有项目的节点。将项目插入世界时会发生拆分。因此,当项目数量超过某个分割阈值时,您会引入一个新的剪切,将世界分成两部分。这些合并和拆分阈值应该是两个常量,可用于调整树的效率。

合并和拆分主要用于保持树的平衡,并确保它根据其规格尽可能高效地工作。这真的是你需要担心的。从一个位置移动东西,从而更新树是非常快的。但是当涉及到合并和拆分时,如果你经常这样做,它可能会变得昂贵。

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

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

干杯!


编辑

树中可以优化很多东西。但是如你所知,过早的优化是所有邪恶的根源。所以从简单开始吧。例如,您可以创建一些可在遍历树时使用的通用回调系统。这样你就不必查询树来获得与绑定框“问题”匹配的对象列表,而是只需遍历树并在每次点击时执行该回调。 “如果我提供的这个绑定框与你相交,那么用这些参数执行这个回调”


7
2018-05-22 22:11





你最肯定想检查 这个来自gamedev.net的碰撞检测资源列表 出。它充满了游戏开发惯例的资源。

除了碰撞检测以外,请检查它们 整个文章和资源列表


5
2018-05-22 20:27





我关心的是一棵树有多好   世界的细分能够   处理大尺寸差异   实体?分裂世界   足够小的实体了   较大的人需要占用一个   我和很多地区   关心这将如何影响   系统的性能。

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

  • 将对象存储在两个分支中,一直向下。一切都以叶子节点结束,但最终可能会有大量的额外指针。可能适合静态的东西。

  • 拆分区域边框上的对象,并将每个部件插入各自的位置。造成很多痛苦,并且没有很好的定义很多对象。

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

顺便说一句,你使用四叉树的原因是因为它真的很容易使用。您没有任何基于启发式的创建,就像您可能使用某些BSP实现一样。这很简单,它完成了工作。

我的另一个主要问题是如何   妥善保管被占用的清单   区域是最新的。因为有很多   移动实体,有些非常   大的,好像分开了   世界上将创造一个重要的   保持跟踪的开销量   哪些实体占据哪个   区域。

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

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


4
2018-05-23 10:21





有很多方法。我建议设置一些特定目标(例如,每秒x次碰撞测试,最小实体与最大实体之间的y比率),并进行一些原型设计以找到实现这些目标的最简单方法。您可能会感到惊讶的是,您需要做的工作很少,无法满足您的需求。 (或者,根据您的具体情况,可能需要大量工作。)

许多加速结构(例如,良好的BSP)可能需要一段时间来设置,因此通常不适合于快速动画。

关于这个主题有很多文献,所以花一些时间进行搜索和研究,以提出一个列表候选方法。嘲笑他们并简介。


2
2018-05-22 21:40





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

通过将射弹保持在网格/树/等查找系统之外可以获得进一步的收益 - 因为您可以快速确定射弹在网格中的位置,您知道哪个网格方格可以查询潜在的碰撞。如果你依次检查每个射弹对环境的碰撞,那么其他实体就不需要反过来检查与射弹的碰撞。


1
2018-05-26 10:15