碰撞檢測問題

Question

我的cocos2d-x是全新的。
從開發一個簡單的遊戲，這是像「飛機大戰」

一個問題，當我實現了碰撞檢測迷惑我剛開始。

• 假設球員的平面能火50+子彈每 時間。
• 超過50+敵人出現在屏幕上。
  

這意味着我必須做50 * 50次檢測的每一幀，倍！ 比賽中的表現應該墜落

所以，我怎麼能優化碰撞檢測？

Answer 1

我不能說Cocos2d，因爲我不使用它。但總的解決方案包括：

打破你的遊戲世界分解成地區

例如將你的世界劃分爲100x100像素塊。在每個對象的每個幀的開始處確定哪些塊（注意複數）會重疊。如果你定期劃分你的世界，這應該很便宜。將您的對象添加到每個塊中的對象列表中。

接下來，再次運行您的對象，這次從塊中讀取。針對與對象重疊的任何其他對象重疊的所有其他對象進行測試。

更復雜的分割策略可能包括四叉樹或kd樹。如果你的世界已經內在地分裂了（例如，對於某些類型的快速碰撞或能見度計算，凸出的扇區），那麼你可以經常搭載它。

迭代一起排序列表

選擇任何尺寸你的世界是最長的一起。比方說，爲了論證的緣故，它是寬於高的，而且你不想考慮對角線。

然後通過開始x位置來排序所有對象。

現在沿列表進行迭代。對於列表中位置爲i的每個對象，請將其與i+1,i+2等中的對象進行覈對，直到找到其最左邊的x超出最右邊的第一個對象。然後停止考慮i處的對象並允許循環滾動到下一個對象。你正在考慮的對象絕對不能與你停止檢查的對象之外的任何對象發生碰撞，因爲它們的最左邊甚至更靠右。

這是極少數情況下插入排序可以是最快的排序，因爲它是最優的 - O（n） - 如果應用於已經排序的列表，並且通常更接近最佳，列表越接近排序。在一個遊戲中，你的對象排序可能在幀之間只有一點變化，所以如果他們排序的最後一幀，他們很可能接近排序這個幀。

不要那麼直接跳轉到昂貴的測試

這些都是廣泛的相位檢測策略，防止絕對不重疊的對象之間的比較。即使一旦你反對對象，你應該考慮在做一個精確的像素檢查之前做一些廣泛的東西。最簡單的解決方案是包圍球 - 制定出爲每個對象一箇中心和半徑然後作爲第一檢查工作出來的兩個中心之間的距離的平方（使用畢達哥拉斯但不超越所述距離的平方，以避免昂貴的方根），並將其與兩個半徑之和的平方進行比較。如果兩個物體至少沒有那麼近，那麼它們就不能重疊，所以你可以跳過更精確的東西。

根據你的成本和你的幾何形狀一般你也可以考慮凸包分離軸（特別是如果你有一個足夠快的機制來緩存哪個軸分開的任何兩個給定對象的最後時間）。