碰撞檢測和時間複雜性：如何更輕鬆地檢查碰撞？

我想寫一個處理各種對象檢測的程序。對象具有原點，寬度，高度和速度。有沒有辦法建立一個數據結構/算法，以便每個對象不檢查其他對象？碰撞檢測和時間複雜性：如何更輕鬆地檢查碰撞？

這個問題我想避免的一些示例代碼：

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]); 
     } 
    } 
}

來源

2012-07-06 user965749

我不認爲你可以使它更容易* *比目前你在做什麼，但是你可以把它很多*更快*。你在問什麼？ – 2012-07-06 22:04:50

如前所述其他答案（s），您可以使用四叉樹結構來確定碰撞更快。

我會推薦GEOS開源的C++庫，它有一個很好的四叉樹實現。 Here are the docs for their quadtree class。

所以，你的僞代碼是這樣的：

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. 
}

來源

2012-07-06 22:06:26 csd

您可以使用quadtree快速找到與另一個矩形相交的所有的矩形。如果您需要處理非矩形形狀，您可以首先找到與bounding boxes相交的對象。

四叉樹

的一些常見用途...

高效的碰撞檢測兩個維度

...

來源

2012-07-06 21:57:59

碰撞檢測和時間複雜性：如何更輕鬆地檢查碰撞？

回答

相關問題