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的父节点处存储平均颜色。只是帮助您有意识地考虑四叉树的一种方法。

希望有所帮助。再一次，也许我误解了一些问题，因为你的问题含糊不清，请告诉我。我很乐意提供帮助。