시야(AOI) 계산 폭증 (N²) Area-of-interest explosion

원인 ID sp-aoi · 주 담당 게임개발팀·서버 개발

누가 누구를 볼 수 있는지 모두끼리 비교하면, 인원이 10배가 될 때 계산은 100배가 됩니다.

왜 모든 캐릭터끼리 거리를 비교하거나, 격자(그리드)로 나눠도 한 셀 근처에 수백 명이 몰림 → 그러면 100명이면 약 1만 번, 1,000명이면 약 100만 번 비교 → 화면에서는 월드 보스·공성전처럼 몰린 곳에서 틱이 폭증해 슬로우모션·뚝뚝 끊김

증상: 슬로우모션, 뚝뚝 끊김
요인: 정체
누가 겪나: 특정 장소·채널, 서버 전체
언제: 사람이 몰릴 때
담당: 주 담당 게임개발팀·서버 개발
게임개발팀 할 일: 격자·구역으로 나눠 근처만 비교, 멀리 있는 대상은 드물게 갱신, 한 사람이 보는 인원에 상한.
수치 감각: 거리 비교와 보임·안 보임 목록 갱신을 합쳐 두 사람 한 쌍마다 0.1µs(1천만 분의 1초)로 잡으면, 1,000명(약 100만 쌍)이면 한 틱에 100ms. 20틱 예산(50ms)의 두 배입니다.
그래프에서는: 인원·부하를 따라 오름 · 서버 틱 시간, 한곳에 모인 인원
확인할 곳: 존·채널별 인원과 틱 시간을 같은 그래프에 놓고 틱 안에서 시야 계산에 쓴 시간을 따로 잰 값. 따로 잰 값이 없으면 perf top -p로 게임 프로세스의 함수별 CPU 비중
이러면 맞음: 한곳에 모인 인원이 2배가 될 때 틱 시간이 4배 가까이 늘고 시야·거리 계산 함수가 CPU 시간의 대부분을 차지함
이러면 아님: 틱 시간이 인원에 비례해 늘거나 전송·직렬화 함수의 비중이 크면 브로드캐스트 폭증이나 직렬화·압축 비용 쪽
확인 수단: 게임 서버·클라이언트의 로그·지표가 필요

출처

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
NetGames 2006 논문(저자 공개본). 모든 쌍의 거리를 재는 방식은 인원이 늘면 감당하지 못하고 정사각형 격자로 나누면 주변 9개 셀만 확인
Replication Graph in Unreal Engine Epic Games
액터마다 모든 접속을 따져 보는 기본 방식은 인원·액터가 많으면 서버 CPU 병목, MMORPG 등은 월드를 격자로 나눠 셀별 목록을 재사용
perf-top(1) — Linux manual page perf
실행 중인 프로세스(-p)나 스레드(-t)의 CPU 사용 비중을 함수(심볼)별로 실시간 표시