如何使Processing.org草图更高效？

Question

我有一个简单的草图（在Processing），基本上有一堆点在四处游荡，如果他们接触到对方，他们会打（每个人都有一个实力值，每次赢时增加，如果相等，赢家是随机的选择）

它适用于约5000个12像素的“僵尸”（有一个半秒的轻微减速，而僵尸最初相互碰撞），问题是当僵尸变得更小，他们不要相互碰撞，并且减速时间可以更长。

代码非常简单 - 基本上每个僵尸都是一个类，它有一个X/Y坐标。每帧所有的僵尸都会轻推一个像素，随机转动lurching度（或不）。我认为缓慢的最大原因是碰撞检测 - 每个僵尸检查每隔一个（所以僵尸1检查2-5000，僵尸2检查1,3-5000等。）

我想保留所有内容简单，“简单处理”（不使用外部库，这可能是更有效，更容易，但我不觉得学习是非常有用的）

int numZombies = 5000; 

Zombie[] zombies = new Zombie[numZombies]; 

void setup(){ 
    size(512, 512); 
    noStroke(); 
    for(int i = 0; i < numZombies; i++){ 
    zombies[i] = new Zombie(i, random(width), random(height), random(360), zombies); 
    } 
} 

void draw(){ 
    background(0); 

    for(int i = 0; i < numZombies; i++){ 
    zombies[i].move(); 
    zombies[i].display(); 
    } 
} 

class Zombie{ 
    int id; // the index of this zombie 

    float x, y; // current location 
    float angle; // angle of zombies movement 
    float lurching = 10; // Amount angle can change 
    float strength = 2; 

    boolean dead = false; // true means zombie is dead 

    float diameter = 12; // How big the zombie is 
    float velocity = 1.0; // How fast zombie moves 

    Zombie[] others; // Stores the other zombies 

    Zombie(int inid, float xin, float yin, float inangle, Zombie[] oin){ 
    id = inid; 
    x = xin; 
    y = yin; 
    angle = inangle; 
    others = oin; 
    } 

    void move(){ 
    if(dead) return; 

    float vx = velocity * sin(radians(180-angle)); 
    float vy = velocity * cos(radians(180-angle)); 

    x = x + vx; 
    y = y + vy; 

    if(x + vx < 0 || x + vx > width || y + vy < 0 || y + vy > height){ 
     // Collided with wall 
     angle = angle + 180; 
    } 

    float adecide = random(3); 

    if(adecide < 1){ 
     // Move left 
     angle=angle - lurching; 
    } 
    else if(adecide > 1 && adecide < 2){ 
     // Don't move x 
    } 
    else if(adecide > 2){ 
     // Move right 
     angle = angle + lurching; 
    } 

    checkFights(); 
    } 

    void checkFights(){ 
    for (int i=0; i < numZombies; i++) { 
     if (i == id || dead || others[i].dead){ 
     continue; 
     } 

     float dx = others[i].x - x; 
     float dy = others[i].y - y; 
     float distance = sqrt(dx*dx + dy*dy); 

     if (distance < diameter){ 
     fight(i); 
     } 
    } 
    } 

    void fight(int oid){ 
    Zombie o = others[oid]; 

    //println("Zombie " + id + "(s: "+ strength +") fighting " + oid + "(s: "+ o.strength +")"); 

    if(strength < o.strength){ 
     kill(); 
     o.strength++; 
    } 
    else if (strength == o.strength){ 
     if(random(1) > 0.5){ 
     kill(); 
     o.strength++; 
     } 
     else{ 
     o.kill(); 
     strength++; 
     } 
    } 
    } 

    void kill(){ 
    dead = true; 
    } 

    void display(){ 
    if(dead) return; 
    ellipse(x, y, diameter, diameter); 
    } 
} 

Answer 1

像1800信息说，不知何故，你需要减少比较的数量。

将游戏区域拆分为区域是个不错的主意。我可以想象，将当前位置与区域边界进行比较并从相应集合中添加/移除僵尸是值得的。假设他们通常会直线前进，他们不应该太频繁地改变区域。

虽然区域之间可能发生碰撞，但我们遇到了问题。为了搭载这个想法，你可以将屏幕分成4个区域，然后再分成9个区域。想想一个叠加在十字架上的井字趾板。这是一个糟糕的绘图，但：

| ! | 
    | ! | 
----+--!-+---- 
    | ! | 
====|==x=|==== 
----+--!-+---- 
    | ! | 
    | ! | 

这样每个僵尸是两个区域在一次在一个方案中的每个边界由另一个区域覆盖。你甚至不必再次检查所有相同的僵尸，因为我们会死的或者他们会。所以唯一的双重处理是单一的others[i].dead检查。

---

我可以很快地看到另一件事是你还是遍历元素的其余部分，即使你死定了：

if (i == id || dead || others[i].dead){ 
    continue; 
    } 

它可能不是节省大量的处理，但它肯定能如果你：

if (dead) return; 

改为。

---

另外作为一个附注，你想检查直径或距离的距离吗？

Answer 2

也许你应该拆了比赛场地成区只能检查同一区域内的僵尸之间的碰撞。您需要减少比较次数。

Answer 3

你得到了自己O(n^2)的复杂性，这就是你的算法。每个移动的僵尸必须与所有其他人一起检查是否正确，如果它们发生相互碰撞会使你产生二次复杂性。

一个方向可能是创建一个表示屏幕的矩阵，而不是迭代所有其他僵尸，只需更新当前僵尸在矩阵上的位置，然后检查另一个僵尸是否已经占用了同一个单元。

Answer 4

这让我想起了这条线索：No idea what could be the problem!!。和collision detection help我指出维基百科的碰撞检测文章。
Quadtrees似乎经常用于2D分区。

Answer 5

您的基本碰撞检测算法具有复杂度为O（n^2）。

您需要一些方法来减少比较次数。

已经提到的一种方法是将游戏区域划分成区域/区域，并且 仅在僵尸处于相同区域/区域时检查碰撞。这是尝试 拓扑排序实体（按距离）。你想要的是将这些僵尸分开，而不仅仅是通过地理区分，而是对它们进行排序，以便只在 彼此“接近”时才进行比较。你想忽略空白区域。

考虑您所在地区的树形结构。当一个地区的僵尸数量超过某个数量时，可以将区域分割得更小，直到区域半径接近您的碰撞距离。使用地图查找区域，并检查给定区域中的所有僵尸（以及任何“足够靠近”的区域）。

你可能想ň是< =的log（n）...