Android遊戲開發：使用哪種數據結構？

Question

我正在製作Android遊戲。我有點試圖保持遊戲的祕密，所以我不能透露太多，所以請耐心等待。基本上它是實時運行的（所以我將實現一個線程來更新對象的座標），它的風格有點像Duck Hunt;你必須擊中在屏幕上移動的物體。但是，遊戲一直在稍微滯後（運行在三星Galaxy S上，這是高端設備之一），所以我相信我需要使用更好的數據結構。

基本上我將這些對象存儲在雙向鏈表中而不是數組中，因爲我希望屏幕上的對象的最大數量是動態的。換句話說，我有一個頭部和尾部對象的引用，並且所有的遊戲對象都像典型的鏈表一樣連接。這提供了以下問題：

1. 搜索如果一個對象與交叉的給定座標（通過觸摸屏幕）需要O（n）的時間（最壞的情況下），因爲我有從頭部到遍歷到尾，並檢查每個對象的hitbox。
2. 兩個對象之間的碰撞檢查需要O（n^2）個時間（再次，最壞的情況），因爲對於每個對象我都要檢查它的hitbox是否與鏈表中所有其他對象相交。

我選擇鏈表的另一個原因是我基本上有兩個鏈表：一個用於活動對象（即屏幕上的對象）和一個用於非活動對象。假設遊戲畫面上最多有8個對象，如果活動鏈表有5個對象，非活動列表將有3個對象。使用兩個鏈表可以使對象變爲非活動狀態時，我可以簡單地將它附加到不活動鏈表上，而不是取消引用它，並等待垃圾回收器回收內存。另外，如果我需要一個新對象，我可以簡單地從非活動鏈接列表中取出一個對象，並將其用於活動鏈接列表中，而不必分配更多內存來創建新對象。我已考慮使用多維數組。這種方法涉及將屏幕劃分爲對象可以躺下的「單元格」。例如，在一個480x800的屏幕上，如果對象的高度和寬度都是80像素，我會將屏幕分成6x10個網格，或者在Java代碼的上下文中，我會製作GameObject [6] [10]。我可以簡單地將對象的座標（在屏幕上）除以80以得到它的索引（在網格上），這也可以提供O（1）插入。這也可以通過座標O（1）進行搜索，因爲我可以用觸摸座標執行相同的操作來檢查相應的索引。

碰撞檢查可能仍然需要O（n^2）時間，因爲我仍然需要經過網格中的每個單元格（儘管這樣我只需要比較最多與我相鄰的8個單元格目前正在檢查）。

但是，網格的想法提出了自己的問題：

1. 如果屏幕比其他480x800的分辨率？另外，如果網格不能均勻分成6x10？這可能會使程序更容易出錯。
2. 正在使用內存方面昂貴的遊戲對象的網格？考慮到我正在爲移動設備開發，我需要考慮這一點。

所以最終的問題是：我應該使用鏈表，多維數組還是其他我沒有考慮過的東西？

下面是我如何實現碰撞的想法：

更好的碰撞檢測性能

private void checkForAllCollisions() { 
GameObject obj1 = mHead; 

while (obj1 != null) { 
     GameObject obj2 = obj1.getNext(); 
      while (obj2 != null) { 
       //getHitBox() returns a Rect object that encompasses the object 
       Rect.intersects(obj1.getHitBox(), obj2.getHitBox()); 
       //Some collision logic 
      } 
      obj1 = obj1.getNext(); 
     } 
} 

Answer 1

常見的數據結構quadtrees（2維）和octrees（3名維）。

如果你想堅持一個列表 - 是否有一個原因，你使用LinkedList而不是ArrayList？我希望你目前正在使用內置的鏈表實現...

---

一個三星Galaxy S擁有512 MB的RAM - 不用擔心佔用太多的內存，一個單一的數據結構（然而）。在這個數據結構開始吸取大量內存之前，您必須擁有相對較多的相對較重的對象。即使您有1000 GameObject實例，並且數據結構中的每個實例（包括在所述數據結構中存儲實例的相關權重）都是10,000字節（這非常大）仍然只有9.5兆內存。

Answer 2

所以我絕對認爲我們需要首先考慮一些事情。

1）LL與陣列

你說，你使用的LL不是數組的，因爲動態屬性LL給你的。然而，我想說，你可以使用一個足夠動態的數組，它的大小已經填滿了，這會給你O（1）運行時插入amortized（假設數組正在被解除/未分類）。但是，會出現這樣一種情況，即每隔一段時間插入一次就可以使用O（n），因爲您必須適當地複製數據。所以，對於這樣的現場比賽，我相信LL是個不錯的選擇。

2.）你考慮遊戲對象的記憶。

這在很大程度上取決於每個GameObject的結構，您尚未提供足夠的詳細信息。如果每個GameObject只包含幾個int或原始類型，那麼很可能你可以負擔得起內存。如果每個GameObject的內存非常昂貴並且使用的是非常大的網格，那麼它肯定會花費大量的內存，但它將取決於每個GameObject的內存使用情況以及網格的大小。

3.）如果分辨率與480x800不同，請不要擔心。如果您正在使用適用於所有的6×10格，可以考慮使用密度倍增，像這樣：

float scale = getContext().getResources().getDisplayMetrics().density; 

，然後的getWidth（）和getHeight（）應該由這個規模相乘得到設備的確切寬度和高度這是使用你的應用程序。然後，您可以將這些數字除以6和10.但是請注意，某些設備上的某些網格可能看起來很醜，即使這些網格按照這種方式正確縮放。

4）衝突處理

你提到你在做碰撞處理。儘管我不能說在你的情況下哪種處理方法是最好的（我仍然有點困惑，你是如何根據你的問題來做這件事的），請記住這些替代方案：

a。） b。）Separate Chaining 角）Double Hashing

這些都是無可否認的哈希衝突處理策略，但鑑於你的遊戲（同樣，你會更瞭解，因爲你已經保存了一些信息回可能實現的）。不過，我會說，如果你使用網格，你可能想要沿着線性探測的方向做一些事情，或者一起創建2個哈希表（如果合適的話），但是這似乎取消了你想要的網格佈局實現，所以，再一次，你的自由裁量權）。另外請注意，您可以使用某種樹（如四叉樹）來獲得更快的碰撞檢測。如果你不知道四叉樹，請查看here。一種好的方法是將葉片上的方形圖像分割成單獨的像素，並在pruning的父節點處存儲平均顏色。只是幫助您有意識地考慮四叉樹的一種方法。

希望有所幫助。再一次，也許我誤解了一些問題，因爲你的問題含糊不清，請告訴我。我很樂意提供幫助。