Collision Detection in 2D

Harrison Chen

Published in

Akatsuki Taiwan Technology

8 min readSep 25, 2020

Overview

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

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

Narrow Phase

Narrow Phase (精確階段) 指的是我們確定兩個物件靠的足夠接近後，我們針對兩個物件進行碰撞偵測的方式。
根據兩者形狀不同，會採取的方式也有所不同。
下面會介紹在2D遊戲中，幾種常見的情況。

Sphere Collision

球體碰撞可以說是其中最為簡單的碰撞處理，只需要判斷兩個球體的半徑和，有沒有超過兩者球心的距離即可判斷

從上圖就可以明顯看出，如果兩者球心距離小於兩者半徑之和，那這兩顆球就碰撞在一起。

距離公式如下：

SphereSphere Pseudo Code

function isSphereCollide():var diff = centerA - centerB
var distanceSqr = diff.sqrMagnitude
var radiusSum = radiusA + radiusB
var radiusSumSqr = radiusSum * radiusSum
return distanceSqr > radiusSumSqr

Box Collision

方塊碰撞同樣也是在遊戲中非常常見的類型，舉凡RPG遊戲或是推動方塊解謎的倉庫番，都會經常遇到需要進行方塊之間碰撞的情況。

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

Axis-Aligned Bounding Box

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

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

比如說兩個方塊擺放如下：

那麼判斷兩個方塊的碰撞，需要檢查的數字即為：

當這些條件全部都滿足時，就代表兩個方塊是不可能重疊的，反之如果兩個軸之間有互相交疊，那就會產生重疊碰撞。

Box-Box Pseudo Code

function isBoxCollide():return !(rectA.x < rectB.x + rectB.width &&
         rectA.x + rectA.width > rectB.x &&
         rectA.y < rectB.y + rectB.height&&
         rectA.height + rectA.y > rectB.y);

Polygon Collision

當然，互相碰撞的物件肯定不會永遠都是單純的圓形或是方形，在遊戲中，我們會時常遇到不規則的多邊形物理，特別是使用Sprite的角色和物件等，都是多邊形的物體。

雖然經常我們都會使用更簡單的形狀(如上面介紹的方形或是圓形，抑或是他們所拼起來的膠囊形狀)作為複雜碰撞體的模擬，但如果真的遇到需要進行複雜多邊形的處理時，我們可以使用下面提到的做法：

Separate Axis Theorem (SAT) 分離軸定理

分離軸定理的基本概念是，如果我們可以找到一條線可以將兩個凸多邊形分開，那他們之前必定不會碰撞。

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

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

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

概念的流程如下：

找出兩個多邊形各自每一個邊的法向量
將兩個多邊形上每一個點分別投影到該向量上
尋找這個邊究竟是不是分離軸 (p1.max > p2.min && p2.max > m1.min)

SAT Pseudo Code

function isSeparate(p1, p2):vert1 = p1.verts
vert2 = p2.verts
norms1 = vert1.getNorms()
norms2 = vert2.getNorms()for all norm in norms1 and norms2:
   minMax1 = getProjMinMax(vert1, norm)
   minMax2 = getProjMinMax(vert2, norm)   separate = minMax1.min > minMax2.max || minMax2.min > minMax1.max
   if separate
      return true
   else
      next iterateif not found any separate
  return false--------------------------------------------------------------------function isPolygonCollide(p1,p2):return !isSeparate(p1, p2)