충돌 판정을 처음 접하면 어렵게 느낄 수 있습니다. 하지만 이것은 해석 기하학(Analytical Geometry)에 기반한 흥미로운 주제입니다. 프로그래머에게는 코딩 기술보다 수학적 사고가 더 필요하죠.
두 도형이 공간에서 어떤 관계인지 묻는 과정이라 보면 됩니다. 게임 규칙은 그 수학적 답을 해석한 결과일 뿐입니다. 그래서 모든 판정은 거리와 투영이라는 개념으로 이어집니다.
가장 기초적인 점과 구의 충돌
가장 쉬운 예시인 Point vs Sphere부터 살펴봅시다. 점은 위치만 있고 구는 반지름을 가집니다. 이 둘의 관계는 정말 직관적입니다.
점과 구 중심 사이의 거리를 재보면 알 수 있습니다. 그 거리가 반지름보다 짧으면 점은 구 안에 있습니다. 반대라면 점은 구 밖에 위치합니다.
이 방법은 총알이 명중했는지 확인할 때 자주 씁니다. 마우스 클릭이 버튼 위에서 일어났는지 볼 때도 유용합니다. 계산이 빠르고 명확하기 때문입니다.
구와 구 사이의 거리 비교
조금 더 나아가 Sphere vs Sphere를 보겠습니다. 두 구가 부딪혔는지 판단하려면 두 가지를 비교합니다. 중심 사이의 거리와 두 반지름의 합입니다.
중심 거리가 반지름 합보다 작다면 두 구는 겹친 상태입니다. 이 방식은 계산 비용이 적어 자주 활용됩니다. 폭발 범위를 계산하거나 캐릭터끼리 밀어낼 때 씁니다.
구는 회전해도 모양이 변하지 않습니다. 그래서 방향을 고려할 필요가 없어 계산이 깔끔합니다. 프로그래머들이 구 충돌을 선호하는 이유가 여기에 있습니다.
복잡한 도형을 위한 분리 축 정리
상자나 다각형처럼 각진 도형은 거리만으로 판정하기 어렵습니다. 이때 분리 축 정리(SAT, Separating Axis Theorem)라는 개념이 등장합니다. 이름은 어렵지만 원리는 의외로 명쾌합니다.
두 도형이 떨어져 있다면 그 사이를 가르는 선이 반드시 존재합니다. 이 선을 축이라고 부릅니다. 이 축에 두 도형을 그림자처럼 비춰보는 겁니다.
투영된 그림자가 서로 겹치지 않는다면 두 도형은 충돌하지 않은 것입니다. 반대로 모든 축에서 그림자가 겹친다면 충돌로 봅니다. 이 논리는 매우 강력합니다.
축 정렬 상자에서의 효율성
이 개념은 AABB 충돌에서 아주 잘 보입니다. AABB는 축에 가지런히 정렬된 상자를 말합니다. 검사해야 할 방향이 x, y, z로 정해져 있어 편합니다.
각 축에서 상자의 최소값과 최대값이 겹치는지 확인하면 됩니다. SAT를 가장 효율적으로 사용하는 사례라고 할 수 있습니다. 상자 충돌 처리가 빠른 이유가 이 때문입니다.
볼록 도형의 표준 GJK 알고리즘
도형이 회전하거나 모양이 제각각이면 검사할 축이 너무 많아집니다. 이 문제를 풀기 위해 GJK 알고리즘이 나왔습니다. 현대 게임 엔진에서 볼록 도형 판정의 표준입니다.
이 방식은 두 도형이 부딪혔는지 직접 묻지 않습니다. 대신 민코프스키 차(Minkowski Difference)라는 새로운 공간을 만듭니다. 그리고 그 공간 안에 원점이 있는지를 검사합니다.
원점이 포함되면 충돌이고 아니면 충돌이 아닙니다. 문제를 바라보는 관점을 완전히 바꿔버린 셈입니다. 덕분에 불필요한 연산을 줄일 수 있습니다.
심플렉스를 이용한 영리한 탐색
GJK는 원점을 찾기 위해 심플렉스(Simplex)라는 도형을 사용합니다. 점 하나에서 시작해 선과 삼각형으로 영역을 넓혀갑니다. 원점을 감쌀 가능성이 있는지 계속 확인하는 과정입니다.
만약 원점을 감쌀 수 없다고 판단되면 즉시 계산을 멈춥니다. 충돌이 없다고 결론을 내리는 것이죠. 계산 낭비를 막는 아주 똑똑한 방법입니다.
이처럼 충돌 판정은 공간을 어떻게 해석하느냐에 달렸습니다. 상황에 맞춰 가장 알맞은 수학적 도구를 고르는 것이 중요합니다. 프로그래머의 선택이 성능을 좌우합니다.
