碰撞檢測優化

Question

我在尋找關於碰撞檢測優化的信息。

存在從點a移動到點b的對象（圓圈）。該物體具有半徑r，並且在該領域也有許多障礙（圓圈）。

我有檢查圓和膠囊之間的碰撞算法（函數），我現在把這個功能每障礙：

for-each (o : obstacles) 
    if collide(o, Capsule(a,b,r)) 
    return true; 

return false; 

許多障礙還相差很遠遠離運動物體，通過碰撞檢測功能可以忽略它們。

我的問題是：

有沒有忽略檢查與碰撞檢測功能的一切障礙的解決方案？類似於最近的鄰居搜索或KD樹？

編輯：所有的障礙物都有相同的半徑。

Answer 1

作爲第一步，您可以忽略所有的障礙物，而不是在特定的框架/框中。

E.g. y座標的所有障礙物（障礙物形狀的y-最低點）大於運動物體半徑的a和b +相同距離的最大y座標可以忽略不計。類似於較低的y邊界和x邊界。 而不是一個盒子，你可以進一步分成兩個（更多）盒子。例如，購買將a-b的距離分成兩個距離，並對（a，（b-a）/ 2），/（b-a）/ 2，b）中的每一個進行上述過程。

但是，這一切都取決於您可以比較這些值與您的碰撞過程相比有多高效。

Answer 2

您可以簡單地使用一個網格，其中每個單元格都包含觸摸該單元格的所有障礙物。現在只需檢查膠囊觸及的碰撞單元。 同樣你也可以使用四叉樹，但從我的經驗來看，網格通常足夠，並且還具有在障礙物移動的情況下易於快速更新的優點。

Answer 3

我可以推薦一個怪物曲線，例如希爾伯特曲線。它是一個像數據結構一樣的四叉樹或kd樹，它將二維複雜度降低爲一維問題。在每一幀你可以從開始建立怪物曲線，這樣可以省去刪除或插入四叉樹或kd樹。它也有一些更好的2D平鋪屬性，但在您的情況下可能不需要。

Answer 4

對馬丁的回答的評論：

這是簡單和好的方法在我的情況。

我做了個盒子狀Box(a.x-R, a.y-R, b.x+R, b.y+R)

其中R = ObjectRadius+ObstacleRadius和刪除每一個障礙是不是這個盒子裏。

在圖中，只有有黃點的障礙物纔會檢查。

障礙

Answer 5

1. 認沽中心到KD樹。
2. 找到最近的中心。
3. 檢查它是否比ObstacleRadius更接近。

Answer 6

您可以嘗試在您的代碼中實現空間分區。將每個物體/障礙物劃分成覆蓋整個空間或地圖的每個箱子。通過這樣做，您可以將障礙分組。所以你可以通過檢查小部分內的碰撞來減少大量的碰撞檢查。如果你的障礙物沒有移動，你只需要爲每個障礙物分區一次。如果他們正在移動，則必須每次更新每個障礙物的分區[重組]。

空間分區技術已經存在了相當長的一段時間，這裏有一個鏈接可以幫助你實現。

http://gameprogrammingpatterns.com/spatial-partition.html