이 Processing.org를 더 효율적으로 만들 수 있습니까?

StackOverflow https://stackoverflow.com/questions/419577

  •  03-07-2019
  •  | 
  •  

문제

간단한 스케치가 있습니다 (in 처리), 기본적으로 많은 점들이 돌아 다니며, 서로 접촉하면 싸우면 (각각의 힘을 가졌으며, 승리 할 때마다 증가합니다. 승자가 무작위로 선택됩니다).

그것은 약 5000 12 픽셀 "좀비"와 잘 어울립니다 (30 초 동안 약간의 속도가 약간 느려지고 좀비는 처음에는 서로 충돌합니다), 문제는 좀비가 작게 만들 때 각각 충돌하지 않습니다. 기타 빠르고 둔화는 훨씬 더 오래 지속될 수 있습니다 ..

코드는 정말 간단합니다. 기본적으로 각 좀비는 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);
  }
}
도움이 되었습니까?

해결책

1800 정보에 따르면, 어떻게 든 비교 횟수를 줄여야합니다.

연주 영역을 구역으로 나누는 것이 좋습니다. 현재 위치를 영역 경계와 비교하고 적절한 컬렉션에서 좀비를 추가/제거하는 데 걸리는 시간이 그만한 가치가 있다고 생각합니다. 그들이 일반적으로 직선으로 갈 것이라고 가정하면, 구역을 너무 자주 바꾸어서는 안됩니다.

구역 간의 충돌 가능성이 있지만 문제가 있습니다. 이 아이디어를 피기 백하려면 화면을 4 개의 영역으로 나누고 9 구역으로 다시 나눌 수 있습니다. 십자가에 오버레이 된 Tic-Tac-Toe 보드를 생각하십시오. 이것은 나쁜 그림이지만 :

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

이런 식으로 각 좀비는 한 번에 두 구역에 있으며 한 가지 계획의 모든 테두리는 다른 영역으로 덮여 있습니다. 우리가 죽었거나 그들이 원했기 때문에 같은 좀비를 다시 확인할 필요조차 없습니다. 따라서 유일한 이중 처리는 단일입니다 others[i].dead 확인하다.

내가 빨리 볼 수있는 또 다른 것은 당신이 죽었더라도 나머지 요소들을 계속 통과한다는 것입니다.

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

많은 처리를 저장하지는 않지만 다음과 같은 경우 몇 가지 지침을 잘라낼 수 있습니다.

  if (dead) return;

대신에.

또한 부수적으로, 거리에 대한 직경이나 반경을 확인하고 싶습니까?

다른 팁

당신은 스스로를 얻었습니다 O(n^2) 복잡성, 그리고 그것은 당신의 알고리즘을 죽이고 있습니다. 움직이는 각 좀비가 충돌하면 다른 모든 좀비가 2 차 복잡성으로 데려 오는 것이 맞습니다.

한 방향은 화면을 나타내는 매트릭스를 만들고 다른 모든 좀비를 반복하는 대신 매트릭스의 현재 좀비 위치를 업데이트하고 다른 좀비가 이미 동일한 셀을 차지하고 있는지 확인하는 것입니다.

기본 충돌 감지 알고리즘이 있습니다 o (n^2) 복잡성.

비교 횟수를 줄일 수있는 접근 방식이 필요합니다.

이미 언급 한 한 가지 방법은 경기장을 구역/지역으로 나누고 좀비가 같은 영역/지역에있을 때만 충돌을 확인하는 것입니다. 이것은 엔티티를 토폴로지 (거리별로) 분류하려는 시도입니다. 당신이 원하는 것은이 좀비를 단순히 지리로가 아니라 서로 '가까운'때만 비교할 수 있도록 분류하는 것입니다. 그리고 당신은 빈 지역을 무시하고 싶습니다.

지역에 대한 나무 구조를 고려하십시오. 지역에 숫자 이상이있을 때 N 좀비의 경우, 지역 반경이 충돌 거리에 접근 할 때까지 영역을 더 작게 분할 할 수 있습니다. 지도를 사용하여 조회 영역을 사용하고 주어진 지역의 모든 좀비 (및 '충분히 가까운'지역)를 확인하십시오.

당신은 아마 원할 것입니다 N <= log (n) ...

어쩌면 경기장을 구역으로 나누고 같은 영역에있는 좀비 사이의 충돌 만 확인해야 할 수도 있습니다. 비교 수를 줄여야합니다.

이 스레드를 생각 나게합니다. 문제가 무엇인지 전혀 모른다 !!. 그리고 충돌 감지 도움말 여기서 Wikipedia의 충돌 감지 기사를 가리 킵니다.
쿼드 트리 2D 파티셔닝에 종종 사용되는 것 같습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top