Collision Detection in 2D. Overview | by Harrison Chen

Collision Detection in 2D ... 這篇文章大致介紹幾種在2D遊戲中常見的碰撞方法，以及簡單提及在遊戲世界中減少碰撞運算的製作策略。

GetunlimitedaccessOpeninappHomeNotificationsListsStoriesWritePublishedinAkatsukiTaiwanTechnologyCollisionDetectionin2DOverview遊戲製作中，碰撞是一個非常常見的遊戲功能，無論是早期的動作遊戲，抑或是打磚塊等休閒益智遊戲，只要和現實的物理行為有關的gameplay，都少不了碰撞偵測的存在。

這篇文章大致介紹幾種在2D遊戲中常見的碰撞方法，以及簡單提及在遊戲世界中減少碰撞運算的製作策略。

NarrowPhaseNarrowPhase(精確階段)指的是我們確定兩個物件靠的足夠接近後，我們針對兩個物件進行碰撞偵測的方式。

根據兩者形狀不同，會採取的方式也有所不同。

下面會介紹在2D遊戲中，幾種常見的情況。

SphereCollision球體碰撞可以說是其中最為簡單的碰撞處理，只需要判斷兩個球體的半徑和，有沒有超過兩者球心的距離即可判斷從上圖就可以明顯看出，如果兩者球心距離小於兩者半徑之和，那這兩顆球就碰撞在一起。

距離公式如下：SphereSpherePseudoCodefunctionisSphereCollide():vardiff=centerA-centerBvardistanceSqr=diff.sqrMagnitudevarradiusSum=radiusA+radiusBvarradiusSumSqr=radiusSum*radiusSumreturndistanceSqr>radiusSumSqrBoxCollision方塊碰撞同樣也是在遊戲中非常常見的類型，舉凡RPG遊戲或是推動方塊解謎的倉庫番，都會經常遇到需要進行方塊之間碰撞的情況。

方塊與方塊之間的碰撞雖然沒有圓形那麼簡單，但也非常容易可以推論出來。

Axis-AlignedBoundingBox判斷兩個沒有旋轉的長方形之間，有沒有互相碰撞在一起。

判斷方式也非常的直覺，直接對對照兩個長方形的長寬之間的距離，就可以判斷出兩者是否有重疊的範圍。

比如說兩個方塊擺放如下：那麼判斷兩個方塊的碰撞，需要檢查的數字即為：當這些條件全部都滿足時，就代表兩個方塊是不可能重疊的，反之如果兩個軸之間有互相交疊，那就會產生重疊碰撞。

Box-BoxPseudoCodefunctionisBoxCollide():return!(rectA.xrectB.x&&rectA.yrectB.y);PolygonCollision當然，互相碰撞的物件肯定不會永遠都是單純的圓形或是方形，在遊戲中，我們會時常遇到不規則的多邊形物理，特別是使用Sprite的角色和物件等，都是多邊形的物體。

雖然經常我們都會使用更簡單的形狀(如上面介紹的方形或是圓形，抑或是他們所拼起來的膠囊形狀)作為複雜碰撞體的模擬，但如果真的遇到需要進行複雜多邊形的處理時，我們可以使用下面提到的做法：SeparateAxisTheorem(SAT)分離軸定理分離軸定理的基本概念是，如果我們可以找到一條線可以將兩個凸多邊形分開，那他們之前必定不會碰撞。

如同上述的原理，這個演算法的目標就是尋找出可以分開兩個凸多邊形的那條直線，就可以斷定兩者並沒有碰撞，反之，如果找不到那條線，那麼兩個物體就發生碰撞。

找尋SAT的方法，其實和上面的方塊碰撞相當類似，我們將兩個多邊形的頂點投影到軸上(方塊碰撞是投影到座標軸上，更為單純)，確定是不是有一條軸可以讓兩個多邊形的投影不會相交。

原理雖然很簡單，但實際上不可能將所有的軸都進行測試一遍(因為在座標系中，存在的軸是無限的！)，所以我們只需要根據這兩個多邊形的相關軸向下手就可以了，在這邊我們可以遍歷兩個多邊形的所有邊的法向量(normal)，就可以在其中找到對應的分離軸。

