1만 마리 이웃 탐색을 6.26ms 로, 그리고 기울기가 0 이 된다는 것

1만 마리가 플레이어로 걸어오면 한 점에 뭉쳐 덩어리가 됩니다. 서로 밀어내게 해야 하는데, 그러려면 각자 자기 근처에 누가 있는지를 알아야 합니다.

전수 검사면 1만 × 1만 = 1억 번 입니다. 매 프레임.

공간을 격자로 나눠 두고 자기 칸과 이웃 칸만 보면 된다는 발상 자체는 전부 검사하지 않으려면 미리 나눠 둔다 에서 다뤘습니다. 여기서는 그걸 실제로 짜면서 걸린 것들을 씁니다.

셀 크기가 곧 계약이다

가장 먼저 정할 것은 셀 크기이고, 이건 취향이 아니라 회피 반경과 같아야 합니다.

셀 크기를 반경과 같게 두면 “반경 안의 이웃은 반드시 자기 셀 아니면 인접 8칸 안에 있다” 가 보장 됩니다. 그러면 3×3 만 보고 나머지는 아예 안 봐도 됩니다.

셀이 반경보다 작으면 더 넓게 봐야 하고, 크면 한 셀에 너무 많이 들어가서 셀을 나눈 의미가 줄어듭니다.

public static class SpatialHash
{
    public const float CellSize = 1f;              // 회피 반경과 같게

    public static int2 ToCell(float3 p) =>
        new int2((int)math.floor(p.x / CellSize), (int)math.floor(p.z / CellSize));

    public static int Key(int2 c) =>
        (c.x * 73856093) ^ (c.y * 19349663);       // 공간 해시 상수
}

매 프레임 다시 만든다

적이 계속 움직이니 격자도 매 프레임 다시 채웁니다. NativeParallelMultiHashMap 을 Persistent 로 한 번 잡아 두고, 프레임마다 비우고 채웁니다.

_map.Clear();
new BuildJob { Writer = _map.AsParallelWriter() }.ScheduleParallel();

AsParallelWriter() 가 있어야 워커 여럿이 동시에 넣을 수 있습니다. 그냥 넘기면 잡 안전성 검사가 거부합니다.

Persistent 로 잡았으면 OnDestroy 에서 Dispose() 는 필수입니다. 안 하면 플레이 모드를 껐다 켤 때마다 누수 경고가 쌓입니다.

조회 쪽은 자기 셀과 인접 8칸을 돌면서 TryGetFirstValue / TryGetNextValue 로 훑습니다.

조용히 실패한 것들

해시가 두 개였다

빌드하는 시스템은 CellKey 라는 메서드를 쓰고 있었고, 조회하는 잡은 x + y * 1000 을 쓰고 있었습니다.

같은 셀에 대해 다른 키가 나옵니다. 그러면 넣은 자리와 찾는 자리가 달라서 이웃을 하나도 못 찾습니다.

그런데 에러가 하나도 안 납니다. 맵은 정상이고, 조회도 정상이고, 그냥 결과가 항상 비어 있습니다. 화면에서는 회피가 안 되는 것으로만 보입니다.

그래서 해시를 SpatialHash 정적 클래스 하나로 몰았습니다. 빌드와 조회가 같은 함수를 쓰게 강제하는 것이 이 버그를 구조적으로 막는 유일한 방법입니다.

x + y * 1000 도 지금은 우연히 맞습니다. 월드 반경이 100이라 셀 좌표가 작아서요. 월드가 커지면 (0, 1) 과 (1000, 0) 이 같은 키가 됩니다. 지금 안 터지는 것과 맞는 것은 다릅니다.

잡을 만들고 스케줄을 안 했다

회피 잡을 다 짜 놓고 OnUpdate 에서 스케줄하는 줄을 안 썼습니다. 컴파일 초록불이고, 화면에서는 그냥 회피가 안 됩니다.

앞의 해시 불일치와 증상이 똑같습니다. 원인이 전혀 다른데 화면이 같습니다. 그래서 “회피가 안 된다” 를 보고 원인을 추측하는 게 무의미했습니다.

자기 자신을 이웃으로 셌다

맵에는 자기도 들어 있습니다. 그래서 조회하면 거리 0인 자기가 나옵니다.

var diff = myPos - neighborPos;
var d = math.length(diff);
if (d > 0.0001f)                    // 이 가드가 없으면
    push += diff / d;               // 0으로 나눠서 NaN

NaN 이 Position 에 한 번 들어가면 그 엔티티는 렌더에서 사라지고 영구히 안 돌아옵니다. 어떤 연산을 해도 NaN 이라서요. 그리고 에러는 안 납니다.

이 가드는 나중에 넉백에서 한 번 더 필요해집니다. 같은 실수를 두 번 할 자리가 있었습니다.

의존성은 자동으로 이어진다

맵을 소유한 시스템이 빌드 잡을 먼저 스케줄하고 회피 잡을 이어서 스케줄합니다. state.Dependency 가 자동으로 체인을 걸어 주므로 순서는 보장됩니다.

