시티즈:스카이라인이나 심시티 같은 도시 시뮬레이션 게임을 확인해보면 수백, 수천 개의 시민과 건물이 같은 시각에 움직이는데도 게임이 스탑되지 않습니다. 이번 포스팅에서는 이게 어떻게 불가능하지 않은 일인지, LOD 시뮬레이션과 공간 분할의 개념을 이용해서 직접 구현해보며 확인해보겠습니다.
1. 왜 유닛을 서로 비교하면 안될까?
가장 심플한 방법은 매 틱마다 모든 유닛이 다른 모든 유닛과의 관계(거리, 충돌, 영향 범위)를 체크하는 것입니다.
문제는 이 방법이 유닛 수의 제곱에 비례해서 느려진다는 것입니다. 유닛이 100개라면 비교 횟수는 약 1만 번에 불과하지만 1000개가 되는 순간 100만 번으로 늘어나게 됩니다. 실제로 간단한 프로토타입을 이용해 이 방식을 직접 구현해 봤더니 유닛 200개까지는 상태가 괜찮다가 800개를 넘어가는 순간에는 눈에 띄게 현저히 느려진 것을 체크할 수 있었습니다.
2. 공간을 분할해 비교 대상을 줄인다
이 문제를 해결할 수 있는 가장 대표적인 방식이 공간 분할입니다. 전체 맵을 일정 크기의 그리드(격자)로 나누고 각 유닛을 자신이 속한 칸에 등록해두는 방식입니다.
이렇게 하게 되면 특정 유닛 주변의 다른 유닛을 찾게 될 때 맵 전체를 관찰할 필요가 없고 그 유닛이 속한 칸과 가까운 칸만 체크하면 됩니다. 유닛 분포가 밀집되어 있지 않은 경우에는 쿼드트리처럼 밀집된 영역을 재귀적으로 더 잘게 쪼개는 구조를 쓰기도 합니다.
3. 직접 구현해서 성능 비교
파이썬으로 그리드 기반 공간 분할을 직접 짜서 브루트포스 방식과 처리 속도를 비교하는 벤치마크를 시뮬레이션해봤습니다. 1000×1000 크기인 가상의 맵에 유닛을 100개부터 3200개까지 늘리면서 반경 15 안에 있는 이웃을 모두 찾는 데에 걸리는 시간을 두 방식으로 각각 체킹하였습니다.(참고로, 두 방법이 찾아낸 이웃 쌍의 개수가 정확히 일치하는 지도 매번 검증 했습니다.) 결과는 아래의 그래프와 같습니다.
유닛이 100개일 때는 두 방법 모두 1밀리초 이하로 체감 차이가 없었지만, 3200개로 늘리자마자 브루트포스는 867밀리초, 격자 방식은 16밀리초로 약 54배 정도 차이가 났습니다. 브루트포스는 유닛 수가 늘어날 수록 처리 시간이 위로 꺾이며 올라갔고 그리드 방식은 비교적 완만한 곡선을 그리는 것으로 확인되었습니다.
4. 똑같이 자주 계산할 필요는 없다
공간 분할과 별개로, 화면에 멀리 있다거나 플레이어 시야 밖에 있는 유닛까지 매 틱 정밀하게 계산 할 필요는 절대 없습니다.
이런 유닛은 갱신 주기를 낮추거나 계산을 단순화하는 LOD(Level of Detail) 시뮬레이션으로 처리되는 경우가 많습니다. 도시 시뮬레이션 장르로 유명한 게임 개발사들이 공개한 개발 블로그를 확인해보면 관찰자로부터 멀리 떨어진 시민이나 차량은 실제 경로 탐색 대신 비교적 단순한 이동으로 대체해 계산량을 크게 줄인다는 내용을 확인할 수가 있습니다.
5. 그리드 크기는 왜 중요한가?
직접 실험을 해보면서 예상 밖으로 중요했던 것이 그리드 한 칸의 크기였습니다. 처음에는 칸을 아주 잘게 잘게 나눌 수록 무조건 속도가 빨라질 것으로 예상하였는데 실제로 시뮬레이션을 돌려보니 정반대의 문제를 먼저 마주하게 되었습니다.
칸이 탐지 반경(15)보다 작은데 주변 3×3칸만 확인하도록 짜두면, 반경 안에 있는 유닛인데도 그보다 먼 칸에 있다는 이유로 아예 찾지 못하는 버그가 생겼습니다. 체크 범위를 그리드 크기에 맞춰서 자동으로 넓히도록 고치고 나서야 두 방법의 결과가 정확히 일치하는 것을 확인할 수 있었습니다.
버그를 고친 뒤에는 칸 크기를 3에서부터 300까지 바꿔가면서 재측정하자 아래 그래프처럼 뚜렷한 U자 곡선이 나왔습니다. 그리드를 너무 잘게 나누면(3~10) 한 유닛 주변에 확인해야 할 칸 수 자체가 늘어나서 느려지고 반대로 너무 크게 잡으면(140 이상) 한 칸에 유닛이 몰려서 브루트포스와 비슷해집니다. 이번 실험에서는 칸 크기 20(탐지 반경의 약 1.3배)일 때 4.6밀리초로 가장 빨랐습니다. 하지만, 이 최적값은 유닛 밀도와 탐지 반경에 따라 달라지기 때문에, 정확한 숫자보다는 “탐지 반경과 비슷하거나 살짝 큰 정도에서 최적점이 생긴다”는 경향 자체를 기억해두는 것이 더 실용적이라고 말할 수 있습니다.
6. 한계와 주의할 점
하지만, 제가 직접 제작한 프로토타입은 실제 상용 게임에 비해 매우 단순화된 버전입니다. 실제 게임들은 많은 스레드에 계산을 나눠 분산 처리하고 그리드 크기도 상황에 맞춰 동적으로 처리하는 등 훨씬 정교한 최적화를 함께 사용합니다.
공간 분할과 LOD만으로는 모든 성능 문제가 해결되는 것도 아니고 오히려 잘못 설계했을 때 그리드 경계에 걸친 유닛을 놓쳐버리는 버그가 생기기도 한다는 점은 직접 체험해보고 나서야 체감했습니다.
7. 마치며
수백 개의 유닛이 같은 시각에 움직이는 도시 시뮬레이션 게임의 숨겨진 비밀은 대단한 하드웨어가 아닌 필요한 계산만 필요한 만큼만 하도록 설계하는 것이라 할 수 있습니다.
공간을 분할하여 비교 대상을 줄이고 눈에 잘 안 보이는 부분은 적당하게 단순화하는 것이죠. 복잡해 보이는 시뮬레이션도 원리를 뜯어 보면 의외로 상식적인 절약에서 시작합니다. 작은 규모의 게임을 직접 제작하는 입장이라면 유닛 수가 수십 개를 넘어가는 순간부터 공간 분할을 적용하기만 성능 차이를 크게 느낄 수 있다는 것을 이번 실험으로부터 확인할 수 있었습니다. 이번 글이 도움이 되었기를 바라며 이만 마치겠습니다.