[筆記] 矩形的碰撞偵測 (上篇)

　　寫遊戲常常用 API 來幫忙處理碰撞偵測，當需要自己寫類似的功能時，發現內部的運作沒有想像中的簡單。最近因為專案的需求，撰寫打磚塊遊戲，原本想利用 pygame 的碰撞偵測，但是不適合這個專案，只好挽起袖子研究研究作作看。上篇介紹矩形碰撞偵測的原理，下篇則介紹在碰撞之後反彈的效果。

pygame 中的碰撞偵測

---

　　pygame 的碰撞偵測（pygame.Rect.colliderect 或是 pygame.sprite.collide_rect）是要兩個矩形重疊才算碰撞。

>>> rect_a = pygame.Rect(0, 0, 5, 5)  # (left, top, width, height)
>>> rect_b = pygame.Rect(5, 0, 5, 5)
>>> pygame.Rect.colliderect(rect_a, rect_b)
0

rect_a 與 rect_b 是相切，並沒有重疊，因此 colliderect 判定沒有碰撞發生。

如果把 rect_b 往左邊移動一格，兩個矩形就會重疊，colliderect 判定有碰撞發生。

>>> rect_b.move_ip(-1, 0)  # (dx, dy)
>>> pygame.Rect.colliderect(rect_a, rect_b)
1

但是在這次專案需要使用的遊戲中，我希望碰撞的情形也要包含兩個矩形相切的情況，就像是兩個平面互撞一樣。

偵測兩個矩形是否碰撞

---

　　在加入相切的條件之前，先了解如何判定碰撞。訂一個矩形的左上角座標為 (left, top)、右下角為 (right, bottom)，用這兩個座標就可以訂出一個矩形的四邊位置。
　　要知道兩個矩形有沒有相撞，可以從兩個矩形「沒有相撞」來思考。設兩個矩形 a 與 b，以下情況可以確定兩個矩形沒有相撞，並列出成立的條件，設定原點在左上方（為了與 pygame 的座標系統一樣，定 x 正方向為向右，y 正方向為向下）：

　A. a 在 b 的上方：a.bottom < b.top
　B. a 在 b 的下方：a.top > b.bottom
　C. a 在 b 的左方：a.right < b.left
　D. a 在 b 的右方：a.left > b.right

把 a 與 b 的關係對調也會得到相同的關係。把這四個條件所形成的區域畫出來，可以發現只要矩形 a 在該區域內（也就是符合上述的任一條件）就一定不與矩形 b 相撞。

反過來說，只要矩形 a 不完全處在該區域內的話，就一定與矩形 b 相撞。將表達式寫出來：

• 四個條件構成的區域：(A or B or C or D)
• 不完全處在該區域：not (A or B or C or D)
• 迪摩根定律：not (A or B or C or D) = (not A) and (not B) and (not C) and (not D)

利用迪摩根定律轉換的結果可以得到矩形 a 與矩形 b 相撞的條件是（y 正方向為向下）：

(a.bottom >= b.top) &&
(a.top <= b.bottom) &&
(a.right >= b.left) &&
(a.left <= b.right)

所得到的式子即為 AABB (Axis-Aligned Bounding Box) collision detection。將符合條件的任一矩形畫出來，可以看到矩形 a 與 b 是相撞的：

這個網站透過自由拖拉兩個矩形來演示兩個矩形是否相撞，很棒的視覺化 demo。

在 pygame 中製作包含相切的碰撞

---

　　回到 pygame 上，pygame 的 Rect 提供 top、bottom、left、right 四個屬性，可以取得矩形的四個邊的座標。要注意的是 bottom 與 right 是不包含在矩形中（exclusive upper bound），意思是矩形的水平座標涵蓋範圍是 left <= x <= right - 1，而垂直座標涵蓋範圍是 top <= y <= bottom - 1。

要在 pygame 中檢測兩個矩形是否碰撞的話，就必須要去除等餘的情況，舉例來說，原本推得的條件 a.bottom >= rect_b.top，在 pygame 中會是 a.bottom - 1 >= rect_b.top，等同於 a.bottom > rect_b.top。依此類推如下：

def check_rect_collide(rect_a, rect_b) -> bool:
    if rect_a.bottom > rect_b.top and 
       rect_a.top < rect_b.bottom and 
       rect_a.right > rect_b.left and 
       rect_a.left < rect_b.right:
        return True
    return False

>>> rect_a = pygame.Rect(0, 0, 5, 5)
>>> rect_b = pygame.Rect(5, 0, 5, 5)
>>> check_rect_collide(rect_a, rect_b)
False
>>> rect_b.move_ip(-1, 0)
>>> check_rect_collide(rect_a, rect_b)
True

　　還記得前面希望碰撞也要包含相切的情況嗎？相切的時候，兩個矩形的邊界會剛好相差 1 單位，舉例來說，依照原本的條件 rect_a.bottom >= rect_b.top，應該要改成 rect_a.bottom + 1 >= rect_b.top，就好像是偷偷幫矩形往水平（或垂直）方向長 1 單位（注意所有矩形長的方向要一致），讓矩形能夠相撞，但實際上是相切。

利用 pygame 的 Rect 中的 bottom 與 right 是 exclusive upper bound 的特性，只要加上相等的條件就可以達成了，因為 bottom 是實際的底邊往下 1 單位，right 是實際的右邊往右 1 單位：

def check_rect_collide(rect_a, rect_b) -> bool:
    if rect_a.bottom >= rect_b.top and 
       rect_a.top <= rect_b.bottom and 
       rect_a.right >= rect_b.left and 
       rect_a.left <= rect_b.right:
        return True
    return False

>>> rect_a = pygame.Rect(0, 0, 5, 5)
>>> rect_b = pygame.Rect(5, 0, 5, 5)
>>> check_rect_collide(rect_a, rect_b)
True

參考資料

---

• Determine if two rectangles overlap each other? - stack overflow
• Rectangle Intersection Demonstration
• pygame.Rect - pygame documentation