좌표를 칸으로, 칸을 배열로

공간을 칸으로 나눠 두면 가까운 것만 본다는 발상은 한 줄로 끝납니다. 그런데 막상 만들어 보면 계산이 아니라 구현에서 막힙니다.

• 맵 가운데를 원점으로 잡았더니 원점 근처에서만 판정이 이상합니다
• 맵이 얼마나 커질지 몰라서 배열 크기를 정할 수가 없습니다
• 두 물체가 부딪혔다는 신호가 두 번씩 옵니다

셋 다 같은 자리에서 나옵니다. 좌표를 칸으로 바꾸고, 칸을 자료구조에 앉히는 자리입니다.

좌표를 칸 번호로 바꾸는 한 줄

칸 번호는 좌표를 칸 크기로 나누면 나옵니다. 이렇게 쓰고 싶어집니다.

int cx = (int)(x / cellSize);   // 여기서 갈립니다

(int) 캐스팅은 0 쪽으로 자릅니다. 양수에서는 내림과 같지만 음수에서는 올림이 됩니다. 칸 크기가 1일 때 무슨 일이 생기는지 보면 이렇습니다.

-0.5 와 0.5 가 같은 칸이 됩니다. 원점을 낀 두 칸이 하나로 붙어서 그 자리만 칸이 두 배로 넓어집니다. 맵 구석을 원점으로 잡으면 음수 좌표가 없으니 안 터지고, 가운데를 원점으로 잡는 순간 터집니다. “왜 맵 가운데서만 이상하지” 가 여기서 나옵니다.

int cx = Mathf.FloorToInt(x / cellSize);

칸 크기를 2의 거듭제곱으로 잡을 수 있다면 나눗셈 대신 시프트를 씁니다.

int cx = (int)x >> shift;       // cellSize == 1 << shift

산술 시프트는 음수에서도 내림입니다. 빠른 길인데 마침 안전한 길이기도 합니다. 다만 (int)x 캐스팅이 앞서 있으니, 좌표가 실수라면 그 캐스팅에서 같은 문제가 되돌아옵니다. 시프트를 쓸 거면 좌표를 먼저 정수로 만드는 자리를 확인하세요.

맵 밖을 다루려면 배열을 버린다

칸 번호가 나왔으면 그 칸의 목록을 찾아야 합니다. 가장 쉬운 방법은 2차원 배열입니다. 그런데 배열은 맵 크기를 미리 알아야 만들 수 있습니다.

오픈월드나 절차적으로 늘어나는 맵에서는 아예 못 정합니다. 물체가 1,000개뿐인데 칸 2,500만 개를 들고 있는 것도 말이 안 됩니다.

그래서 칸 번호를 해시해서 정해진 개수의 버킷에 넣습니다. 공간 해시(spatial hash)입니다.

int Hash(int cx, int cy)
    => ((cx * 73856093) ^ (cy * 19349663)) & (bucketCount - 1);

두 큰 소수를 곱해 XOR 하는 이 조합은 공간 해시에서 흔히 쓰는 것입니다. 버킷 수를 2의 거듭제곱으로 잡으면 나머지 연산 대신 & 로 끝납니다.

여기서 해시 충돌은 걱정거리가 아닙니다. 일반적인 해시 테이블과 다른 점입니다.

멀리 떨어진 두 칸이 같은 버킷에 들어와도, 어차피 꺼낸 다음에 거리를 재서 거릅니다. 후보가 조금 늘어날 뿐 답이 틀리지는 않습니다. 그래서 충돌 처리를 따로 안 해도 됩니다. 버킷 수만 물체 수와 비슷하게 잡아 두면 됩니다.

반대로 칸 번호를 버킷에 같이 저장해 두지 않으면 안 됩니다. 꺼낸 것이 정말 그 칸의 물체인지 확인할 방법이 없어집니다. 거리로 거르니 결과는 맞지만, 엉뚱한 칸의 물체까지 매번 거리 계산을 하게 됩니다.

같은 쌍을 두 번 보지 않기

자기 칸과 이웃 여덟 칸을 보면 A 와 B 의 쌍을 두 번 봅니다. A 에서 B 를 한 번, B 에서 A 를 한 번입니다. 충돌 신호가 두 번 오는 이유가 이것입니다.

이웃을 절반만 보면 됩니다. 자기 칸 안에서는 j > i 인 쌍만 보고, 이웃은 오른쪽·왼쪽아래·아래·오른쪽아래 넷만 봅니다.

static readonly (int dx, int dy)[] Half = { (1, 0), (-1, 1), (0, 1), (1, 1) };

for (int i = 0; i < ids.Count; i++) {
    for (int j = i + 1; j < ids.Count; j++)   // 같은 칸
        Test(ids[i], ids[j]);

    foreach (var (dx, dy) in Half)            // 이웃 절반
        foreach (var other in CellAt(cx + dx, cy + dy))
            Test(ids[i], other);
}

