c++ - 碰撞检测和时间复杂度：如何更轻松地检查碰撞？

Question

我正在尝试编写一个处理各种对象检测的程序。对象具有原点、宽度、高度和速度。有没有办法设置数据结构/算法，以便每个对象都不会与其他所有对象进行检查？

我试图避免的问题的一些示例代码：

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
       }
    }
}

Answer 1

您可以使用四叉树快速找到与另一个矩形相交的所有矩形。如果您需要处理非矩形形状，您可以先找到边界框相交的对象。

四叉树的一些常见用途

• ...
• 二维高效碰撞检测
• ...

Answer 2

正如其他答案所提到的，您可以使用四叉树结构来加快碰撞检测速度。

我会推荐GEOS开源 C++ 库，它具有良好的四叉树实现。 这是他们的四叉树类的文档。

所以你的伪代码看起来像这样：

Quadtree quadtree;
// Create and populate the quadtree.
// Change it whenever the balls move.

// Here's the intersection loop:
for (int i=0; i<ballCount; ++i) {
    Envelope envelope = ...;  // Get the bounds (envelope) of ball i
    std::vector<void*> possiblyIntersectingBalls;
    quadtree.query(envelope, possiblyIntersectingBalls);
    // Now loop over the members of possiblyIntersectingBalls to check
    // if they really intersect, since quadtree only checks bounding
    // box intersection.
}