게임 서버의 공간 해시에서 조회 반경·객체 크기·분포를 바탕으로 셀 크기와 중복 처리를 어떻게 정하나요?

공간 해시나 uniform grid는 월드 좌표를 셀 좌표로 바꾸고 셀별 객체 목록을 관리해, 전체 객체가 아니라 조회 범위와 겹치는 셀의 후보만 검사하는 구조입니다. 셀 크기를 작게 하면 셀당 후보와 불필요한 거리 검사가 줄 수 있지만 큰 객체가 여러 셀에 등록되고 이동 때 목록 갱신이 많아집니다. 크게 하면 객체 등록은 단순해질 수 있지만 핫스팟 셀의 후보가 급증합니다. 따라서 정답인 셀 크기는 평균 객체 크기 하나가 아니라 조회-갱신 비용 균형(query-update cost balance)으로 정합니다.

셀 크기와 분포

조회 반경이 R이면 최소한 그 반경을 덮는 셀 범위를 검사해야 하므로 셀이 너무 작으면 한 조회가 많은 셀을 해시 조회하는 비용이 생깁니다. 객체 반경과 속도도 봐야 합니다. 큰 객체는 자신이 차지하는 모든 셀에 등록하거나 중심 셀과 확장 경계를 별도로 저장할 수 있고, 한 틱에 여러 셀을 건너뛰는 빠른 객체는 이전 위치와 현재 위치를 잇는 전체 이동 궤적을 덮는 swept 경계를 계산해 그 경계와 교차하는 모든 셀에 후보를 등록해야 합니다. 단순히 이전·현재 셀의 합집합만 쓰면 중간 셀을 건너뛰는 빠른 객체를 놓칠 수 있습니다. 객체 크기가 매우 다르면 작은 객체용 격자와 큰 객체용 구조를 나누는 계층 격자를 검토합니다. 균일 분포에서는 평균 후보 수가 좋아 보여도 전투 지역·스폰 지점 같은 핫스팟에서는 한 셀의 후보가 수천 개가 될 수 있습니다. 셀 크기를 줄이면 핫스팟을 분할할 수 있지만 큰 객체와 해시 버킷 수, 메모리가 늘어납니다.

해시 함수가 같은 버킷을 반환하는 것은 실제 같은 공간 셀이라는 뜻이 아니므로, 버킷 안에서 (cellX, cellY, cellZ) 좌표를 비교하고 목록을 분리해야 합니다. 음수 좌표는 언어의 정수 나눗셈이 0 방향으로 절삭되는지 바닥으로 내리는지 확인해, 예를 들어 -1이 0번 셀에 잘못 들어가지 않도록 floor division을 사용하겠습니다.

중복·수명·갱신

큰 객체가 여러 셀에 등록되면 한 조회에서 같은 객체가 여러 번 후보로 나옵니다. 객체 ID와 조회 세대의 방문 집합으로 중복을 제거하고, 최종 거리·형상 검사는 한 번만 수행합니다. 이동 갱신과 조회가 동시에 일어나면 틱 시작 스냅샷, RCU 스타일의 읽기 참조, 위치 버전을 사용해 한 검사에서 이전 셀과 새 셀을 혼합하지 않게 합니다. 삭제된 객체가 셀 목록에 남는 경우도 있으므로 목록 항목의 세대와 실제 객체 수명을 확인합니다. 테스트는 균일 분포·핫스팟·경계·음수 좌표·고속 이동·다중 셀 객체·큰 조회 반경을 포함합니다. 후보 수, 실제 정밀 검사 수, 셀 조회 수, 이동 갱신 비용, 중복률, p99와 메모리 상한을 함께 측정하겠습니다. AOI와 충돌 후보가 같은 인덱스를 써도 필터·수명·갱신 주기가 같다는 보장은 없으므로, 공통 인덱스가 두 요구를 모두 만족하는지 먼저 확인해야 합니다.

조회 반경이 셀 하나보다 훨씬 크면 셀을 많이 해시하는 비용과 후보 수가 줄어드는 이점을 함께 계산해야 합니다. 고속 객체는 중심 셀이 바뀌지 않아도 이동 경계가 여러 셀을 가로지를 수 있으므로 선형 병진이면 시작·끝 형상을 포함한 swept 경계 전체를 사용하고, 회전·곡선 운동은 중간 궤적도 보수적으로 포함하며, 오래된 항목은 세대와 정리 시점으로 제한하겠습니다. 공간 해시가 AOI와 충돌 broad phase에 함께 쓰여도 반경·갱신 주기·수명 요구는 다를 수 있습니다. 공통 인덱스에서 후보를 얻어 각 소비자가 필터링하는 방식과 별도 인덱스를 두는 방식을 p99와 메모리로 비교하겠습니다. 셀 크기 변경은 인덱스 전체 재구축이나 점진적 이중 운영이 필요할 수 있습니다. 한 틱 동안 이전 격자와 새 격자를 함께 조회해 후보 누락을 막고, 결과를 비교한 뒤 새 구조로 전환할 수 있지만 중복 후보를 제거해야 합니다.

운영 중 전환이라면 객체 세대와 인덱스 버전을 후보에 넣어 서로 다른 구조의 항목을 혼동하지 않겠습니다. 공간 해시의 최악 비용은 한 핫스팟에 모든 객체가 몰릴 때 나타납니다. 해당 지역만 하위 셀로 분할하거나 별도 동적 트리로 승격할 수 있지만, 승격·강등의 기준이 흔들리면 갱신 비용이 더 커집니다. 후보 p99와 이동 갱신 p99를 함께 보고, 평균 개선이 최악 지연을 악화시키지 않는지 확인하겠습니다.