충돌 감지 - 모든 언어

Question

지금은 간단한 게임을 작성하고 있으며 많은 오브젝트 사이의 충돌을 감지 할 수 있어야합니다 (10 개의 오브젝트가 20 개의 다른 오브젝트와 충돌하지만 두 그룹 사이에는 충돌이 없는지 확인).

 //Check for collisions between tanks and bullets 
     ArrayList<Object> objectsToRemove = new ArrayList<Object>(); 
     for (int i = 0; i < tanksOnScreen.size(); i += 1) { 
      //Get tank 
      Tank tank = tanksOnScreen.get(i); 

      for (int e = 0; e < bulletsOnScreen.size(); e += 1) { 
       //Get bullet 
       Bullet bullet = bulletsOnScreen.get(e); 

       //Check for collision 
       if (tank.collides(bullet.x, bullet.y, 10, 10)) { 
        System.out.println("Collide"); 
        objectsToRemove.add(bullet); 
        objectsToRemove.add(tank); 
        break; 
       } 
      } 
     } 

     for (Object obj:objectsToRemove) { 
      if (obj.getClass().equals(Bullet.class)) { 
       bulletsOnScreen.remove(bulletsOnScreen.indexOf(obj)); 
      } else if (obj.getClass().equals(Tank.class)) { 
       tanksOnScreen.remove(tanksOnScreen.indexOf(obj)); 
      } 
     } 

그리고 탱크의 collides() 방법 :

public boolean collides(float px, float py, float pwidth, float pheight) { 
    // If the distance between the two centers of the lines on x and y axis 
    // Is less than the distance of half the w and h added together, the objects 
    // Are colliding 
    float x1 = (px > x) ? x : px, x2 = (px > x) ? px : x, y1 = (py > y) ? y : py, y2 = (py > y) ? py : y; 
    float w1 = (x1 < x2) ? width : pwidth, w2 = (x1 < x2) ? pwidth : width, h1 = (y1 < y2) ? height : pheight, h2 = (y1 < y2) ? pheight : height; 
    if ((x2 + w2/2) - (x1 + w1/2) < (w1/2 + w2/2)&&(y2 + h2/2) - (y1 + h1/2) < (h1/2 + h2/2)) { 
     return true; 
    } else { 
     return false; 
    } 
} 

을 지금은 작동하지만 내가 (그런데 자바) 충돌을 감지 매우 후에 천천히 경기를 일으키는 몇 가지 간단한 코드를 작성했습니다

지연이 객체 위로 반복하기 위해 double for 루프 때문에 있다고 가정합니다. 나는 루프를 위해 이들을 근절하는 방법이나 화면의 특정 영역에서 총알을 얻는 방법을 잘 모르며 루프를 위해 다른 것을 사용하지 않고이 총알을 확인하는 것만합니다 (분리라고 생각합니다). 누구든지 여러 객체를 사용하여 충돌 탐지를 위해 올바른 방향으로 나를 안내 할 수 있습니까? 의사 코드 일지라도 그 대답이 어떤 언어인지는 신경 쓰지 않습니다.

감사합니다,

벤

편집 한

내가 지금 업데이 트를 제공 자바에 대한 슬릭 그래픽 API를 사용하여 및 방법을 렌더링하고있어 렌더링 및 게임 추가 논리. 나는이 충돌 탐지를 update 메소드에 두었다. (이것은 매 프레임마다 약 60 회 호출된다.) 속도 저하는 충돌이 발생한 후 발생하며 개체가 화면에서 제거됩니다. for 루프에서 객체를 삭제 한 후 break 명령을 사용하면 해당 객체가 제거됩니다.

편집 2

모든 해답들에 대한 감사 및 참조는 미래를위한 큰 도움이됩니다. 나는 총알과 탱크에 루프를 교환하는 것만으로 문제를 해결 했으므로 총알이 파괴 된 후에도 반복되지 않았다. 결국 문제를 해결하기가 쉽기 때문에 질문하지 말았어야했습니다. Dave와 Banthar는 문제가 코드와 관련이 없으며 즉시 발생해야한다고 말하면서 옳았습니다.

Answer 1

모든 답변을 주셔서 감사합니다. 참고 문헌은 향후 큰 도움이됩니다. 나는 총알과 탱크에 루프를 교환하는 것만으로 문제를 해결 했으므로 총알이 파괴 된 후에도 반복되지 않았다.결국 문제를 해결하기가 쉽기 때문에 질문하지 말았어야했습니다. Dave와 Banthar는 문제가 코드와 관련이 없으며 즉시 발생해야한다고 말하면서 옳았습니다.

Answer 2

좋은 아이디어 중 하나는 octree입니다. 총알이 움직이면서 나는 당신이 그것의 운동 버전을 필요로한다고 가정한다 - 인터넷상의 운동 학적 자료 구조에 관한 많은 기사들이있다.

더 복잡한 볼록 다각형 사이의 충돌을 감지하려면이 계산을 위해 매우 빠른 gjk 알고리즘을 사용하는 것이 좋습니다. 이렇게하면 한 쌍의 오브젝트에 대한 충돌 감지 시간 만 가속화되며 쌍 수는 여전히 동일하게 유지됩니다.

Answer 3

내가 뭔가를 놓치지 않았거나 표시하지 않은 추가 코드가 없다면 O (n^2)로 실행됩니다. 여기서 n은 20입니다. 사용자에게는 즉각적으로 보일 것입니다.

디버거에서 단계별로 시도해 속도가 느려지는지 확인합니다.

정교하게 편집하십시오. 비싼 조작은 게시 한 코드에 없습니다. 그것은 당신이 게시 한 코드에 의해 호출되는 다른 곳입니다.