[筆記] 矩形的碰撞偵測 (下篇) - 沒被偵測到的碰撞

　　有時就是天不從人願，當覺得碰撞 OK，反彈 OK 的時候，就會出現不 OK 的情況。做了一個球速會漸漸加快的 pixel game，然後遊戲就逐漸毋湯。當球移動的速度很快的時候，球會穿越平台，連碰撞都沒有被偵測到，然後就蹦蹦了。

問題點

---

如圖所示，當球一次移動的距離大於板子的厚度時，板子可是一點感覺都沒有呢。因為球的移動並非連續移動，而是在這個影格是 A 地點，下一個影格就直接出現在 B 地點（直接加上要移動的距離）。可以想像做碰撞偵測時，是看當下每個物件的位子來判斷有沒有碰撞的，所以當球直接「掠過」板子時，就不會被偵測到碰撞。如此一來就會出現穿板的現象，原本應該繼續的遊戲，就 Game Over 了。

解法

---

　　既然會直接掠過去，那只好紀錄物件的移動路徑來做碰撞偵測。因為在場景中的物件碰撞箱都是以矩形為準，所以我會以矩形的四個角來產生移動路徑，如圖左的四條藍線，主要可以偵測到角碰角的情況，如圖右。

只要當任何一條藍線，也就是物件四個角的路徑任一一條，碰到另一個矩形，就是有碰撞。

演算法

---

　　解法的基底是去判斷一條路徑有沒有碰到矩形，換句話說就是，判斷一條路徑有沒有碰到矩形的任一個邊，也就是判斷任兩條線有沒有相交。先來推導式子（可編輯的版本在 hackmd 上）：

由推導結果可以知道，要算 s 與 t，要取得兩條線段的起點差的向量（Δu）與兩條線段各自起點到終點的向量（v）。

程式

---

兩線相交

將上面得到的算式轉換成程式碼，形成函式 line_intersect()，用來檢查兩條線是否相交：

def line_intersect(line_a, line_b) -> bool:
    """
    Check if two line segments intersect
    @param line_a A tuple (Vector2, Vector2) representing both end points
           of line segment
    @param line_b Same as `line_a`
    """
    # line_a and line_b have the same end point
    if line_a[0] == line_b[0] or \
       line_a[1] == line_b[0] or \
       line_a[0] == line_b[1] or \
       line_a[1] == line_b[1]:
        return True

    # Calculate if two line segments intersect 
    va = line_a[1] - line_a[0]
    vb = line_b[1] - line_b[0]
    det = va.x * vb.y - va.y * vb.x

    if det == 0:
        # Two line segments are parallel
        return False

    du = line_a[0] - line_b[0]
    s = (vb.x * du.y - vb.y * du.x) / det
    t = (va.x * du.y - va.y * du.x) / det

    if 0 <= s <= 1 and 0 <= t <= 1:
        return True

    return False

利用 pygame.math.Vector2 來代表點，傳入的線都是 2 元素的 tuple，代表線段的起點跟終點。一開始可以先做簡單的檢查，如果端點重疊，那就代表相交。接著帶入算式，判斷最後的 s 與 t 的值。

檢查線段有無碰到矩形

接著將矩形拆解成四個線段，依次跟指定線段檢查有無相交，如果有就是有碰到：

def rect_collideline(rect: Rect, line) -> bool:
    """
    Check if line segment intersects with a rect
    @param rect The Rect of the target rectangle
    @param line A tuple (Vector2, Vector2) representing both end points
           of line segment
    """
    line_top = (Vector2(rect.topleft), Vector2(rect.topright))
    line_bottom = (Vector2(rect.bottomleft), Vector2(rect.bottomright))
    line_left = (Vector2(rect.topleft), Vector2(rect.bottomleft))
    line_right = (Vector2(rect.topright), Vector2(rect.bottomright))

    return line_intersect(line_top, line) or \
        line_intersect(line_bottom, line) or \
        line_intersect(line_left, line) or \
        line_intersect(line_right, line)

這邊利用 pygame.Rect 提供屬性取得四個角的座標。要注意的是，因為在我的設計上是有包含「相切」的情況（詳見系列文的前篇），所以在產生線段時，右邊與下邊是比實際矩形還要大一單位。如果想要判定一條線有沒有「貫穿」一個矩形的話，則要計算相交的線段數是不是 2。

檢查移動的矩形是否有撞到另一個矩形

最後就是讓移動的矩形產生四個角的移動路徑，與要被撞的矩形做檢查，只要有任一條路徑撞到，那就代表這兩個矩形有相撞或相切：

def moving_collide_or_contact(move_last_pos, move_rect, target_rect) -> bool:
    """
    Check if the moving rectangle collides or contacts another rectangle.
    @param move_last_pos The `pygame.Rect` representing the position of moving rectangle at the last frame
    @param move_rect The `pygame.Rect` representing the current position of moving rectangle
    @param target_rect The `pygame.Rect` representing the current position of target rectangle
    """
    # Generate the routine of 4 corners of the moving sprite
    routines = ( \
        (Vector2(move_last_pos.topleft), Vector2(move_rect.topleft)), \
        (Vector2(move_last_pos.topright), Vector2(move_rect.topright)), \
        (Vector2(move_last_pos.bottomleft), Vector2(move_rect.bottomleft)), \
        (Vector2(move_last_pos.bottomright), Vector2(move_rect.bottomright))
    )

    # Check any of routines collides the rect
    ## Take the bottom and right into account when using the API of pygame
    rect_expanded = target_rect.inflate(1, 1)
    for routine in routines:
        # Exclude the case that the moving rectangle goes from the surface of target rectangle
        if not rect_expanded.collidepoint(routine[0]) and \
            rect_collideline(sprite.rect, routine):
            return True

    return False

這邊有一個額外的檢查，如果是線段的起點與目標矩形相交的話，那就要排除這條線。因為在碰撞檢查後，移動的矩形會被「排出」到被撞的矩形的表面（詳見系列文的中篇），此時移動的矩形在下一個影格就會從碰撞表面出發，如此一來起點一定會與目標矩形相交，所以要排除這樣的情況。這裡利用 pygame 提供的 API pygame.Rect.colldepoint 來檢查一個點有沒有碰到矩形，而為了包含相切的情況，所以要先讓目標矩形各往右往下拓展 1 單位，才去檢查（因為 pygame API 只有檢查有無嵌入的情況）。

效能

---

　　拿了之前做的打磚塊遊戲來測試效能，這個場景中有 96 個磚塊，代表每一個影格要做 96 次的碰撞偵測。
首先是原本的偵測方式約 2500 ~ 2600 fps：

而用新的演算法，可以看到一開始約 300 fps，隨著磚塊減少提升到 2000 fps：

雖然新的演算法計算比較繁雜，但是在場景中還是可以有 300 fps，以遊戲來說綽綽有餘。另外也可以搭配優化，以打磚塊來說其實只要檢查球附近的磚塊有沒有碰撞即可，所以可以事先切割區域，在檢查區域內的磚塊，不用全部檢查。

參考資料

---

• How to check if line segment intersects a rectangle? - StackOverflow
• Determining if two line segments intersect? - StackOverflow