如何使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）...