c++ - 碰撞检测和时间复杂度 : How do I make checking for collisions easier?

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

您可以使用 quadtree快速找到与另一个矩形相交的所有矩形。如果你需要处理非矩形形状，你可以先找到bounding boxes的对象相交。

Some common uses of quadtrees

• ...
• Efficient collision detection in two dimensions
• ...