많은 캐릭터의 충돌을 검사하려 합니다. 충돌 후보를 먼저 추리는 broad phase와 실제 형상을 검사하는 narrow phase를 왜 나누나요?

많은 물체를 서로 모두 정밀 검사하면 후보 쌍이 대략 객체 수의 제곱으로 늘어납니다. 그래서 먼저 싸고 보수적인 경계로 충돌 가능성이 있는 쌍만 추린 뒤, 그 후보에 실제 형상과 게임 규칙을 적용합니다. 전자를 넓은 단계(broad phase), 후자를 좁은 단계(narrow phase)라고 부릅니다. broad phase는 거짓 양성을 조금 포함해도 되지만 실제 충돌 후보를 누락하면 안 되고, narrow phase가 최종 판정의 책임을 집니다.

후보를 줄이는 방법

캐릭터를 원, 축 정렬 경계 상자, 캡슐 같은 단순한 도형으로 감싸고 uniform grid·공간 해시·동적 AABB 트리에서 가까운 객체를 찾을 수 있습니다. 서로 멀리 떨어진 객체는 정밀한 다각형이나 캡슐 교차 계산에 들어가지 않습니다. 다만 AABB가 겹쳐도 실제 몸체는 떨어져 있을 수 있으므로 그것을 곧바로 충돌로 확정하면 안 됩니다. 후보를 만들 때 충돌 레이어, 팀, 객체 유형처럼 결과가 항상 배제되는 조건을 함께 적용하면 narrow phase 비용을 줄일 수 있지만, 빠른 물체는 현재 위치만 인덱스에 넣지 말고, 선형 병진을 전제로 한 한 틱의 swept AABB를 사용해야 합니다. 회전이나 곡선 운동으로 형상이 크게 바뀌면 시작·끝 상자만으로 부족하므로 회전 범위를 포함한 보수적 경계나 별도 연속 검사를 사용합니다. 객체가 이동 중이면 인덱스 갱신 시점과 충돌 검사 시점의 스냅샷도 중요합니다.

갱신 중인 목록을 읽어 한 셀에서는 보이고 다른 셀에서는 사라지는 상태가 되면 후보 누락이 생깁니다. 틱 시작에 불변 스냅샷을 만들거나, 객체의 위치 버전과 참조 수명을 관리해 하나의 검사 라운드가 일관된 장면을 보게 하겠습니다. 객체 크기가 크게 다르면 작은 셀 하나에 큰 객체를 억지로 넣기보다 여러 셀 등록, 계층 격자, 별도 큰 객체 목록을 검토합니다.

정밀 판정과 비용

narrow phase에서는 실제 캡슐·박스·메시의 교차, 높이와 경사, 충돌 레이어, 트리거인지 물리적 밀어내기인지, 이동 중 최초 충돌 시점까지 확인합니다. broad phase가 보수적이지 않아 경계를 잘못 계산하면 narrow phase가 아무리 정밀해도 빠진 충돌을 복구할 수 없습니다. 반대로 지나치게 큰 경계를 쓰면 후보가 너무 많아져 두 단계 분리의 이점이 사라집니다. 테스트는 균일 분포와 핫스팟, 큰 객체와 작은 객체, 고속 이동, 셀 경계 왕복, 레이어 필터, 같은 쌍의 중복 후보를 포함합니다. 전체 쌍 수, 후보 수와 p99, narrow phase 시간, 누락된 충돌, 프레임별 메모리를 따로 측정하겠습니다. “경계가 겹친다”는 것은 가능성이고 “실제 형상이 규칙을 위반한다”가 판정이라는 후보-확정 분리(candidate/confirmation separation)가 설계의 핵심입니다. 후보 생성의 보수성은 충돌 형상만이 아니라 시간 범위에도 달려 있습니다.

현재 프레임 위치를 인덱스에 갱신하는 중 다른 스레드가 이전 목록을 읽을 수 있다면 이전과 새 경계를 모두 잠시 유지하거나 틱 스냅샷을 사용해야 합니다. broad phase가 후보를 놓치지 않는지 확인하려면 무작위 테스트만으로 부족하고, 경계 접촉·최대 속도·최대 크기에서 가능한 이동 궤적을 생성해 기준 정밀 검사와 후보 집합의 포함 관계를 검증하겠습니다. narrow phase에서 여러 후보가 동시에 닿으면 가장 이른 충돌 시간, 고정된 객체 ID 같은 결정적 기준을 사용하고, 트리거·피해·물리 밀어내기의 부수 효과를 중복 적용하지 않게 이벤트 ID를 둡니다. 후보를 많이 줄였다는 수치보다 최종 판정이 빠진 적이 없는지가 먼저입니다. 두 단계 사이에 필터를 추가할수록 비용은 줄 수 있지만, 필터 조건이 변할 때 인덱스와 스냅샷이 같은 규칙을 보는지 확인해야 합니다. 객체의 ID·세대가 일치하는지와 실제 형상 메모리가 검사 끝까지 살아 있는지도 확인합니다.

세대 비교는 중복 후보 제거와 별개이며 해제된 메모리에 접근해도 안전하게 만드는 장치가 아닙니다.