游戲中對象選取的方法

對于PC游戲，在鼠標大行其道的今天，如何由鼠標的位置判定其下的對象是什么，是幾乎所有游戲都必須面對的問題。

以下提供幾種方法，僅供參考。

1、包圍框法：
　　一般的，對游戲中的每個對象創建一個伴隨的包圍框，通過遍歷所有可見對象，判定鼠標坐標點是否落在某個包圍框的內部來獲取其選取的對象。這種方法的優點是簡單，算法容易理解，當使用矩形包圍框，而對象數量又比較有限的時候，效率也是很好的。缺點是選取不夠精確，無法對對象的細節做選取。在2D游戲中，包圍框一般是矩形，或者是若干個矩形的組合，而3D游戲使用包圍盒，或者包圍球或其組合等方式。無論具體方式如何，其算法實質都是一樣的。

2、枚舉法：
　　效率最低的方法之一。和1，包圍框法類似，它也需要遍歷所有可見對象，但是由于缺少包圍盒機制，只能檢測對象位于鼠標下的那個位置是否有有效象素，或者有效的alpha值，對3D對象而言，就是檢查鼠標點形成的選取射線是否穿越對象的某個面片。這種方法可以實現很精確的選取，但是由于效率太低，所以很少直接使用，一般先使用方法1減少遍歷對象的數量之后，再使用這個方法達到精確的選取。

3、反饋法：
　　這是一個很有效，也很快捷的方法，尤其在3D游戲中，有無可比擬的優越性。反饋法的實現很簡單，首先要維護一個后臺緩沖區，當繪制目標對象的時候，同時將對象的可見信息(一般是對象圖片的Alpha值，或者Z值) 寫入后臺緩沖，然后檢測鼠標對應的緩沖區的位置的值是否有變化，如果變化了，表明剛才繪制的對象可以被鼠標選中。當緩沖使用了復雜一些的Z運算的時候，我們在繪制完成之后，就可以得到一個鼠標可以選取的對象列表，然后只要簡單的根據一定的原則從這個列表中提取需要的對象就可以了。這個機制在2D下，一般不維護額外的緩沖區而直接使用繪圖緩沖區。3D下，像OpenGL提供了內置的反饋方法，更方便了用戶的使用。實際也可以利用Z buffer，模板緩沖等實現類似的機制。這種方法可以實現精確到象素級的選取，而幾乎不影響運行效率。缺點是需要對繪制部分的代碼有很高的控制權限。

4、直接映射法：
　　這也是一個高效算法，可以達到O(1)的時間復雜度。常見于2D戰棋類游戲中。在這類游戲中，場景是用一個二維表存儲的，表的每個項，保存著它上面的對象信息，我們可以通過一個簡單的算法，由當前的鼠標位置得到表的索引，然后直接讀取索引對應的項就完成了選取。在固定視角的3D游戲甚至非固定視角的3D游戲中，也可以使用這種方法。這種方法的缺點是對象在場景中，只能是按二維表，或者多層二維表排布的。這種方法對內存空間的需求也比較大。棋牌類游戲比較適合使用這種方法。

　　由于每種方法都有其固有的優缺點，而對游戲而言，場景又千變萬化，復雜紛繁。為了能適應實際的需求，上面的方法可以組合使用，從而揚長避短，更好的達成需求。其他一些復雜的選取，比如范圍選取(框選)等，也可以由以上幾種基本的方法演化而來。

原文轉自：http://www.anti-gravitydesign.com