- 게임 물리에서 반복되는 충돌 감지를 공 시뮬레이션으로 풀어 보며, 모든 쌍 검사에서 sweep-and-prune로 넘어가는 최적화 흐름을 설명함
- 단순 방식은
n개 객체의 모든 후보 쌍에 intersects()를 호출해 약 (n*(n-1))/2번 검사하므로 O(n²) 로 빠르게 커짐
- AABB 교차 테스트는 여러 부등식과
&&로 구성되며, 단락 평가와 부등식의 추이성을 이용하면 충돌 가능성이 없는 후보를 일찍 버릴 수 있음
- 객체를 왼쪽 경계인 minimum x 기준으로 정렬한 뒤,
ball2.left > ball1.right가 되는 순간 내부 루프를 break해 이후 후보를 한꺼번에 제외함
- 정렬 비용 O(n log n) 에 x축 겹침 수
m만큼의 루프 비용을 더해 평균적으로 O(n log n + m) 수준이 되며, 불필요한 intersects() 호출이 크게 줄어듦
게임 충돌 감지의 출발점
- 충돌 감지는 비디오 게임 프로그래밍에서 여러 동작의 전제가 됨
- 캐릭터가 서로 통과하지 못하게 함
- Goomba가 다른 객체와 부딪혔을 때 방향을 바꿈
- agar.io에서 큰 세포가 작은 세포를 접촉 시 먹음
- 일반적인 게임 물리를 처리함
- 예시는 강체 공 시뮬레이션을 사용해 여러 충돌 감지 접근을 비교함
- 범위는 가장 단순한 방식에서 sweep-and-prune로 이어지는 접근이며, 공간 분할이나 공간 트리 세분화는 제외함
모든 쌍을 검사하는 단순 접근
- 가장 직접적인 방법은 모든 객체 쌍을 후보로 보는 방식임
- 바깥 루프는 각 공을 순회함
- 안쪽 루프는
i + 1부터 시작해 A-B와 B-A 같은 중복 쌍을 피함
- 각 후보 쌍에
intersects(ball1, ball2)를 호출하고, 참이면 bounce(ball1, ball2)를 실행함
- 이 검사는 매 시간 단계마다 반복되므로, 공은 충돌하는 시점에 튕김 처리됨
- 객체 수가 적을 때는 충분하지만, 수가 늘어나면 검사량이 빠르게 성능 병목이 됨
O(n²)이 만드는 한계
- 단순 알고리듬은 Big O 기준으로 O(n²) 시간에 실행됨
n개의 공에 대해 검사해야 할 쌍은 대략 (n*(n-1))/2, 즉 0.5n² - 0.5n개임
n = 5이면 10쌍n = 10이면 45쌍n = 15이면 105쌍n = 20이면 190쌍
- 모든 객체가 동시에 겹치는 최악의 경우에는 어떤 충돌 감지 알고리듬도 O(n²) 충돌 처리를 피하기 어려움
- 실제 비교에서는 최악의 경우보다 평균 및 최선의 경우가 더 실용적임
- 단순 방식은 실제 충돌 수와 무관하게 항상 Θ(n²) 로 움직여 개선 여지가 큼
intersects() 안의 반복 작업
- 최적화의 출발점은 모든 후보 쌍마다 호출되는
intersects() 함수임
- 일반적인 AABB 교차 테스트는 각 방향의 경계를 비교하는 여러 부등식 검사로 구성됨
function intersects(object1, object2) {
// compare objects' bounds to see if they overlap
return object1.left < object2.right
&& object1.right > object2.left
&& object1.top < object2.bottom
&& object1.bottom > object2.top;
}
- 이 검사는 네 조건으로 나뉨
object1.left < object2.rightobject1.right > object2.leftobject1.top < object2.bottomobject1.bottom > object2.top
&&의 단락 평가 때문에 조건 하나라도 거짓이면 전체 교차 테스트는 즉시 거짓이 됨- 여러 테스트에 걸쳐 “적어도 하나의 조건이 거짓”인 경우를 일반화하면
intersects() 호출 자체를 줄일 수 있음
- 이는 한 축에서 그림자가 겹치지 않으면 두 객체가 충돌하지 않는다는 분리축 정리와 같은 방향의 아이디어임
부등식의 추이성으로 후보 버리기
object1.right > object2.left 조건 하나만 보더라도 최적화 여지가 생김- 세 객체 A, B, C가 수평으로 A-B-C 순서에 있을 때 다음 검사가 모두 거짓일 수 있음
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
A > B가 거짓이고 B > C가 거짓이면, 부등식의 추이성으로 A > C도 거짓임을 알 수 있음- 따라서
intersects(A, C)를 호출하지 않아도 두 객체가 충돌하지 않는다고 판단 가능함
- 이 생략은 객체가 특정 순서에 있을 때만 적용되지만, 객체의 레이블은 임의적이므로 왼쪽 객체를 A, 가운데를 B, 오른쪽을 C처럼 정하면 됨
- 객체를 이런 논리적 순서로 배치하는 작업이 곧 정렬임
x축 최소값 기준 정렬
- 정렬된 리스트는 부등식의 추이성을 여러 후보에 한꺼번에 적용할 수 있게 해줌
- 일반적인 빠른 정렬 알고리듬은 O(n log n) 이며, O(n²)보다 낮음
- 객체는 점이 아니라 x축 구간을 차지하므로, x 위치 기준 정렬에는 왼쪽 경계인 minimum x를 사용함
- 단순 O(n²) 코드에서 필요한 변경은 두 가지임
- 루프 전에
sortByLeft(balls)로 공을 왼쪽 경계 x좌표 기준 정렬함
- 내부 루프에서
ball2.left > ball1.right이면 break함
// sort by min x
sortByLeft(balls);
// for each ball
for (let i = 0; i < balls.length; i++) {
const ball1 = balls[i];
// check each of the other balls
for (let j = i + 1; j < balls.length; j++) {
const ball2 = balls[j];
// stop when too far away
if (ball2.left > ball1.right) break;
// check for collision
if (intersects(ball1, ball2)) {
bounce(ball1, ball2);
}
}
}
- 정렬 함수는 왼쪽 경계 차이를 기준으로 배열을 정렬함
function sortByLeft(balls) {
balls.sort((a,b) => a.left - b.left);
}
break가 안전한 이유
- 리스트가 정렬되어 있으면 임의의 양의 정수
c에 대해 다음 관계가 성립함
balls[j + c].left >= balls[j].left
- 현재 후보가 다음 조건을 만족하면 현재 쌍은 x축에서 겹치지 않음
balls[j].left > ball1.right
balls[j + c].left >= balls[j].left > ball1.right
- 추이성에 따라
balls[j + c].left > ball1.right도 참이므로, 이후 모든 후보 역시 현재 ball1과 x축에서 겹치지 않음
- 현재
ball2가 ball1과 더 이상 겹치지 않는 순간, 내부 루프의 나머지 후보는 검사하지 않고 중단할 수 있음
- 이 최적화는 실제
intersects() 호출을 x축에서 겹치는 쌍으로 제한함
개선된 시간 복잡도
- 정렬 비용은 mergesort나 quicksort 같은 빠른 정렬을 기준으로 O(n log n) 항을 추가함
- 조기 중단이 있는 이중 루프는 평균적으로 O(n + m) 로 볼 수 있음
m은 전체 x축 겹침 수임- 최선의 경우 겹침이 없으면 불필요한 처리가 거의 없어 O(n)에 가까움
- 최악의 경우에는 여전히 O(n²)까지 악화될 수 있음
- 평균 사례는 객체가 대체로 고르게 분포하고 객체당 충돌이 몇 개만 발생하는 상황을 가정함
- 전체 복잡도는 정렬과 루프를 합쳐 O(n log n + m) 임
- 단순 방식보다 나아지는 이유는 두 가지임
n log n은 n²보다 작음- 겹침 수
m에 일부 의존하므로 필요한 것보다 더 많이 처리하지 않음
구현 부담과 다음 단계
- 이 정렬 기반 방식은 코드 변경이 적으면서 실행 시간 성능을 크게 개선하는 균형점임
- 비교 데모에서는 전역 모든 쌍 검사보다 정렬 기반 쌍 검사가 프레임당
intersects() 테스트 수를 눈에 띄게 줄임
- 정렬 비용은 비교 시각화에 표시되지 않지만, 교차 테스트가 충분히 비싸다는 전제를 둠
- 더 발전된 방식과 최종 코드는 Part 2로 이어짐