كيف يمكنني جعل مخطط Processing.org هذا أكثر كفاءة؟

Question

لدي رسم بسيط (في يعالج)، في الأساس مجموعة من النقاط تتجول، إذا تلامست مع بعضها البعض فإنها تتقاتل (لكل منها قيمة قوة، تزداد في كل مرة يفوزون فيها، وإذا كانت متساوية يتم اختيار الفائز عشوائيًا)

إنه يعمل بشكل جيد مع حوالي 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

وأنت حصلت على نفسك تعقيد O(n^2)، وهذا ما ادى الى مقتل الخوارزمية الخاصة بك. انها صحيحة أن كل غيبوبة يتحرك لها أن تحقق مع كل الآخرين إذا ما اصطدمت التي تأتيك إلى تعقيد الدرجة الثانية.

ويمكن أن تكون ذات اتجاه واحد لإنشاء مصفوفة تمثل الشاشة، وبدلا من بالتكرار عبر كل الكسالى أخرى، ببساطة تحديث موقع غيبوبة الحالية على مصفوفة، والتحقق من هناك إذا غيبوبة آخر يحتل بالفعل أن نفس الخلية.

Answer 3

لديك خوارزمية الكشف عن الاصطدام الأساسية يا (ن ^ 2) تعقيد.

أنت بحاجة إلى بعض الأساليب التي من شأنها تقليل عدد المقارنات.

أحد الأساليب المذكورة سابقًا ، هي تقسيم ملعب الملعب إلى مناطق/مناطق ، والتحقق فقط من الاصطدام عندما يكون الزومبي في نفس المنطقة/المنطقة.هذه محاولة لفرز الكيانات من الناحية الطوبولوجية (عن طريق المسافة).ما تريده هو فصل هذه الزومبي ليس ببساطة عن طريق الجغرافيا ، ولكن لفرزها بحيث تتم مقارنتها فقط عندما تكون "قريبة" من بعضها البعض.وتريد تجاهل المناطق الفارغة.

النظر في هيكل شجرة لمناطقك.عندما تحتوي المنطقة على أكثر من رقم ما ن من الزومبي، يمكنك تقسيم المنطقة إلى أجزاء أصغر، حتى يقترب نصف قطر المنطقة من مسافة الاصطدام.استخدم خريطة للبحث عن المنطقة، وتحقق من جميع الزومبي في منطقة معينة (وأي منطقة "قريبة بدرجة كافية").

ربما تريد ن أن تكون <= سجل (ن) ...

Answer 4

وربما يجب عليك تقسيم الملعب تصل إلى مناطق وتحقق فقط عن اصطدام بين الكسالى التي هي في نفس المنطقة. تحتاج إلى تقليل عدد المقارنات.

Answer 5

وهذا يذكرني هذا الموضوع: <لأ href = "http://processing.org/discourse/yabb_beta/YaBB.cgi؟board=Syntax؛action=display؛num=1221446441" يختلط = "نوفولو noreferrer" عنوان = "معالجة 1.0 - أي فكرة عما يمكن أن يكون مشكلة !!"> أي فكرة عما يمكن أن يكون مشكلة !! . و <لأ href = "http://processing.org/discourse/yabb_beta/YaBB.cgi؟board=Programs؛action=display؛num=1230698202" يختلط = "نوفولو noreferrer" عنوان = "معالجة 1.0 - اصطدام كشف المساعدة" > اصطدام كشف المساعدة حيث أشير إلى المادة كشف التصادم ويكيبيديا.
مجانا يبدو ليتم غالبا ما تستخدم ل2D التقسيم .