21. 관심 영역(AoI) 관리와 대역폭 최적화

난이도: 상

모범답안

1. AoI 의 필요성

서버가 존의 모든 엔티티 상태를 모든 접속자에게 매 틱 보내면 메시지 수가 플레이어 수 N 에 대해 O(N²) 로 증가한다. 실제로 한 플레이어에게 의미 있는 것은 그의 화면·상호작용 반경 안에 있는 소수 엔티티뿐이다. AoI 는 각 관측자에게 "관련 있는" 엔티티 집합만 골라 동기화하는 기법으로, 대역폭·직렬화·CPU 를 "평균 이웃 수" 규모로 낮춰 O(N·k)(k≪N)로 만든다. MMO 확장성의 핵심 축이다.

2. 자료구조 비교

• 고정 격자(uniform grid): 월드를 셀로 나눠 각 엔티티를 셀에 등록. 관측자의 AoI = 자기 셀 + 인접 셀들의 엔티티. 진입/이탈은 엔티티가 셀을 넘을 때만 계산 → 갱신이 국소적이고 O(1)에 가깝다. 셀 크기가 AoI 반경과 맞아야 효율적이다. 단점: 밀집 지역(보스/이벤트)에서 한 셀에 몰리면 그 셀이 핫스팟이 된다.
• 십자 링크드 리스트(cross-linked list): x축·y축으로 정렬된 이중 연결 리스트를 유지하며 이동 시 이웃만 스왑. 정밀 반경 판정에 유리하나 구현이 복잡하고 축별 정렬 유지 비용이 있다.
• 계층 구조(쿼드트리/옥트리, 계층 격자): 밀도가 불균일할 때 적응적으로 분할. 넓은 시야·불균등 분포에 유리하지만, 이동이 잦으면 트리 재구성 비용이 커서 실시간 갱신엔 격자보다 불리한 경우가 많다.
• 실무 결론: 이동이 잦은 게임엔 고정/계층 격자가 가장 흔하다(갱신 국소성). 넓은 관측·불균등 분포엔 격자+동적 셀 분할을 섞는다.

3. enter/leave 이벤트와 flapping

엔티티가 셀 A→B 로 넘어가면, 그 엔티티를 보던 관측자 집합과 새로 보게 될 집합의 차집합만 계산해 leave/enter 를 발행한다(전수 비교 불필요). 경계에서 앞뒤로 진동하면 매번 enter/leave 폭풍이 나므로, 히스테리시스를 준다: 들어올 때 반경 R, 나갈 때 R+여유(Δ)를 적용해 경계에서의 떨림을 흡수하거나, 셀 전환에 최소 유지 시간을 둔다.

4. 대역폭 절감 기법

• LOD 차등: 가까운 엔티티는 고빈도·고해상도, 먼 엔티티는 저빈도·저해상도로 갱신. 위치는 자주, 장비 외형 같은 정적 데이터는 진입 시 1회.
• 델타 압축: 마지막으로 보낸 상태 대비 변한 필드만 비트마스크와 함께 전송, 안 바뀐 필드 생략. 좌표는 양자화·상대 인코딩.
• 대역폭 예산 + 우선순위 큐: 관측자별 초당 바이트 예산을 두고, 중요도(거리, 전투 관련성, 최근 변화량) 점수로 우선순위 큐를 만들어 예산 안에서 상위부터 전송. 예산 초과분은 다음 틱으로 미룸(관련 없는 먼 엔티티는 자연히 저빈도).
• 관측자 집합 변경: 새로 진입한 엔티티는 전체 스냅샷 1회(baseline), 이후는 증분(델타). 이탈은 destroy 이벤트 1회.

5. 틱과의 결합

매 틱 전수 재계산은 O(N²) 로 회귀하므로 금지. 대신 변경 이벤트 기반: 엔티티가 셀 경계를 넘는 순간에만 AoI 집합을 갱신하고, 매 틱엔 이미 계산된 관측자 집합에 대해 델타만 직렬화한다. AoI 갱신·직렬화가 무거우면 시뮬레이션 스레드와 분리(읽기 전용 스냅샷을 넘겨 별도 워커가 직렬화)하거나, 관측자별 전송을 여러 틱에 분산(스태거링)해 한 틱에 몰리지 않게 한다.

면접 포인트

• O(N²) → O(N·k) 로 낮추는 것이 AoI 의 본질.
• 이동 잦은 환경에서 격자(갱신 국소성)가 트리보다 유리한 이유.
• 대역폭 예산 + 우선순위 + 델타 압축의 결합, flapping 히스테리시스.