1

我正在使用 Binary Space Partitioning Tree制作碰撞检测系统。我有两种对象：

  • 需要检查与其他对象碰撞的动态对象（角色、射弹），
  • 静态对象（如墙壁）不进行相互碰撞测试，但只能针对动态对象进行测试。

为此，我使用了两种数据结构：用于存储所有动态对象的列表，以及包含每个对象（动态或静态）的 BSP 树。因此，每个动态对象都存储在两个结构中。

最后，我通过遍历我的列表并使用树来测试每个对象来执行我的碰撞检测，如下所示：

foreach(DynamicObject dynobj in myListOfDynamicObjects)
{
    //check the collision against every close dynamic or static objects
    myBSPtree.CheckCollision(dynobj);
}

然而，在这一点上，我没有想到：两个动态对象之间的每次碰撞检查都会进行两次。例如 ：

                                                                \
动态对象列表：{dynA, dynB} 树：dynA
                                                              / \
                                                          静态1动态B

组合测试：

  • dyna - dyna （处理无用的情况）
  • 动态-静态1
  • dynA - dynB
  • dynB - dynA（同上）
  • dynB - 静态1
  • dynB - dynB

为了跳过无用的检查，我想在每个对象上添加一个属性Order：它将是对象构造时给出的唯一标识符，并像这样使用：

if(dynA.Order < dynB.Order){ CheckCollision(dynA,dynB); }

这样，每个对象组合只进行一次碰撞检查。

我的问题是：如果这种技术是正确的（我的意思是它是一个好的设计吗？），并且由于每个对象在 C# 中都有一个唯一的引用，我可以像这样直接比较它们的引用吗：（？）

if(dynA.Reference < dynB.Reference){ CheckCollision(dynA,dynB); }

我们可以使用object.ReferenceEquals来查看两个引用是否相等，但是我们可以对这些引用进行实际比较吗？

4

1 回答 1

1

我会好好看看 Quake/2/3 如何处理这个问题。您可以在这里考虑一些优化：

1) 使用三次子体积作为 3 维网格来缓存每个实体所在的 BSP 的哪个区域。这样，您只需针对整个树的子集测试每个动态对象。随着 BSP 树大小的增长，这是一个巨大的性能改进。

这是我的实现，它是从 Quake2 借来的，并且为了可读性而进行了大量清理：

https://github.com/jdolan/quetoo/blob/master/src/server/sv_world.c

2）为了避免重复的碰撞检查，只需在您的主要碰撞入口点引入一个计数器，并在每次调用该函数时递增它。测试给定对象时，将其自己的碰撞计数器设置为当前计数器值。在进行任何工作之前检查该值。这就是 Quake 避免两次检查相同 BSP 节点的方式。

if (obj->collisionCounter == _collisionCounter) {
    return;
}

obj->collisionCounter = _collisionCounter;

如果您希望您的碰撞代码是线程安全的，请确保您具有所有碰撞参数和状态的碰撞上下文结构，并将该结构的实例传递给您的所有碰撞函数。而且，当然，实现该collisionCounter结构的内部。Quake 称这种结构为 a trace_t，顺便说一句。再说一次，如果它有帮助，这是我的：

https://github.com/jdolan/quetoo/blob/master/src/collision/cm_trace.c

于 2016-10-24T12:36:52.967 回答