比簡單地檢查每對對象更好的2D碰撞檢測性能

我需要我的2D碰撞檢測算法是可伸縮的，但我擔心它不是。我的算法做到這一點：比簡單地檢查每對對象更好的2D碰撞檢測性能

創建精靈對象的鏈表（包括所有的數據）

private LinkedList<Sprite> collisionSpritesList = new LinkedList<Sprite>();
主客場循環，然後將所有精靈的鏈表：

public void GameUpdate() { collisionSpritesList.add(avatar); collisionSpritesList.add(enemy1); collisionSpritesList.add(enemy2); }
然後collisionCheck()方法所謂的;它循環遍歷列表中所有對的實體，尋找衝突。然後LinkedList被完全擦除。這是因爲實體需要更新其新位置。

公共布爾checkCollision（）{

for(int i = 0; i < collisionSpritesList.size(); i++) 
{ 


for(int j = 0; j < collisionSpritesList.size(); j++) 
{ 
if(i != j) 
{ 
    if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle())) 
    { 
     Point p = gridMap.getRandomWalkableLocation(); 
     collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize()); 
     collisionSpritesList.clear(); 
     return true; 
    } 
    }

}}

collisionSpritesList.clear(); 
    return false; 
}

我的問題是如何有效的檢查碰撞的這種方式？應該以不同的方式完成嗎？如果是的話，那裏有哪些可擴展的方法？

來源

2011-05-08 abc123

我會考慮使用QuadTree來細分你的空間，然後只檢查在同一個「桶」或空間中的精靈的碰撞。

來源

2011-05-08 12:37:16

如果你可以在一個數據結構中劃分你的精靈並考慮它們的位置，那麼你可以限制你需要執行的碰撞測試次數。

使用的一種數據結構稱爲四叉樹。下面LIMK介紹如何使用碰撞檢測，結合四叉樹：

http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

來源

2011-05-08 12:41:56 ditkin

保持一個排序列表（由軸的一個排序），並用冒泡排序，這將擴展至O求助於它每個週期（n * x），其中x是每個週期的平均移動量。

，然後使用具有O（N * K），其中k軸

上的排序的平均重疊（列表它由minX這裏排序）

for(int i = 0; i < collisionSpritesList.size(); i++) 
{ 
    for(int j = i+1; j < collisionSpritesList.size(); j++) 
    { 
    if(collisionSpritesList.get(j).getRectangle().minX()>collisionSpritesList.get(i).getRectangle().maxX()) 
     break;//breakout inner for when no overlap on x-axis possible 

    if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle())) 
     { 
     Point p = gridMap.getRandomWalkableLocation(); 
     collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize()); 
     return true; 
     } 
    } 
}

掃描算法

來源

2011-05-08 13:35:02

比簡單地檢查每對對象更好的2D碰撞檢測性能

回答

相關問題