彈幕遊戲的碰撞檢測一般是怎麼實現的？

01-26

在存在大量活動物體，且對象數量非常大的彈幕遊戲中，碰撞檢測一般用什麼方式實現？從早期遊戲（如街機）到現代彈幕遊戲，實現有沒有什麼進化？最好有已經存在的遊戲做實例。
補充：受「用像素碰撞才能真正重現街機的打機感」這條匿名回答的啟發，老的街機遊戲是不是可以在渲染的時候順便就把碰撞檢測做了？記得JavaME的API都是支持像素級檢測的。

在碰撞檢測的粗略階段（broad phase）可以使用空間劃分（space partitioning）[1]，把子彈動態地放置於區域里，例如二維的時間最簡單是把屏幕空間劃分成網格（grid），把每個子彈放至於方格之內。假設k是方格的數量，最好的時間複雜度得以提升至O(n/k)，但最壞仍然是O(n)，因為所有子彈可能集中在一起。常用的動態空間劃分方式還有四叉樹／八叉樹（quadtree/octree）、哈希空間（hash space）等。

上述的是說多個子彈與一個物體的碰接，而子彈與子彈之間是不會碰撞的。更通用的要檢查每個物體與其他每個物體是否碰撞，即最壞情況是O(n^2)的。傳統上可使用各種空間劃分方法，及／或掃掠裁減（sweep and prune）演算法[2][3]。

由於sweep-and-prune的做法最早見於1992年，所以之前的遊戲應該不會使用，更多的是用最簡單的網格空間劃分。關於這個問題也可參考[4]，它把space partition當作一個遊戲編程模式。

[1] Gregory著，葉勁峰譯，《遊戲引擎架構》，p. 562，電子工業出版社，2014。

[2] Bara, David. "Dynamic simulation of non-penetrating rigid bodies." Computer Graphics (SIGGRAPH92) (1992): 303-308.

[3] Cohen, Jonathan D., et al. "I-COLLIDE: An interactive and exact collision detection system for large-scale environments." Proceedings of the 1995 symposium on Interactive 3D graphics. ACM, 1995.

[4] Nystrom, Robert. Game programming patterns. Genever Benning, 2014. Spatial Partition · Optimization Patterns · Game Programming Patterns 中譯版：Game-Programming-Patterns-CN/06.4-Spatial Partition.md at master · GameDevelopmentCollege/Game-Programming-Patterns-CN · GitHub

彈幕遊戲永遠是新手學習遊戲開發第一個做的遊戲里最合適的一種，所用的碰撞也是最簡單的。基本上用矩形檢測可以解決全部碰撞測試。

子彈的碰撞體一個矩形解決問題，機體和複雜一些的形狀用組合矩形解決問題。矩形萬歲。

上個月正好在公司花兩天做了個彈幕遊戲的demo。彈幕碰撞主要是將敵人和自己的子彈區分開，分別存入兩個網格對象中。網格對象持有一個二維數組（當然一維數組也可以），數組的長度為（屏幕長度/單個網格的長度 * 屏幕高度/單個網格的高度）。效果如下圖：

數組用於存放處在該網格中的所有子彈。假設屏幕為480*800，我們選定網格為80*80，則共有480/80*800/80=60個網格，我們指定有斜線的網格對應數組[0][0]。接下來根據子彈的位置將其加入到數組中。公式如下：

row = math.floor(子彈Y軸位置/網格高度）

col = math.floor(子彈X軸位置/網格長度）

比如子彈位置為（100，200），則將其加入到數組中的[1][2]中，在子彈位置發生改變同時更新其在數組中的位置。需要與網格對象中的子彈進行檢測的飛機以同樣的方法計算出（col，row），則只需與數組[col][row]中的子彈進行碰撞檢測即可。

不知道有沒有說清楚……

好像還沒怎麼特別在意過這個問題，現代遊戲引擎做這種普遍壓力不大

我是用unity，可以從unity這個角度聊聊，其他引擎就沒那麼清楚

Unity是二維三維都支持的遊戲引擎

三維的話基本使用三維碰撞體（很多射擊遊戲會用raycast做射線判斷，那種情況一般忽略子彈的速度，彈幕應該不適合）

所以一般就是普通的collider,三維物體的碰撞，那比較重要的應該是子彈之間無碰撞，而僅僅與目標物體如敵人或主角，（因為如果大量子彈相互碰撞的話，很多會在短時間出現複數級別的碰撞，雖然引擎也不是不能承受，但是總會有些意外情況）

所以一般會把子彈和敵人自己分層分開，設定層之間的碰撞，這樣或者自身子彈可以擊毀敵人的子彈之類的判定也就可以做。

unity創建大量物體的瞬間，是有可能卡斷的，另外還有就是子彈不會永遠存在，要有出屏幕的銷毀機制，unity下面會做pool,也就是一個子彈設定它的最多出現的上限，那開機的時候就創建了這麼多子彈出來，只不過都隱藏起來，如果被創建就顯示一個子彈到相應的位置，這樣不會導致遊戲的性能下降。

如果是用2d的演算法，會更快一些，但是思路也大抵是一樣，那如果要做什麼子彈彈回的立場，時間壓縮等等的特效也都很簡單，。

補充，另外還有一種情況，比如說射線類武器，那就是穿過所有的物體，這種情況，可以考慮用raycast。

個人覺得：

以前的街機遊戲顯然沒有做碰撞測試也不需要做碰撞測試。它所做的只是一個調色盤中的像素色彩對比而已。

其實彈幕遊戲沒那麼麻煩，一個一個比就好了。

敵人的子彈只要和player算一次，而player發出的子彈一點都不多，和每個敵人算也沒關係......

然後一般碰撞用矩形或者圓作為hitbox即可......

@Milo Yip大大已經高屋建瓴得說明該問題屬於空間劃分，已有N多NB論文等著你。 @施展童鞋給出的實現方案已經很細節了，我之前的項目也採用了類似方案。說說我自己的實現細節吧。

曾經也開發過一款2D橫版彈幕端游。一般彈幕遊戲的子彈都會有矩形碰撞框讓策劃配置（不會只是一個質點），以實現不同大小或多種組合的物體。

比如這種常規的

還有這種長條的

所以可以把問題抽象成如何在網格數組中快速判定矩形相交，當然我們前提是矩形數量眾多，否則O(N^2)枚舉就行，就不用上網格了。

按矩形大小塞入不同網格，如橙色的矩形塞入[0][0],[0][1],[1][0],[1][1] 4個網格中
對每個矩形，遍歷其所覆蓋的網格，將每個格子的矩形放進set中進行去重
從set中去掉本體矩形，對set中剩下的所有矩形進行碰撞檢測

個人經驗以供參考：

網格處理方式簡單，效率一般情況下比四叉樹好
網格大小很重要，過小的話大矩形會被分割的過細，過大的話單個網格內有太多待判定矩形

先保存，後面再補~

東方project似乎是用圓做hitbox。

因為橢圓彈、箭彈、符札都是圓形判定。

用像素碰撞才能真正重現街機的打機感