LV. 11
GP 69

【心得】常玩電腦的你,對遊戲中的碰撞檢測感興趣嗎? #49F補充

樓主 阿維 md9830415
278 -

作者標示-非商業性

本授權條款允許使用者重製、散布、傳輸以及修改著作,但不得為商業目的之使用。使用時必須按照著作人指定的方式表彰其姓名。

「遊戲中的多邊形碰撞檢測」



也許有些人對電腦遊戲中如何處理碰撞處理感興趣,希望你們能在讀完這篇文章後,也能大概了解遊戲是如何偵測物體的碰撞。


而這篇文有三個主要目的 :
  1. 對遊戲中的碰撞感興趣,卻不會寫程式的人可以了解原理
  2. 讓有能力實作的人,可以跟著文章寫出簡易的多邊形碰撞檢測
  3. 自己的學習筆記


這次要來介紹的主題是分離軸碰撞檢測(Separating Axis Theorem, SAT)
分離軸定理通常用語檢測兩個多邊形或多邊形與圓之間的碰撞,跟所有演算法一樣他具有一定的優勢與缺點。


文中我會慢慢講解背後的原理,並使用輕鬆的插圖與程式碼做簡單的範例。

範例所使用的語言為Java Script,加上自製的向量函式庫,但我想觀念懂了應該不會有太大問題。


讓我們開始吧

目錄
  1. 矩形碰撞檢測
  2. 什麼是分離軸檢測?
  3. 知識補充1 – 向量
  4. 知識補充2 – 旋轉變換
  5. 如何取得分離軸上的投影?
  6. 編寫程式碼-投影、旋轉與判斷
  7. 如何取得分離軸?
  8. 粗糙的矩形檢測
  9. 編寫程式碼 – 多邊形與多邊形
  10. 編寫程式碼 – 多邊形與圓
  11. SAT的總結
  12. 多物體的碰撞優化
  13. 動態物體間的碰撞檢測
  14. 結尾與感想
  15. 參考資源


這篇文章是我在Blog上寫完後,覺得有些人可能會感興趣,加上內容不深,所以想分享給大家,但是搬運的工程挺大的,因此我先擷取部份的內容做簡單整理,並用簡單明瞭的方式為各位講解。

希望你在閱讀後能有些收穫。



1. 矩形碰撞檢測


由最簡單的碰撞檢測開始講,這樣比較好讓各位了解為什麼需要分離軸檢測,所以先從一般的矩形碰撞開始。

所謂的矩形碰撞就是將兩個物體透過長方形包圍起來,這樣只需要檢查兩個矩形之間有沒有重疊就可以知道有沒有發生碰撞。

而這種檢測方式,就是所謂的AABB碰撞包圍盒,也許有人有聽過,但沒聽過也沒關西,並不影響閱讀。
讓我們先來看看矩形碰撞是如何運作的吧。


這裡有兩個矩形A、B,Box A最左邊為A.min、最右邊為A.max,而Box B同理。

由上圖一眼就可看出,兩盒子之間沒有發生碰撞,因為B.min > A.max。


當我們將兩盒子靠近後 :

可以明顯地看到A與B發生碰撞,這時的A.max > B.min,代表它們之間發生了重疊,物體之間沒有縫隙,碰撞發生了


而剛剛只有討論A左邊的狀況,如果這時A跑到右邊去了呢?

同樣的道理,當B在左邊時,條件就要稍微改一下,B.max > A.min時發生碰撞。


讓我們把得到的兩個結果合在一起,就可以得到這樣的條件 :



但聰明的你一定發現,只能檢查水平的啊! ! !
沒事,剛剛了解了水平的判斷後,垂直應該也不是太大的問題,把前面兩張圖抓下來,開小畫家轉90度讓它站起來,然後你就了解怎麼檢查垂直了。

只要將更改一下判斷的參數就完成了,上下的判斷應該就不用再寫算式了。


讓我們來看看結果 :

噹噹~太神啦~,你們成功完成了基本的矩形碰撞檢測了,輕鬆吧。


但是接下來的部分才是重點。

如果今天我們把某一個方塊旋轉一下 :

有發現到什麼問題?
沒錯,它們明明就沒有撞到,但是用剛剛的矩形檢測卻是告訴我碰撞。

所以可以得知矩形碰撞計算方法簡單、速度快,但卻有幾個問題:
1.當物體旋轉時就無法檢查
2.只能檢查矩型物體


那麼要如何解決這兩個問題呢?
沒錯,就是原文的主題「SAT碰撞檢測」,這個方法可以幾乎完美的解決這兩個問題。


到這裡差不多是我文中的第一小節,最後附上一張完成範例,希望因為這篇文章,而對碰撞感興趣的人可以去原文看看。

SAT碰撞檢測的範例 :





剩下的內容去哪了? 請加購額外補充包DLC
因為不好移植到這裡,所以我直接放我的文章連結


希望能幫助到一些對碰撞處理有興趣的人



總結:

可能很多人都直接先下拉,沒關西,我幫你們總結一下 :

我不會寫程式,那我看完這篇文有什麼用?

哪天朋友跟你抱怨「為什麼這樣都判定擊中」、「最好沒碰到就死啦」...時,
就可以拿著這些知識在朋友面前秀一波啦 ! ! !

痾...對,然後,就沒有然後了...。




如果有誤還請指教
----------------------------
2018/3/21 更新:因網站中途掛點,文章更換新的位置為http://davidhsu666.com/archives/gamecollisiondetection/
278
-
未登入的勇者,要加入討論嗎?
板務人員:

7567 筆精華,昨天 更新
一個月內新增 15
歡迎加入共同維護。


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】