문제 21 — 관심 영역(AoI) 관리와 대역폭 최적화

대규모 심리스 MMORPG 존 서버에서 한 존에 수천 명의 플레이어와 NPC가 있다. 모든 엔티티의 상태(위치/애니메이션/HP 등)를 모든 접속자에게 매 틱 보내면 대역폭과 CPU가 O(N²)로 폭발한다.

다음을 설명하라.

1. 관심 영역(Area of Interest, AoI) 이란 무엇이며, 왜 필요한가? "각 플레이어에게 관련 있는 엔티티만 동기화한다"는 원칙을 O(N²) 문제와 연결해 설명하라.

2. AoI 를 구현하는 대표적 자료구조/알고리즘을 비교하라:

   • 고정 격자(uniform grid) / 셀 기반
   • 십자 링크드 리스트(cross-linked list) 방식
   • 스팬/버킷 정렬, 쿼드트리 등 계층 구조 각각의 진입/이탈 이벤트 계산 비용과 이동이 잦은 환경에서의 트레이드오프를 논하라.

3. 엔티티가 이동할 때 발생하는 진입(enter)/이탈(leave) 이벤트를 어떻게 효율적으로 계산하는가? 경계에서 왔다 갔다 할 때의 떨림(flapping) 을 줄이는 방법(히스테리시스/여유 반경)을 설명하라.

4. 대역폭을 더 줄이는 기법을 설명하라:

   • 거리/중요도 기반 업데이트 빈도·해상도 차등(LOD)
   • 상태 델타 압축과 관련 없는 필드 생략
   • 우선순위 큐 기반 대역폭 예산 배분
   • 관측자 집합 변경 시 스냅샷 vs 증분 전송

5. AoI 계산을 게임 틱과 어떻게 결합하는가? 매 틱 전수 재계산 대신 사용하는 기법(변경분만 처리, 셀 이동 시에만 갱신)과, 이 계산이 시뮬레이션을 막지 않게 하는 방법을 논하라.