概念的流程如下：找出兩個多邊形各自每一個邊的法向量將兩個多邊形上每一個點分別投影到該向量上尋找這個邊究竟是不是分離軸(p1.max>p2.min&&p2.max>m1.min)SATPseudoCodefunctionisSeparate(p1,p2):vert1=p1.vertsvert2=p2.vertsnorms1=vert1.getNorms()norms2=vert2.getNorms()forallnorminnorms1andnorms2:minMax1=getProjMinMax(vert1,norm)minMax2=getProjMinMax(vert2,norm)separate=minMax1.min>minMax2.max||minMax2.min>minMax1.maxifseparatereturntrueelsenextiterateifnotfoundanyseparatereturnfalse--------------------------------------------------------------------functionisPolygonCollide(p1,p2):return!isSeparate(p1,p2)ImplementationofSATinUnityCode:DemoGIF:BroadPhaseBroadPhase(廣泛階段)，指的是當世界(World)中有太多碰撞體，如果逐個使用SAT等高消耗的碰撞偵測方式去比對太耗效能了，甚至可能會無法在目標裝置上正常運作。

為此，我們會先使用空間加速演算法進行空間分類與加速，如果距離太遠的物件從一開始就不需要進入到NarrowPhase去進行比對。

常見的空間加速結構有像是OctTree,KD-Tree,AABBTree等，以下用簡單的AABB樹作為舉例。

AABBTree在broadphase階段，我們會將原本各種形狀的碰撞體，外面都包上一層AABB將碰撞體加上AABB當我們用AABB包覆每個碰撞體後，在進行更複雜的碰撞檢測前，就可以先偵測包覆他們的AABB有沒有碰撞，減低碰撞偵測的消耗。

但即使用上AABB去做碰撞檢測，我們還是必須比對n平方次物件，才能確定兩兩物體間有沒有碰撞。

當世界中的物體數量很多的時候，n平方會造成效能極大的負擔，此時，AABB-tree就派上了用場。

我們會將鄰近的碰撞體們用另一個AABB包覆起來，如下圖：將相關的AABB合併起來由此一來，偵測兩個物體有沒有兩兩碰撞，就可以被簡化成兩個更大的AABB之間有沒有兩兩碰撞，讓原本需要N-square的的次數被大幅減低。

而AABB樹的實作，就是兩兩一組的階層方式將AABB合併起來。

將最接近的兩個物件合併再將粉紅色的兩個物件合併最後加上rootnode形成二元樹用這種方式合併AABB就是AABB-tree的構建步驟，因為不是本篇的重點，所以較為複雜的insertnode,deletenode與關聯的調整等在這篇文章就不細談。

Conclusion這篇文章提到的碰撞偵測方法都是單純且簡單的方法，而目前常見的遊戲引擎以及商業引擎中都會包含完整的物理系統，其中也對這些碰撞體偵測進行了更完整的實作也更近一步做了許多的優化，所以自己造輪子的需求可能會日益減少。

不過，在遊戲設計時，常常並不需要用到完整的物理模擬，而是希望簡單偵測物體覆蓋等等。

而且商用物理引擎本身對於開發者來說，也不應該完全當成一個黑盒子，理解裡面的做法除了可以在使用商業引擎時更得心應手，必要時也可以自己製作簡單的碰撞規則來對應遊戲所需的設計。

此外，這些碰撞演算法以及思路對於開發遊戲上時常遇到的規則製作也是非常有用的啟發和應用，可以說是非常泛用的小知識！--MorefromAkatsukiTaiwanTechnologyEngineerBlogofAkatsukiTaiwanReadmorefromAkatsukiTaiwanTechnologyAboutHelpTermsPrivacyGettheMediumappGetstartedHarrisonChen7FollowersFollowMorefromMediumSezavarMaskRCNN,U-Net,DeepLabReviewYeohKengHzouAlittlejourneytowardImageProcessing — part1HongXiaohuiExplanationofORBinpointfeatureextractionHajarZoubirIdentifyingcracksinconcretebridgeimagesusingedgedetectiontechniquesHelpStatusWritersBlogCareersPrivacyTermsAboutKnowable