공간 분할, 데이터 지향 설계, SIMD 최적화
RTS, 배틀로얄 같은 대규모 게임에서는 많은 유닛이 동시에 움직이며, 각 유닛은 주변 적을 탐지하거나 공격 범위를 계산해야 합니다. 이러한 거리 기반 공간 쿼리가 매 프레임마다 수행되면서 성능 병목이 발생합니다.
이 프로젝트는 1만 개 이상의 객체를 실시간으로 처리할 수 있는 고성능 공간 쿼리 시스템을 구축하는 것을 목표로 합니다.
단순 알고리즘 개선을 넘어, 자료구조 선택, 메모리 레이아웃 설계, CPU 하드웨어 활용까지 전 과정을 최적화했습니다.
나이브 방식 대비 2배 이상의 성능 향상을 달성하여, 1만 개 이상의 객체를 실시간으로 처리할 수 있게 되었습니다.
가장 기본적인 Naive 방식은 플레이어 주변의 대상을 찾기 위해 월드에 존재하는 모든 유닛(N명)을 전수 조사합니다. 비록 플레이어 1명을 대상으로 한 쿼리일지라도, 유닛이 1만 명으로 늘어나면 매 프레임 1만 번의 거리 계산이 필요하며, 이러한 호출이 늘어날수록 CPU 부하는 선형적으로 증가하여 성능 병목의 원인이 됩니다.
// Naive 방식: 주변 유닛을 찾기 위해 전체 리스트를 순회 for (size_t i = 0; i < allUnits.size(); ++i) { float distSq = CalculateDistanceSq(playerPos, allUnits[i].pos); if (distSq < radiusSq) { // 결과 저장 } }
std::vector<GameObject*>는 포인터 배열이라 객체의 실제 데이터가 메모리에 흩어져 있습니다. CPU가 데이터를 읽을 때 메모리를 여기저기 점프해야 해서(포인터 체이싱) 캐시 효율이 떨어지고, 결과적으로 대규모 연산에서 성능 병목이 발생합니다.
// 포인터 배열: 주소값은 연속적이나, 실제 데이터는 메모리 곳곳에 흩어져 있음 std::vector<GameObject*> Objects; for (auto* Obj : Objects) { // 1. Obj 역참조시 메모리가 흩어져 있어 캐시 미스 확률 높음 // 2. GetPosition() 호출을 위해 메모리 점프 float dist = glm::distance(PlayerPos, Obj->GetPosition()); }
알고리즘 최적화 외에도 매 루프마다 발생하는 작은 오버헤드들이 대규모 데이터에서는 큰 성능 저하를 일으킵니다.
std::vector에 push_back을 반복적으로 호출하면, 내부 용량이 부족할 때마다 더 큰 메모리를 새로 할당하고 기존 데이터를 전체 복사합니다. 1만 개의 객체를 처리할 때 이러한 재할당이 수십 번 발생하면, 단순한 데이터 추가 작업만으로도 상당한 시간이 소요됩니다.
이를 해결하기 위해 미리 예상되는 크기만큼 reserve()로 공간을 확보하여 불필요한 재할당을 방지했습니다.
알고리즘을 최적화한 후에도 CPU의 하드웨어 기능을 활용하지 않으면 성능 향상에 한계가 있습니다.
일반적인 코드는 한 번에 유닛 1명의 거리만 계산합니다. 하지만 SSE(SIMD 명령어)를 사용하면 128비트 레지스터에 4명의 좌표 데이터를 동시에 로드하여, 단일 명령어로 4개의 거리를 병렬로 계산할 수 있습니다.
예를 들어 1만 명의 유닛을 처리할 때, 일반 코드는 1만 번의 연산이 필요하지만 SSE를 사용하면 약 2,500번의 연산으로 줄어들어 이론상 4배 가까운 성능 향상이 가능합니다.
Grid 공간 분할을 적용하여 탐색 범위를 플레이어가 속한 셀과 인접한 셀(K개)로 제한했습니다. 이제 전체 유닛 수(N)가 아무리 많아져도 실제 쿼리 연산량은 플레이어 주변의 유닛 밀도(K)에만 영향을 받게 되어 실질적인 연산 비용을 상수 시간 수준으로 관리할 수 있게 되었습니다.
각 셀의 유닛을 저장하는 자료구조로 세 가지 옵션을 고려했습니다:
결론: 매 프레임 격자를 재구축하고 빈번한 쿼리를 수행하는 구조이기 때문에, 삽입/삭제보다 순회 성능과 캐시 효율이 중요하므로 std::vector를 선택했습니다.
/** * x, z : 쿼리 중심 좌표 * InRadius : 탐색 반경 */ const void OptimizedGridVectorRebuild::GetNeighborGridable(float x, float z, float InRadius, std::vector<QueryResult>& OutResult) { OutResult.clear(); // 1. 탐색할 셀 범위 계산 int CellSearchRange = static_cast<int>(std::ceil(InRadius / CellSize)); float RadiusSq = InRadius * InRadius; int CenterCol = static_cast<int>(x / CellSize); int CenterRow = static_cast<int>(z / CellSize); // 2. 주변 셀만 순회 for (int R = CenterRow - CellSearchRange; R <= CenterRow + CellSearchRange; ++R) { if (R < 0 || R >= Rows) continue; int RowOffset = R * Cols; for (int C = CenterCol - CellSearchRange; C <= CenterCol + CellSearchRange; ++C) { if (C < 0 || C >= Cols) continue; auto& Cell = Cells[RowOffset + C]; if (Cell.Actors.empty()) continue; // [셀 내 유닛 정밀 검사] // ... (아래 SIMD 로직으로 이어짐) } } }
유닛의 모든 정보(위치, HP, 이름, 상태 등)를 하나의 객체(GameObject)에 담고, 그 객체의 포인터를 배열로 관리했습니다.
Obj->GetPosition() 호출 시 매번 메모리 여기 저기를 점프해야 합니다. 또한 각 객체의 실제 메모리는 흩어져 있어 캐시를 활용하기 힘듭니다.
결과적으로 대규모 연산에서 캐시 미스가 빈번하게 발생하여 성능 병목이 됩니다.
// AoS (Array of Structures) // 유닛이 각자 객체 형태로 존재하며, 포인터를 통해 쿼리를 수행 for (auto* Obj : Objects) { static std::vector<IGridable*> QueryResults; QueryResults.clear(); // 문제 1: Obj->GetPosition() 호출 시 포인터 체이싱 발생 // 문제 2: 객체 내 연산에 불필요한 데이터(HP, Name 등)가 캐시 라인을 점유함 int QueryRadius = 1; CurrentGrid->GetNeighborGridable(Obj->GetPosition(), QueryRadius, QueryResults); }
연산에 필요한 위치 데이터(X, Z)만 따로 추출하여 연속된 배열(std::vector<float>)로 재구성했습니다. 유닛 객체를 찾아가는 대신, 데이터가 모여있는 배열을 직접 순회합니다.
포인터의 역참조가 제거되고, 필요한 데이터만 로드되어 캐시 효율이 향상됩니다.
// SoA (Structure of Arrays) // 연산에 필요한 핵심 데이터(X, Z)만 배열로 모아 선형적으로 처리 for (int i = 0; i < Objects.size(); i++) { // 1. 역참조 없이 연속된 메모리 배열(pX, pZ)에서 직접 읽기 (캐시 히트율 증가) float CurrentX = pX[i]; float CurrentZ = pZ[i]; static std::vector<QueryResult> QueryResults; QueryResults.clear(); // 2. 불필요한 재할당 방지를 위한 reserve 활용 QueryResults.reserve(FinalReserve); // 3. 인자값으로 좌표를 직접 전달하여 포인터 역참조 제거 OptimizedVectorGrid->GetNeighborGridable(CurrentX, CurrentZ, QueryRadius, QueryResults); }
사전에 크기를 예약하지 않으면 데이터가 추가될 때마다 재할당이 발생합니다. 기존 데이터를 커진 새 공간으로 전체 복사하여 많은 비용이 들게 됩니다.
따라서 그리드를 초기화할 때, 각 셀의 vector 들에게 셀 당 평균 밀도를 계산해 공간을 확보했습니다.
// OptimizedGridVectorRebuild 생성자 로직 OptimizedGridVectorRebuild::OptimizedGridVectorRebuild(float InWidth, float InHeight, float InCellSize) { Cells.resize(Rows * Cols); // 셀당 평균 밀도 계산 (예: 1만 명 / 100개 셀 = 셀당 100명) size_t AverageDensity = World::MaxSpawnCount / (Rows * Cols); for (auto& cell : Cells) { // 런타임 중 push_back 시 메모리 재할당이 발생하지 않도록 미리 예약 cell.PosX.reserve(AverageDensity); cell.PosZ.reserve(AverageDensity); cell.Actors.reserve(AverageDensity); } }
또한, 쿼리 결과를 받아올 QueryResult vector는 static으로 선언해 매번 새로운 벡터를 만들지 않고, 내가 쿼리할 반경 내에 몇 명이 있을지 기대값을 미리 계산하여 공간을 확보했습니다.
void World::QueryTestOptimizedVectorRebuild() { ... float WorldArea = GridWidth * GridHeight; float UnitDensity = Objects.size() / WorldArea; // 유닛 밀도 float QueryArea = (2 * QueryRadius) * (2 * QueryRadius); //원형 -> 사각형 float MarginRatio = 2.0f; // 여유 확보 비율 int FinalReserve = static_cast<size_t>(UnitDensity * QueryArea * MarginRatio); // 특정 범위에 몇 명의 유닛이 있을 지 기대값 ... for (int i = 0; i < Objects.size(); i++) { ... static std::vector<QueryResult> QueryResults; QueryResults.clear(); QueryResults.reserve(FinalReserve); ...
일반적인 연산은 유닛 1명의 거리를 계산하기 위해 여러 단계의 명령어를 거치지만, SSE를 사용하면 128비트 레지스터에 4명의 좌표(float 4개)를 동시에 실어 한 번의 명령어로 처리합니다.
1만 명을 처리할 때 약 2,500번의 연산으로 줄어들어, 이론상 최대 4배의 성능 향상이 가능합니다.
const void OptimizedGridVectorRebuild::GetNeighborGridableWithSSE(float X, float Z, float InRadius, std::vector<QueryResult>& OutResult) { ... // SIMD 비교를 위한 레지스터 준비 __m128 vCenterX = _mm_set1_ps(X); __m128 vCenterZ = _mm_set1_ps(Z); __m128 vRadiusSq = _mm_set1_ps(RadiusSq); int CenterCol = static_cast<int>(X / CellSize); int CenterRow = static_cast<int>(Z / CellSize); // 셀 탐색 루프 for (int R = CenterRow - CellSearchRange; R <= CenterRow + CellSearchRange; ++R) { if (R < 0 || R >= Rows) continue; int RowOffset = R * Cols; for (int C = CenterCol - CellSearchRange; C <= CenterCol + CellSearchRange; ++C) { if (C < 0 || C >= Cols) continue; auto& Cell = Cells[RowOffset + C]; const size_t Count = Cell.Actors.size(); if (Count == 0) continue; const float* pX = Cell.PosX.data(); const float* pZ = Cell.PosZ.data(); IGridable* const* pActors = Cell.Actors.data(); size_t i = 0; // SIMD 로 실제 반경 내 유닛만 정밀 선별 for (; i + 3 < Count; i += 4) { // 유닛 4명의 좌표 로드 __m128 PackedX = _mm_loadu_ps(&pX[i]); // 시작 주소부터 128비트(float * 4) 로드 __m128 PackedZ = _mm_loadu_ps(&pZ[i]); // _ps = Packed Single 32bit 4개로 취급 // dx, dz 계산 (내 위치 - 유닛 위치) __m128 vDx = _mm_sub_ps(vCenterX, PackedX); __m128 vDz = _mm_sub_ps(vCenterZ, PackedZ); // 거리 제곱 계산: (dx*dx + dz*dz) __m128 vDistSq = _mm_add_ps(_mm_mul_ps(vDx, vDx), _mm_mul_ps(vDz, vDz)); // 공격 반경과 비교하여 마스크 생성 (vDistSq < vRadiusSq) __m128 vMask = _mm_cmplt_ps(vDistSq, vRadiusSq); // 32bit 를 모두 0 or 1 값으로 채움 int Bitmask = _mm_movemask_ps(vMask); // 32bit 를 1bit 로 압축 0 or 1 총 4bit ex) 1010 -> int(10) // 범위 안에 한 명이라도 있다면 실행 if (Bitmask != 0) { for (int j = 0; j < 4; ++j) { if (Bitmask & (1 << j)) //ex) 1010 에서 오른쪽 0 부터 왼쪽으로 1칸씩 쉬프트하여 & 비교 { // i는 현재 4명 묶음의 시작 번호, j는 그 안에서의 순서(0-3) OutResult.push_back({ pActors[i + j], pX[i + j], pZ[i + j] }); } } } } // 4로 나누어 떨어지지 않는 데이터는 따로 처리 for (; i < Count; ++i) { float dx = x - pX[i]; float dz = z - pZ[i]; if (dx * dx + dz * dz < RadiusSq) { OutResult.push_back({ pActors[i], pX[i], pZ[i] }); } } } } }