▲

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

 (leanrada.com)
3P by neo 3달전 | favorite | 댓글 1개

충돌 감지 알고리듬

충돌 감지

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

단순한 접근법 🐥

  • 모든 객체 쌍을 검사하여 충돌 여부를 확인하는 방법
  • 코드 예시: 
    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 등이 있음
▲
neo 3달전  [-]
Hacker News 의견

  • 저자는 최적의 성능을 위해 mergesort나 quicksort 같은 "빠른" 정렬 알고리즘을 사용할 것을 제안함

    • 그러나 실제로는 insertion sort 같은 "덜 좋은" 정렬 알고리즘이 더 나은 성능을 보일 수 있음
    • 충돌 감지 시스템의 객체는 프레임 간에 상대적으로 작은 단계로 이동하기 때문에 이전 프레임의 거의 정렬된 리스트를 유지할 수 있음
    • 이러한 거의 정렬된 리스트를 정렬할 때, insertion sort는 O(n)에 가깝고 Quicksort는 O(n^2)에 가까움

  • 과거에 비슷한 작업을 했지만 정렬 대신 각 방향에 대한 인덱스 리스트를 유지했음

    • 예를 들어, objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge 같은 4개의 리스트가 있음
    • 객체가 수평으로 이동하면 leftEdge와 rightEdge 배열에서 자신의 인덱스를 업데이트함
    • 이동하면서 최대 1~2개의 인덱스만 교환하면 됨

  • 이 글은 정말 잘 정리되어 있음

    • 90년대 후반부터 게임 개발을 해왔지만 대부분의 작업이 엔진에 의해 추상화됨
    • 복잡한 시스템 시뮬레이션을 이해하는 데 필수적임
    • 저자가 매우 접근하기 쉬운 글을 작성해줘서 감사함

  • 연속 충돌 감지에 관한 문서를 항상 즐겨 읽었음

  • 일러스트레이션 사용이 좋았음

    • 때때로 이러한 기사들이 멋진 데모를 모으기 위한 핑계처럼 느껴지지만, 이번 글은 일러스트레이션이 주를 이루지 않음

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/

  • "이 단순한 알고리즘은 Big O 용어로 O(n^2) 시간에 실행됨"이라는 주장에 대해 의문을 제기함

    • 외부 루프(i)는 n - 1까지 세고, 내부 루프(j)는 i + 1에서 시작하여 점점 적은 수를 셈
    • CS 전공자는 아니지만, 큰 n 값에 대해 O(n^2)와 대략적으로 동일한지, 아니면 더 적은지 궁금함

  • 이 방법이 잠재적 충돌자를 줄이기 위해 쿼드 트리를 사용하는 것과 유사한지 궁금했음

  • 선형 프로그래밍 방법이 제안된 적이 있는지 궁금했음

  • 이 웹사이트에 좋은 의미로 산만해졌음

    • 재미있고 영감을 줌
답변달기