마인크래프트 JE가 히트박스를 복셀 비트셋으로 표현하고, 서로 다른 복셀 크기를 맞추기 위해 좌표를 분할해 3중 루프와 프레디케이트로 교차·포함·동등성까지 검사하는 구조를 해부하며, 간단한 AABB 목록 방식과의 비교로 비효율을 지적한다.
2024년 9월 14일Telegram
게임에서의 충돌 검출은 무거운 알고리즘이 쓰입니다. 예를 들어, 공간에서 임의로 회전한 두 개의 정육면체만 생각해도 얼마나 복잡할지 상상해 보세요. 두 모서리가 맞닿거나, 꼭짓점과 면이 닿거나, 그보다 더 복잡한 접촉이 일어날 수 있습니다.
마인크래프트에서는 모든 히트박스의 기하가 좌표축에 평행합니다, 즉 기울어지지 않습니다. 이 점이 충돌 탐색을 크게 단순화합니다.
나였다면 아주 단순하게 짰을 거예요. 블록의 히트박스는 여러 직육면체의 합집합이니, 그걸 그대로 저장하면 됩니다. 예컨대 6요소 튜플(x1, y1, z1, x2, y2, z2)들의 리스트로요. 대부분의 경우 이 리스트는 매우 짧습니다. 일반적인 큐브는 길이가 1, 유리판은 2까지 갈 수 있고, 모루는 무려 3개, 담장은 무려 4개나 됩니다. 히트박스 교차 검사는 두 히트박스의 직육면체 쌍을 전부 돌면 충분합니다(최대 16쌍 정도일 것 같네요). 축에 평행한 직육면체끼리는 교차 판정이 아주 간단하니까요.
하지만 Minecraft JE를 쓴 건 제가 아니니, 구현은 다릅니다.
거기서는 히트박스를 복셀(3차원의 픽셀) 배열로 저장합니다. W×H×D 크기의 비트셋이 있고, 각 비트가 하나의 복셀을 나타냅니다. 복셀은 꼭 정육면체일 필요가 없습니다. 비트셋 옆에 각 축별 복셀의 크기 배열을 따로 둡니다. 예를 들어, 다음과 같은 히트박스(깊이 방향 ×4)라면
##..
####
####
####
비트셋은 4개 원소에 대해 다음과 같이 저장되고,
10
11
복셀 크기는 가로 2,2, 세로 1,3, 깊이 4가 됩니다.
설령 두 히트박스가 기가 막히게 정렬되어 있다 해도, 두 히트박스의 비트셋을 그대로 AND 연산하는 건 옳지 않습니다. 복셀 크기가 서로 다를 수 있어서, #.와 .#는 충분히 서로 교차할 수 있고(반대로 ###.와 .###는 교차하지 않을 수도 있습니다). 1차원에서 올바른 방법은 다음과 같습니다.
3차원에서는 세 축 모두에 대해 같은 알고리즘을 적용합니다. 각 축마다 구간 배열을 만들고, 세 겹의 중첩 루프로 이 구간들이 만드는 모든 직육면체를 순회합니다. 이렇게 하면 그 직육면체들이 복셀 경계를 절대 가로지르지 않습니다. 총 (W1+W2+2)×(H1+H2+2)×(D1+D2+2)번의 검사가 이뤄집니다.
예를 들어 유리판의 히트박스가 이렇게 생겼다고 합시다:
.#.
###
.#.
여기서는 두 축에 대해 관심 좌표가 4개(0,1,2,3), 나머지 한 축에 대해 2개(0,1)입니다. 정육면체형 몹은 각 축에 관심 좌표가 2개씩이므로, 몹과 유리판의 충돌을 검사할 때(그 전에, 예를 들어 거리 기반의 더 거친 검사가 모호한 결과를 내놓았다면) 루프는 6×6×4=144번 순회합니다. 비교를 위해 말하자면, 제 방식이라면 2번이면 끝납니다.
히트박스 교차 검사는 히트박스 위에서 할 수 있는 유일하게 유용한 연산이 아닙니다. 예를 들어 담장 블록은 두 가지 모델이 있습니다. 위 블록과 연결되는 모델, 그리고 연결되지 않는 모델. 연결 기준은 담장의 윗면 전체가 위 블록의 아랫면 전체와 맞닿는지 여부입니다. 즉, 담장의 윗면 "히트박스"가 그 블록 아랫면의 "히트박스"에 포함되어 있어야 합니다. 본질적으로 같은 문제지만 3D가 아니라 2D이고, 교차가 아니라 포함 관계죠.
추상 팩토리의 추상 팩토리를 사랑하는 분들은 여기서 문제 서술이 비슷하니 해법도 같아야 한다고 생각했습니다. 그래서 교차 검사용 절차를 일반화해서, 프레디케이트를 인자로 받는 공용 절차로 바꿔버렸습니다. 프레디케이트란 두 인자를 받는 임의의 불리언 함수입니다. 교차 검사는 a∧b, 비포함 검사는 a∧¬b가 되겠죠. 이 절차는 공간 어딘가의 한 점에서라도 프레디케이트가 true를 반환하면 true를 돌려줍니다.
불행히도(혹은 다행히도) 재미는 여기서 끝나지 않습니다. 몹의 길찾기 AI는 히트박스를 고려하기 때문에, 블록을 다른 블록으로 바꾸거나(혹은 블록 상태가 바뀌면) 경로를 다시 짜야 할 수도 있습니다. 최적화를 위해서는 기존 히트박스와 새 히트박스가 다를 때만 다시 계산해야 합니다. 그럼 히트박스가 같은지 어떻게 확인할까요? 맞습니다, 이미 만든 절차를 프레디케이트 a≠b로 돌리면 됩니다.
이제 이 모든 과정을 터보 모드로 훑어봅시다. 소스 코드에서는 시작 시 히트박스를 여러 직육면체의 합집합으로 명령형으로 계산하고, 그 결과로 복셀 배열을 생성합니다. 블록이 바뀔 때마다 이 배열들을 읽어 오고, "관심" 좌표 집합의 합집합을 구하고, 그 좌표들로 3중 루프를 돌립니다. 루프 안에서는 비트셋 원소를 읽고, 동적으로 주입된 프레디케이트 a≠b를 호출합니다. 어딘가에는 두 히트박스가 동일한 객체(주소 기준)라면 항상 같다고 치자는 최적화도 굴러다니지만, 다른 히트박스들에는 도움 되지 않습니다.
왜 이렇게까지 해야 하는지는 제 이해를 살짝 벗어납니다. 저는 직육면체 배열을 저장해 두고, 그냥 그걸로 동등성 비교를 했을 겁니다. 히트박스가 코드에 박혀 있고 데이터팩으로 바뀌지도 않는 걸 감안하면, 같은 히트박스는(여러 분해 방법이 가능하더라도) 항상 같은 직육면체 분해를 쓰도록 미리 보장하는 것도 가능할 겁니다. Mojang의 해법은 제 머리엔 떠오르지도 않네요. 아마 저는 진짜 프로그래머가 아닌가 봅니다.