LancatServer

矩形碰撞檢測 FireWheel火輪手槍(二)

Word count: 1,948 / Reading time: 7 min
2018/08/02 Share

矩形對矩形

那今天如果是矩形之間的碰撞呢？雖然在我的遊戲中並沒有運用到矩形對矩形的碰撞，但是這算是碰撞檢測的基礎之一，因此我還是一併說明。

#註：此處說明之矩形皆為不旋轉的矩形

矩形對矩形的碰撞檢測需要用到「座標」的概念，總的來說，就是判斷兩個矩形的x範圍與y範圍有沒有重疊。只要x範圍與y範圍同時重疊了就代表這兩個矩形碰到了。
同樣的，我們先來列出已知資訊：

  • 座標(x, y)
  • 長寬(w, h)

註：矩形的表示方式 XYWH

在電腦中，表示一個矩形的方法跟數學上有些許不同。首先，在電腦的座標系中，Y是向下增加的，這樣的座標系稱為「繪圖座標系」。
在繪圖座標系之中，原點在螢幕的左上角，因此x向右增加，y向下增加。

先退一步來講，在數線中，該如何判斷一條線與另一條線重疊？
我們可以用邊界的角度來思考，今天有兩條線段 AB線段, CD線段 在同一直線上，會有兩種情形，CD 在 AB 的左邊或者右邊。假如 CD 在 AB 右邊時，只要 C 比 B 還要左邊，就代表重疊了；假如 CD 在 AB 左邊，只要 D 比 A 還右，就代表重疊了。

發現了嗎？只要我的左邊比你的右邊還左 and, 我的右邊比你的左邊還右，就代表我們站在前後了。

那今天我們把左邊右邊換一個說法，在繪圖座標系中一個矩形的座標位置會是左上角，那這樣左邊就是x，右邊是x + w；上面是y，下面是y + h。
你沒聽錯，y愈上面愈小，y愈下面愈大，在電腦的繪圖座標系中確實如此。

以下用 r1, r2 來代表矩形1、矩形2。
左邊在數線上通常是變小，因此就是小於。因此剛才的陳述就可以換成這樣：
r1.x < r2.x + r2.w # r1的左邊比r2的右邊還左（考慮r1在右時）
r1.x + r1.w > r2.x # r1的右邊比r2的左邊還右（考慮r1在左時）

以上判斷可以讓我們知道r1與r2的x範圍是否有重疊，注意，這邊並不是判斷r1與r2的邊有沒有相交喔！

那只判斷x範圍還不夠，我們還需要判斷y範圍有沒有重疊。y的判斷也一樣，只要照一樣的方式寫，把x換成y，w換成h就可以了。
由於y點在上方，所以愈上數字會愈小，只是表達的方式不同，但實際計算是沒有差別的。
r1.y < r2.y + r2.h # r1的上邊比r2的下邊還上（考慮r1在下時）
r1.y + r1.h > r2.y # r1的下邊比r2的上邊還下（考慮r1在上時）

