빠른 비교

구조 이해

broad phase는 정확한 충돌 판정이 아니라 후보 축소다

충돌 판정을 단순하게 만들면 모든 객체 쌍을 검사합니다. 객체가 n개면 후보 쌍은 대략 n * (n - 1) / 2개까지 늘어나므로, 적과 투사체가 많아지는 순간 비용이 급격히 커집니다. Broad phase는 이 전체 비교를 바로 실행하지 않고 "부딪힐 가능성이 있는 후보"만 좁혀 주는 단계입니다. 실제 겹침 여부는 이후 narrow phase에서 AABB, circle, capsule, polygon, physics shape 같은 정확한 판정으로 확인합니다.

all objects
  -> broad phase: 가까운 후보만 추림
  -> narrow phase: 실제 shape 충돌 판정
  -> collision response

cell 크기는 성능 특성을 결정하는 첫 번째 변수다

Uniform grid와 spatial hash는 객체를 cell에 넣고, query할 때 같은 cell이나 이웃 cell의 객체만 검사합니다. cell이 너무 크면 한 cell 안에 객체가 많이 몰려 후보가 줄지 않습니다. 반대로 cell이 너무 작으면 큰 객체가 여러 cell에 걸치고, 이동할 때 cell membership 갱신 비용이 커집니다. 실무에서는 평균 객체 크기, 공격 범위, 카메라나 시야 query 범위를 기준으로 cell 크기를 먼저 잡고, profiler로 후보 수와 갱신 비용을 같이 봐야 합니다.

cell too large  -> 후보가 너무 많음
cell too small  -> 삽입, 제거, 이웃 조회가 많아짐
cell reasonable -> 후보 수와 갱신 비용이 함께 줄어듦

false positive는 허용하지만 false negative는 막아야 한다

Broad phase는 "후보가 너무 많이 나온다"는 문제는 견딜 수 있습니다. 후보가 많으면 narrow phase 비용이 늘어날 뿐입니다. 반대로 실제로 부딪힐 수 있는 객체가 후보에서 빠지는 false negative는 게임 규칙을 깨뜨립니다. 큰 객체가 여러 cell에 걸칠 수 있다면 겹치는 모든 cell에 등록하거나, query 범위를 객체 반경만큼 확장해야 합니다. 경계선에 있는 객체를 현재 cell 하나에만 넣으면 바로 옆 cell의 충돌을 놓칠 수 있습니다.

동적 객체와 정적 객체는 같은 구조에 넣지 않아도 된다

벽, 바닥, 지형처럼 거의 움직이지 않는 대상은 한 번 만든 spatial index를 오래 재사용할 수 있습니다. 반대로 적, 투사체, 아이템처럼 매 frame 움직이는 대상은 삽입과 제거 비용이 계속 발생합니다. 둘을 같은 구조로만 관리하면 정적 데이터까지 매번 다시 만지는 실수가 생깁니다. 자주 바뀌는 동적 객체는 단순한 grid나 hash에 두고, 정적 geometry는 별도 BVH, quadtree, tile map index로 나누는 편이 관리하기 쉽습니다.

선택 기준

주의할 점

실패 예시
- 큰 보스 collider를 중심점이 들어간 cell 하나에만 등록
- 투사체 query도 현재 cell 하나만 확인
- 보스의 collider가 이웃 cell까지 걸쳐 있지만 후보에서 빠짐

결과
- 눈에 보이는 접촉이 있는데 충돌 이벤트가 발생하지 않음
- cell 경계에서만 재현되는 불규칙한 버그가 생김

또 다른 흔한 실패는 profiler 없이 구조부터 복잡하게 만드는 것입니다. 객체 수가 적거나 query 빈도가 낮으면 전체 비교가 더 읽기 쉽고 충분히 빠를 수 있습니다. Broad phase는 후보 수, 갱신 빈도, query 범위가 실제 병목으로 확인될 때 적용하는 것이 좋습니다.