生成BSP树中每个对象的组合(不重复)

Question

我正在制作一个碰撞检测系统二叉空间分区树。我有两种对象:

• 需要检查与其他物体碰撞的动态对象(角色、弹丸)，
• 静态对象(如墙壁)，这些对象不会被测试彼此之间的碰撞，但只能针对动态对象进行测试。

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

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

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

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

<>之前＼动态对象列表:{dynA, dynB}树:dynA/static1 dynB之前

测试组合:

dynA - dynA(无用的情况处理)
• dynA - static1
• dynA - dynB
• dynB - dynA(同上)
• dynB - static1
dynB - dynB

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

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

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

我的问题是:如果这种技术是正确的(我的意思是它是一个好的设计吗?)，并且因为每个对象在c#中都有一个唯一的引用，我可以像这样直接比较它们的引用吗:(?)

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

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

Answer 1

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

1)使用立方子体积作为三维网格来缓存每个实体所在的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将这种结构称为trace_t。如果有帮助的话，这里是我的:

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