而這所有條件必須要全部符合才代表兩個矩形相撞，因此我們將每個條件用and連起來，就會只有在全部符合的時候才回傳true。
以下為Python實做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
判斷矩形是否相交函數
輸入：r1, r2兩個矩形物件
r1與r2分別帶有 x, y, w, h四個屬性
輸出：碰到(true), 沒碰到(false)
'''
def rect_to_rect (r1, r2) :
    return (
        r1.x < r2.x + r2.w and
        r2.x < r1.x + r1.w and
        r1.y < r2.y + r2.h and
        r2.y < r1.y + r1.h
    )
#在函數裡為了排版整齊，我將第2及第4行的大小於順序調換，對程式執行是沒有差別的
#實作者：林宏信 2018 7/21

…那圓形對矩形呢？

在我的遊戲中有「牆壁」，是玩家與怪物都無法穿過的障礙物。玩家與怪物是圓形，而牆壁卻是矩形。完蛋了，現在不能用兩物件的距離，因為牆壁不是圓的；也不能用座標系重疊，因為圓形不是方的。
沒關係，我們先列出已知的資訊：

項目 屬性 附註
圓形 x, y, r x, y為圓心座標
矩形 x, y, w, h x, y為矩形左上角座標

好，這次是真正的難題了，在場有同學能為我們指引方向嗎？ （等一下）

找尋規律

我們先來亂猜看看，今天如果把一顆球從矩形右邊靠近，我們只要注意球的圓心到矩形右邊的距離，是否小於半徑就可以了；那如果從上面靠近呢？嗯…那應該就要跟上邊比才對；那如果從左邊來就跟左邊比、下面來就跟下邊比，好像沒有很難吼？

發現例外

那如果從左上方來呢？該跟誰比勒？
今天這顆球假如在矩形的右上方，圓心跟矩形左側及上側的距離已經小於半徑，也就是我們原先以為應該要碰到的情況，但實際上並沒有碰到。這又該怎麼辦？

看來計算圓心到邊的距離並不完全正確，
如果我們要計算圓形是否有碰到矩形，那是否能利用圓形到矩形的最短距離呢？!
只要判斷圓心到矩形的最短距離是否有小於半徑，應該就可以了吧！
沒錯！這就是圓形對矩形的核心概念，透過判斷最短距離是否小於半徑，來檢測圓是否有碰到矩形。

因此我們要來找出一個矩形最靠近圓心的那個點在哪裡，透過這個點和圓心的距離，來判斷圓是否有碰觸到矩形。

計算最靠近的點

首先，假如矩形不存在，最靠近圓心的點在哪裡？就在圓心，我知道這樣講是廢話，但只要我們把圓心的x, y給限制在矩形的範圍中，讓它盡可能的接近圓心，就可以找到最近點了。

所謂 「限制」 的意思是說，假如這個點比矩形的右邊還右，那就將它設定為矩形的右邊；如果比矩形的左邊還左，就將它設定為矩形的左邊；假如它沒有超過矩形的座標範圍，那就保持它原先的座標。上下邊以此類推。

那我們將上述講的「限制範圍」這件事寫成一個函數，讓我們後面可以重複呼叫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
定義 set_range 函數，將數值 number 設定在 minimal 到 maximum之間的範圍。
輸入：最小值、最大值、欲計算數字
輸出：計算後結果，介於minimal ~ maximum 之間
'''

def set_range (minimal, maximum, number):
    if number > maximum:
        return maximum
    elif number < minimal:
        return minimal
    else :
        return number

# 實做：林宏信 2018-7-25

那我們接下來只要將數字分別帶入函數中即可。
矩形的左邊即x, 右邊為x + w
矩形的上面是y, 下面是y + h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''
定義 圓形矩形碰撞檢測函數
輸入: c: 圓形物件，帶有 x, y, r屬性
     r: 矩形物件, 帶有 x, y, w, h屬性
輸出：碰到: True / 沒碰到: False
'''

def circle_to_rect (c, r):
    x = set_range(r.x, r.x + r.w, c.x) # 呼叫上方定義的限制範圍函數
    y = set_range(r.y, r.y + r.h, c.y)
    d = ((c.x - x) ** 2 + (c.y - y) ** 2) ** 0.5 # 跟前面一樣利用畢氏定理求距離的算式
    return d < c.r #回傳「最短距離是否小於圓的半徑」的比較結果

#實做：林宏信 2018-7-25

作者: lancatlin 林宏信

發表日期: August 2nd 2018, 5:45:28

版權聲明: 歡迎分享文章。如要轉載須標明文章連結

CATALOG
  1. 1. 矩形對矩形
    1. 1.1. 註：矩形的表示方式 XYWH
  2. 2. …那圓形對矩形呢？
    1. 2.1. 找尋規律
    2. 2.2. 發現例外
    3. 2.3. 計算最靠近的點
Total : 7
2018
2018科展回顧 Docker life Minecraft OurLiveWorld
FireWheel OurLiveWorld