Как я могу сделать этот 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

Ваш основной алгоритм обнаружения столкновений имеет сложность O (n ^ 2) .

Вам нужен какой-то подход, который уменьшит количество сравнений.

Один из подходов, уже упомянутых, заключается в разделении игрового поля на зоны / регионы и проверять столкновение только в том случае, если зомби находится в той же зоне / регионе. Это попытка сортировать объекты топологически (по расстоянию). То, что вы хотите, это отделить эти зомби не просто по географии, но и сортировать их так, чтобы они сравнивались только тогда, когда они «близки» друг к другу. И вы хотите игнорировать пустые регионы.

Рассмотрите древовидную структуру для ваших регионов. Когда в регионе больше чем несколько N зомби, вы можете разделить регион на меньшее, пока радиус региона не приблизится к расстоянию столкновения. Используйте карту для поиска региона и проверьте всех зомби в данном регионе (и любой «достаточно близкий» регион).

Возможно, вы хотите, чтобы N было < = log (n) ...

Answer 4

Возможно, вам следует разбить игровое поле на зоны и проверять только столкновения между зомби, которые находятся в одной зоне. Вам нужно уменьшить количество сравнений.

Answer 5

Это напоминает мне эту тему: Не знаю, в чем может быть проблема !! . И справка по обнаружению столкновений , где я указываю на статью по обнаружению столкновений в Википедии.
Quadtrees , кажется, часто используется для 2D-разбиения .