단 싱글톤에 담아 다른 시스템으로 넘긴 raw 네이티브 컨테이너는 이 추적을 우회합니다. 이건 나중에 공격 판정 시스템에서 잡 안전성 예외 2,531개로 터집니다. 여기서는 한 시스템 안에 있어서 문제가 없었습니다.

검증

숫자로 확인할 수 있는 것을 하나 잡아 뒀습니다. 점유 셀 개수 입니다.

적 1만 마리를 넣고 셌더니 8,310개 셀 이 채워졌습니다. 셀당 평균 1.2마리입니다.

이 숫자가 말해 주는 게 둘입니다.

• 해시가 잘 분산되고 있습니다. 몰려 있으면 점유 셀이 훨씬 적게 나옵니다
• 셀당 1.2마리면 3×3 조회에서 평균 10마리쯤 검사한다는 뜻입니다. 1만 마리를 다 보는 것 대신 열 마리를 봅니다

그리고 화면이 바뀌었습니다. 한 점에 뭉쳐 있던 덩어리가 균일한 원반 군집이 됐습니다.

그래서 얼마나 빨라졌나

이웃을 찾는 방법만 바꿔서 쟀습니다. 나머지 조건은 전부 같습니다.

3.13배는 이 표에서 제일 안 중요한 숫자다

3.13배는 1만 마리일 때의 값 입니다. 2만 마리면 다른 숫자가 나옵니다. 조건이 바뀌면 같이 바뀌는 숫자를 결과라고 부르기는 어렵습니다.

봐야 할 것은 오른쪽 열이 아니라 세로로 읽은 모양 입니다.

공간 해시 쪽은 완전히 평평합니다. 6.1에서 6.5 사이입니다. 적이 1천이든 1만이든 프레임타임이 그대로입니다.

이 6.2ms 는 렌더와 이동과 에디터 오버헤드를 합친 고정 비용 이고, 이웃 탐색이 거기에 얹은 몫은 사실상 0에 수렴 합니다.

왜 그런지는 앞에서 정한 계약에서 그대로 나옵니다. 셀 크기를 회피 반경과 같게 뒀으니 밀도가 일정하면 엔티티당 검사 수가 상수입니다. O(n · k) 에서 k 가 안 변합니다.

전수 검사 쪽은 5,000을 넘기며 무너집니다. 6.35 → 7.60 → 9.25 → 19.60. 고정비용 6.2를 빼면 0.15 → 1.4 → 3.05 → 13.4 입니다. 5,000에서 10,000으로 두 배 될 때 약 4.4배 입니다. n² 그대로입니다.

꼬리가 더 극적이다

평균만 보면 실제 체감을 놓칩니다. p95 를 보면 이렇습니다.

평균이 19.60인데 상위 5퍼센트가 28.94입니다. 프레임이 튄다는 뜻입니다. 공간 해시 쪽은 평균 6.26에 p95 가 7.03이라 거의 붙어 있습니다.

평균 3배 차이보다 이쪽이 플레이 감각에서 더 큽니다. 일정하게 느린 것과 가끔 튀는 것은 다른 문제 입니다.

예상이 틀린 것 둘

“O(n²) 면 프레임 폭사” 는 틀렸다

작업 전 예상은 “1억 번이면 프레임이 죽는다” 였습니다. 전수 검사도 51fps 로 돌았습니다.

전수 검사 버전도 Burst 로 컴파일되고, SIMD 를 쓰고, 워커 스레드에 병렬로 뿌려집니다. 알고리즘만 다르고 나머지 조건은 전부 같습니다.

그러니 이 비교는 “느린 O(n²) 대 빠른 알고리즘” 이 아닙니다. “Burst 로 최적화된 O(n²) 대 Burst + 알고리즘” 입니다.

읽는 방향이 두 가지입니다. Burst 만으로도 1억 연산이 51fps 를 냅니다. 이것도 놀라운 숫자입니다. 그리고 그 위에 알고리즘을 얹으면 3.13배가 더 나오고, 무엇보다 기울기가 0이 됩니다.

1,000 마리에서는 공간 해시가 진다

6.51 대 6.35. 그리드 쪽이 느립니다.

해시맵을 매 프레임 비우고 다시 채우는 고정 오버헤드가 있는데, 1,000 마리에서는 그 비용이 절약한 것보다 큽니다. 이 프로젝트에서 손익분기점은 대략 2,000 마리 근처 입니다.

최적화는 공짜가 아닙니다. “무조건 좋은 최적화” 는 없고, 자료구조를 하나 얹는 것은 고정 비용을 하나 사는 일입니다.

적이 항상 500마리인 게임이었다면 이 작업은 손해였습니다. 그리고 그건 재 보기 전에는 알 수 없었습니다.

여기서 얻은 기준

배수가 아니라 기울기를 본다.

배수는 잰 지점에서만 유효한 값이고, 기울기는 “n 이 늘면 어떻게 되는가” 라는 구조에 대한 답입니다. 그리고 게임이 나중에 어디까지 갈지 모르니 구조 쪽이 더 오래 쓸모 있습니다.