게임 속 세상이 그럴듯해 보이려면 물체끼리 부딪히는 처리가 필요합니다. 하지만 이 작업은 계산 비용이 정말 많이 들어갑니다. 화면에 수백 개의 물체가 있다고 가정해 봅시다. 이것들을 하나하나 다 비교하면 컴퓨터가 버티지 못할 겁니다.
계산을 줄이는 것이 최선의 방법
그래서 프로그래머들은 모든 충돌을 정확히 검사하려 들지 않습니다. 대신 검사하지 않아도 되는 경우를 최대한 빨리 찾아내 제외합니다. 계산을 안 하는 것이 가장 빠른 최적화이기 때문입니다. 처음엔 이 접근 방식이 조금 낯설 수 있습니다.
보통은 정확한 계산을 먼저 떠올리기 쉽습니다. 하지만 게임에서는 굳이 하지 않아도 될 연산을 빼는 것이 더 중요합니다. 이 원리를 이해하면 최적화의 큰 그림이 보입니다.
시간의 흐름을 이용하는 시간적 연속성
가장 먼저 살펴볼 개념은 시간적 연속성(Temporal Coherency)입니다. 프레임과 프레임 사이에는 큰 변화가 없다는 점을 이용합니다. 물체들은 아주 짧은 시간 동안 조금만 움직입니다.
저번 프레임에서 멀리 떨어져 있던 물체는 이번에도 안 부딪힐 확률이 높습니다. 굳이 다시 계산할 필요가 없다는 뜻이죠. 이전 결과를 재사용하면 불필요한 연산을 크게 줄일 수 있습니다.
매번 새롭게 계산하는 대신 지난 데이터를 믿고 가는 겁니다. 이렇게 하면 성능을 아주 효율적으로 아낄 수 있습니다. 정말 똑똑한 방법이지 않나요?
공간을 나누어 관리하는 공간 분할
또 다른 중요한 전략은 공간 분할(Spatial Partitioning)이라고 부릅니다. 충돌은 기본적으로 가까이 있는 물체들끼리만 일어납니다. 전체 공간을 여러 구역으로 나누어 관리하면 어떨까요?
같은 구역이나 인접한 곳에 있는 물체만 검사하면 됩니다. 옥트리(Octree)나 BSP 트리 같은 방식이 여기서 나왔습니다. 서로 멀리 떨어진 물체는 아예 검사 대상에서 빼버리는 겁니다.
이렇게 구역을 나누면 물체가 많아져도 성능이 급격히 떨어지지 않습니다. 불필요한 만남을 원천적으로 차단하는 셈입니다. 덕분에 안정적인 프레임 유지가 가능해집니다.
거칠게 솎아내는 브로드 페이즈
최적화 과정은 보통 단계별로 이루어집니다. 첫 단계인 브로드 페이즈(Broad Phase)는 후보를 거칠게 추리는 과정입니다. 여기서는 계산이 빠른 단순한 도형을 주로 사용합니다.
겹칠 가능성이 없는 물체 쌍을 대량으로 제거하는 것이 목표입니다. 정확도보다는 속도가 중요합니다. 후보를 조금 많이 남기더라도 일단 빠르게 줄이는 것이 유리합니다.
중간 단계인 미드페이즈의 역할
복잡한 물체를 다룰 때는 미드페이즈(Midphase)라는 단계가 등장합니다. 물체 전체를 감싸는 큰 틀을 먼저 검사합니다. 정말 가까워졌을 때만 내부의 세부적인 모양을 확인하는 식입니다.
큰 상자를 먼저 보고 필요할 때만 작은 상자를 보는 방식입니다. 모양이 복잡한 물체일수록 이 과정이 큰 도움을 줍니다. 불필요한 세부 검사를 막아주니까요.
정밀하게 확인하는 내로우 페이즈
마지막으로 내로우 페이즈(Narrow Phase)에서 정밀한 검사를 수행합니다. 구와 구 혹은 캡슐과 삼각형 같은 구체적인 모양을 비교합니다. 계산 비용은 가장 크지만 대상이 이미 많이 줄어든 상태입니다.
무거운 계산은 정말 필요할 때만 수행하니 전체 성능은 유지됩니다. 앞선 단계들이 훌륭하게 후보를 걸러준 덕분입니다. 덕분에 프로그래머는 정교한 알고리즘을 마음껏 쓸 수 있습니다.
대표적인 알고리즘 스윕 앤 프룬
브로드 페이즈에서 자주 쓰이는 스윕 앤 프룬(Sweep and Prune)도 알아두면 좋습니다. 물체의 경계 상자를 축 위에 투영해 정렬하는 방식입니다. 겹치는 구간만 충돌 후보로 봅니다.
물체가 조금씩만 움직인다는 점을 아주 잘 활용한 알고리즘입니다. 정렬 결과가 크게 바뀌지 않아 매우 효율적입니다. 많은 게임 엔진이 이 방식을 채택하고 있습니다.
충돌 최적화의 진짜 목표는 계산을 빠르게 하는 것이 아닙니다. 계산 자체를 최대한 피하는 것에 있습니다. 이 원리를 잘 활용하면 수많은 물체가 있어도 게임은 부드럽게 돌아갑니다.
