2D遊戲中的碰撞檢測都是N^2複雜度嗎？

01-04

比如2D場景中有N個運動的物體（比如彈道）。碰撞檢測是在每一幀都進行N^2的檢查嗎？有沒有數據結構可以降低複雜度，比如運動方向相反的物體不做檢測？實際的遊戲開發是怎麼做的？
即使不知道實際項目是怎麼實現的，也希望大家談談自己的思路。

如果是RPG那樣的，完全可以用4叉樹來做碰撞檢查，再不濟也可以在每一個tile上保存上面所有物體的鏈表（一個物體可能會出現在多個tile上），怎樣都不會墮落到N^2

如果討論大O（複雜度上限）的話，確實是N^2的，這僅僅會發生在所有物體都重疊在一個很緊密的空間里的場合，而這種場合在遊戲里是不多見的。

採用四叉樹、AABB樹等演算法，可以讓絕大部分情況下的平均複雜度接近NlgN的水平。

針對快速移動的物體，它會在一幀里經過比較遠的距離，為防止穿越，需要對經過的整個距離做碰撞檢測，此時往往需要特別的優化。基本上都是一些很trick的技巧。

如果你遊戲中需要的碰撞檢測數量級很小，比如說：最多同時有個100參與碰撞檢測的單位，那麼四叉樹和網格演算法對效率沒有什麼實質性提升，但是隨著碰撞單位數量的增加，優化演算法的重要性就會非常關鍵，簡單的逐一測試演算法，只要到500個碰撞單位，以flash為例，幀數就會降到不能玩的地步。

四叉樹和網格這兩種演算法都是用來降低碰撞檢測複雜度的，網上都能搜索到詳細的資料，要搞清基本原理還是要搜索詳細資料仔細的看一下，三言兩語說不清楚。如果只是做一個單機小遊戲且碰撞不是很多的話，不想搞也可以，如果是做比較正式的項目最好研究一下，這兩種方法還是很實用很有幫助的。說一下經驗之談：四叉樹適用與碰撞單位的尺寸跨度很大的情形，就是說有的單位碰撞盒可能非常大，有的非常小，網格更適用於單位碰撞盒尺寸固定，或者尺寸變化範圍很小的情況。這兩個特點和演算法本身的機制是有聯繫的。

除了演算法以外，結合你的遊戲玩法機制設定，你幾乎總能歸納出一些隱含的限制規則，這些都可以加以利用，從而對演算法複雜度進行一些簡化，例如你自己提到的，反向的單位不參與檢測，只要你發現一些更簡單的規則且一定正確沒有例外，那這個規則就能用來優化演算法且不產生bug。

有朋友提到了穿越問題。如果碰撞單位是像子彈一樣速度飛快，那麼遊戲主循環的兩個邏輯幀之間，這顆子彈飛躍的區域可能就穿過了一個目標，如果你只是在每一幀內根據碰撞演算法檢測子彈是不是和某個目標重合了，結果都是false的，但這個過程從表現上看就是子彈像穿過空氣一樣穿過了目標，就是沒打中。針對可能出現的這種情況，你需要增加演算法，確保在兩幀之間增加足夠的採樣點，來檢測可能發生的碰撞。

扯多一點，碰撞檢測這套東西本身是用簡化的機制對真實世界進行模擬，目的是為玩家營造一種空間上的真實感，最終追求是要給玩家那種感覺，而不是真的利用技術儘可能做到和真實一樣，這是兩個不同的目標。碰撞檢測本身就是對真實世界的簡化，在保證建立規則與體驗的前提下，碰撞檢測本身也可以進一步簡化，比如：沒有實時檢測碰撞的子彈，所有子彈創建的那一刻，就已經根據子彈的位置，方向，速度，用一個簡化方法計算了他的生命周期內打到了誰。而不是真的在一個過程中去每幀不斷檢查他是不是有打到誰，俗稱「沒有彈道」。類似這種出於性能和網路考慮的折衷方案在網遊開發中還是比較常見的，總之當性能壓榨到極限以後，就要從障眼法上做文章了。

物理引擎的碰撞檢測是分為兩個階段的

第一個階段是叫做broad phase 這個階段才有簡單演算法判斷兩物體有無可能相交例如 aabb 包圍盒檢測

第二個階段稱為 narrow phase 這時候才對有可能碰撞物體進行解算

這兩個階段複雜的相差很大的第一個階段會排除大量不可能相交的物體

具體可以參考維基百科

http://en.m.wikipedia.org/wiki/Physics_engine

而四叉樹 uniform grid 等數據結構也應該算作 broad phase 裡面

上面兩位所說的 4 叉樹, 和 tile 的方法, 在Chipmunk2D這個物理引擎都有類似的實現, 適用於不同的場景, 這是一個開源引擎, 感興趣的話可以去看看對應API的源代碼.

另外他們的文檔中也提到了這兩種演算法, 還配有圖解, 值得一看.

Spatial Indexing: Chipmunk Game Dynamics Manual

Spatial Hashing: Chipmunk Game Dynamics Manual

Overview: Chipmunk Game Dynamics Manual

如果物體數目確實很少，比如10個，那麼用n^2遍歷也未嘗不可。

如果數目比較多，比如發射了一堆子彈，各種特效什麼的，那麼就需要用更好的演算法了。

如果非要自己做的話，首先需要對物體弄包圍盒，一般是軸對稱的比如AABB, 你也可以用球。

作測試有兩種，第一比如你要知道某個物體和場景中那個物體相交，一般比如主角和場景的碰撞，這裡用四叉樹，二叉樹比較方便。

如果是想獲得場景中所有的相交信息，那用四叉樹就慢了。這種情況下比較適合SAP(Sweep and prune)Sweep and prune。 SAP是基於AABB包圍盒，幾乎掃兩遍(橫一次豎一次)就可以得到場景中哪倆個包圍盒相交的列表。

然後對這個列表做進一步的測試就是narrowphase. Narrowphase可以做幾何體級別的測試和像素級別的測試，根據你的需要。如果遊戲物體是抽象到幾何體，比如憤怒的小鳥那樣的圓，convex, 和方塊，那就根據計算幾何的方法算一下，很快的。如果是像素級別的測試，那麼就比較來那個物體的像素是否有重合。

不過一般遊戲可以直接用box2d來做，比較省事，還帶物理效果。

不用四叉樹的話，可以使用多邊形連線的思路來進行碰撞檢測。

例如某一幀畫面中，有四個物體要進行碰撞檢測

var items = [item1, item2, item3,item4]

for(var i=items.length; i--;){ for(var j = i-1; j--){ if(collide(items[i], items[j])){ console.log("collide !"); } else { console.log("not collide"); } } }

上面不經過四叉樹進行碰撞檢測列表的優化，時間複雜度為O((1+N)*N/2)。

其實能優化的是，縮小碰撞檢測的列表，以及在在碰撞檢測列表中使用一對一（一對一貌似穩妥一點時間複雜度為O(N^2)），還是多邊形連線的思路進行碰撞檢測。