빠뜨리는 쌍은 없습니다. 위쪽 네 칸과의 쌍은 그 칸이 자기 차례일 때 봅니다. 1,000개를 뿌려 재 보면 검사 횟수가 3,554번에서 1,777번으로 정확히 절반이 됩니다.

칸이 반경보다 작으면 겹을 늘려야 한다

이웃 한 겹, 즉 아홉 칸을 보는 것은 칸 크기가 검사 반경보다 클 때만 맞습니다. 칸이 반경보다 작으면 한 겹으로는 반경을 못 덮어서 가까운 쌍을 놓칩니다.

봐야 하는 겹 수는 이렇게 정해집니다.

겹 수 k = ceil(검사 반경 / 칸 크기)
보는 칸 = (2k + 1)²

칸을 잘게 쪼개면 거리 검사는 줄지만 훑어야 하는 칸이 제곱으로 늘어납니다. 100×100 맵에 물체 1,000개를 뿌리고 검사 반경을 2로 두고 재 봤습니다. 찾아낸 가까운 쌍은 646개로 전부 같고, 드는 일만 다릅니다.

칸 크기를 검사 반경에 맞춘 자리가 바닥입니다. 양쪽으로 멀어지면 여덟 배, 마흔 배씩 불어납니다. 왼쪽 절반은 칸을 도느라 비싸지고 오른쪽 절반은 거리를 재느라 비싸집니다.

참고로 전부 대 전부로 비교하면 499,500번입니다. 바닥값의 백 배입니다.

칸마다 리스트를 두지 않는다

남은 것은 그릇입니다. 칸마다 리스트를 하나씩 두는 것이 가장 먼저 떠오릅니다.

List<int>[] cells;              // 이렇게 하고 싶어지지만

이러면 칸 수만큼 리스트를 할당하고, 매 프레임 전부 Clear() 하고, 칸을 훑을 때마다 다른 곳에 흩어진 메모리를 따라갑니다. 칸이 수천 개면 그 자체가 부담이고, 리스트가 늘어날 때마다 새 배열을 잡습니다.

배열 세 개면 같은 일을 할 수 있습니다. 세고, 더하고, 담습니다.

// 1. 칸마다 몇 개인지 센다
Array.Clear(count, 0, count.Length);
for (int i = 0; i < n; i++) count[CellOf(pos[i])]++;

// 2. 앞에서부터 더해서 각 칸이 쓸 자리의 시작을 정한다
int sum = 0;
for (int c = 0; c < cellCount; c++) {
    start[c] = sum;
    sum += count[c];
}
start[cellCount] = sum;

// 3. 시작 자리부터 차례로 담는다
Array.Copy(start, cursor, cellCount);
for (int i = 0; i < n; i++) items[cursor[CellOf(pos[i])]++] = i;

이제 한 칸의 물체는 배열에서 붙어 있습니다.

for (int k = start[c]; k < start[c + 1]; k++) {
    int id = items[k];
    // ...
}

얻는 것이 여럿입니다.

• 할당이 없습니다. 배열 세 개를 한 번 잡아 두고 매 프레임 덮어씁니다. GC 가 볼 것이 없습니다
• 순서대로 읽습니다. 한 칸의 물체가 붙어 있으니 캐시가 잘 맞습니다
• 잡 시스템에 올릴 수 있습니다. 리스트가 없으니 네이티브 배열로 그대로 옮겨집니다
• 매 프레임 통째로 다시 지어도 쌉니다. 물체가 칸을 옮겼는지 따질 필요가 없습니다

값도 있습니다. 비용이 물체 수에 칸 수를 더한 만큼입니다. 누적합은 물체가 몇 개든 칸 수만큼 돕니다. 칸이 물체보다 훨씬 많으면 그 부분이 커집니다. 공간 해시로 버킷 수를 물체 수에 맞춰 두는 것이 여기서도 값을 합니다.

정리

균일 격자는 발상이 아니라 경계에서 막힙니다.

• 칸 번호는 내림으로 구합니다. (int) 캐스팅은 음수에서 0 쪽으로 잘려서 원점 근처 두 칸을 붙여 놓습니다
• 맵 크기를 못 정하면 배열 대신 해시로 버킷에 넣습니다. 거리로 거르니 해시 충돌은 답을 안 깨뜨립니다
• 이웃은 절반만 봅니다. 나머지 절반은 상대 칸이 자기 차례에 봅니다. 검사가 정확히 절반이 됩니다
• 봐야 하는 겹 수는 ceil(반경 / 칸 크기) 입니다. 칸을 반경에 맞춘 자리가 바닥이고 양쪽으로 멀어지면 급하게 비싸집니다
• 그릇은 리스트 배열 대신 세고, 더하고, 담는 배열 세 개로 만듭니다. 할당이 없고 한 칸이 메모리에서 붙어 있습니다