GN⁺: 정렬, 스윕, 가지치기: Collision Detection Algorithms (2023)

충돌 감지 알고리듬

충돌 감지

• 비디오 게임 프로그래밍에서 충돌 감지는 매우 일반적인 문제임
• 캐릭터가 서로 통과하지 못하게 하거나, 물리 엔진을 구현하는 데 필수적임

단순한 접근법 🐥

• 모든 객체 쌍을 검사하여 충돌 여부를 확인하는 방법
• 코드 예시:

  for (let i = 0; i < balls.length; i++) {
    const ball1 = balls[i];
    for (let j = i + 1; j < balls.length; j++) {
      const ball2 = balls[j];
      if (intersects(ball1, ball2)) {
        bounce(ball1, ball2);
      }
    }
  }
  

• 이 방법은 O(n^2) 시간 복잡도를 가짐

성능 문제

• 객체 수가 많아질수록 성능 문제가 발생함
• 예를 들어, n = 20일 때 190개의 쌍을 검사해야 함

해결책 개선

• 불필요한 작업을 줄이는 것이 중요함
• intersects() 함수 최적화:

  function intersects(object1, object2) {
    return object1.left < object2.right &&
           object1.right > object2.left &&
           object1.top < object2.bottom &&
           object1.bottom > object2.top;
  }
  

정렬을 통한 최적화

• 객체를 x 좌표에 따라 정렬하면 불필요한 검사를 줄일 수 있음
• 코드 예시:

  sortByLeft(balls);
  for (let i = 0; i < balls.length; i++) {
    const ball1 = balls[i];
    for (let j = i + 1; j < balls.length; j++) {
      const ball2 = balls[j];
      if (ball2.left > ball1.right) break;
      if (intersects(ball1, ball2)) {
        bounce(ball1, ball2);
      }
    }
  }
  

성능 분석

• 정렬: O(n log n)
• 내부 루프: 평균적으로 O(n + m) (m은 x축에서 겹치는 총 개수)
• 최종 시간 복잡도: O(n log n + m)

시각적 비교

• 전역 쌍 검사와 정렬된 쌍 검사의 비교
• 정렬된 쌍 검사가 훨씬 적은 검사를 수행함

GN⁺의 정리

• 이 글은 게임 개발에서 충돌 감지 알고리듬을 최적화하는 방법을 다룸
• 단순한 O(n^2) 알고리듬에서 시작하여 정렬을 통해 성능을 크게 향상시킴
• 게임 개발자나 소프트웨어 엔지니어에게 매우 유용한 정보임
• 비슷한 기능을 가진 다른 프로젝트로는 Box2D, Bullet Physics 등이 있음