WANcatServer

矩形碰撞檢測 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

CATALOG
  1. 1. 矩形對矩形
    1. 1.1. 註:矩形的表示方式 XYWH
  2. 2. …那圓形對矩形呢?
    1. 2.1. 找尋規律
    2. 2.2. 發現例外
    3. 2.3. 計算最靠近的點