使用边界框慢速碰撞检测

Question

我有一个小型图书馆，我想用它来创建游戏。首先，我试图实现像素完美的碰撞检测，但是这样做并不顺利，所以我决定使用简单的边界框碰撞检测。它可以正常工作，但是在物体数量超过20个左右后，它开始放慢速度。这里是我的代码： （以循环方式运行，每秒25次）BorderBox类的

for (int i=0;i<sc.collGr.size();i++){ 
    CollisionGroup gr=sc.collGr.get(i); 
    Collidable[] cc=gr.getCollidables(); 
    for (int l=0;l<cc.length;l++){ 
     for (int w=l+1;w<cc.length;w++){ 
      if (BorderBox.areColliding(cc[l].getBorderBox(), cc[w].getBorderBox()){ 
       addEventToHandler(sc.collGr.get(i),cc[l],cc[w]); 
      } 
     } 
    } 
} 

部分：

public class BorderBox { 
int top; 
int down; 
int left; 
int right; 

/** 
* Creates new BorderBox object 
* Arguments: (top, down, left, right); 
* */ 
public BorderBox(int topy,int downy, int leftx,int rightx){ 
    top=topy; 
    down=downy; 
    left=leftx; 
    right=rightx; 
} 

/** 
* Checks if two provided BorderBoxes are colliding. 
* */ 
public static boolean areColliding(BorderBox a,BorderBox b){ 
    if (b.left<=a.right && b.right>=a.left && b.down>=a.top && b.top<=a.down){ 
     return true; 
    } 
    return false; 
} 

Answer 1

检查这种方式是O(n^2)操作。也就是说，当你添加一个新的对象时，你正在做的工作量增加了二次方。

我之前缓解这种情况的方式与其他建议一样，是在两个不同的数组中有两种类型的可碰撞对象。一个数组有少量的对象，主要是角色，另一个数组有敌人。这个想法是，你不关心敌人彼此碰撞。因此，你大大减少你所要做的工作量，仅如果从更小的数组元素与较大的一个元素碰撞检查。

这当然是游戏的特殊，如果一切拥有一切碰撞无法工作。尽管如此，我发现简单的游戏往往不是这种情况。

Answer 2

分配你的空间，以避免检查远分开的对象碰撞。根据你的游戏，一个简单的网格可以使用像kd-Trees这样的更有趣的东西。我曾经做过一个有实际房间的游戏，我只是检查同一房间内的物体之间的碰撞（假设房间比对象更少，或者更新哪个对象在哪个房间中很容易）。