# 정렬, 스윕, 가지치기: Collision Detection Algorithms (2023) > Clean Markdown view of GeekNews topic #16325. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=16325](https://news.hada.io/topic?id=16325) - GeekNews Markdown: [https://news.hada.io/topic/16325.md](https://news.hada.io/topic/16325.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2024-08-15T23:34:41+09:00 - Updated: 2024-08-15T23:34:41+09:00 - Original source: [leanrada.com](https://leanrada.com/notes/sweep-and-prune/) - Points: 3 - Comments: 1 ## Topic Body ### 충돌 감지 알고리듬 #### 충돌 감지 - 비디오 게임 프로그래밍에서 충돌 감지는 매우 일반적인 문제임 - 캐릭터가 서로 통과하지 못하게 하거나, 물리 엔진을 구현하는 데 필수적임 #### 단순한 접근법 🐥 - 모든 객체 쌍을 검사하여 충돌 여부를 확인하는 방법 - 코드 예시: ```javascript 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()` 함수 최적화: ```javascript function intersects(object1, object2) { return object1.left < object2.right && object1.right > object2.left && object1.top < object2.bottom && object1.bottom > object2.top; } ``` #### 정렬을 통한 최적화 - 객체를 x 좌표에 따라 정렬하면 불필요한 검사를 줄일 수 있음 - 코드 예시: ```javascript 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 등이 있음 ## Comments ### Comment 28045 - Author: neo - Created: 2024-08-15T23:34:42+09:00 - Points: 1 ###### [Hacker News 의견](https://news.ycombinator.com/item?id=41241942) - 저자는 최적의 성능을 위해 mergesort나 quicksort 같은 "빠른" 정렬 알고리즘을 사용할 것을 제안함 - 그러나 실제로는 insertion sort 같은 "덜 좋은" 정렬 알고리즘이 더 나은 성능을 보일 수 있음 - 충돌 감지 시스템의 객체는 프레임 간에 상대적으로 작은 단계로 이동하기 때문에 이전 프레임의 거의 정렬된 리스트를 유지할 수 있음 - 이러한 거의 정렬된 리스트를 정렬할 때, insertion sort는 O(n)에 가깝고 Quicksort는 O(n^2)에 가까움 - 과거에 비슷한 작업을 했지만 정렬 대신 각 방향에 대한 인덱스 리스트를 유지했음 - 예를 들어, `objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge` 같은 4개의 리스트가 있음 - 객체가 수평으로 이동하면 leftEdge와 rightEdge 배열에서 자신의 인덱스를 업데이트함 - 이동하면서 최대 1~2개의 인덱스만 교환하면 됨 - 이 글은 정말 잘 정리되어 있음 - 90년대 후반부터 게임 개발을 해왔지만 대부분의 작업이 엔진에 의해 추상화됨 - 복잡한 시스템 시뮬레이션을 이해하는 데 필수적임 - 저자가 매우 접근하기 쉬운 글을 작성해줘서 감사함 - 연속 충돌 감지에 관한 문서를 항상 즐겨 읽었음 - - 라이브러리 자체는 성능 면에서 놀라움 - 그러나 최적화가 많이 되어 있어 통합하기는 다소 어려움 - 일러스트레이션 사용이 좋았음 - 때때로 이러한 기사들이 멋진 데모를 모으기 위한 핑계처럼 느껴지지만, 이번 글은 일러스트레이션이 주를 이루지 않음 - Part 2: - 그의 다른 글도 확인해보길 권장함: - "이 단순한 알고리즘은 Big O 용어로 O(n^2) 시간에 실행됨"이라는 주장에 대해 의문을 제기함 - 외부 루프(i)는 n - 1까지 세고, 내부 루프(j)는 i + 1에서 시작하여 점점 적은 수를 셈 - CS 전공자는 아니지만, 큰 n 값에 대해 O(n^2)와 대략적으로 동일한지, 아니면 더 적은지 궁금함 - 이 방법이 잠재적 충돌자를 줄이기 위해 쿼드 트리를 사용하는 것과 유사한지 궁금했음 - 선형 프로그래밍 방법이 제안된 적이 있는지 궁금했음 - - 이 웹사이트에 좋은 의미로 산만해졌음 - 재미있고 영감을 줌