視野（AOI）計算量暴增（N²） Area-of-interest explosion

原因 ID sp-aoi · 主要負責 遊戲開發團隊（伺服器開發）

若要判斷誰能看到誰而讓所有人兩兩比較，人數變成 10 倍時，運算量會變成 100 倍。

為什麼 所有角色兩兩比較距離，或即使切成格狀（grid），一個格子附近仍擠了數百人 → 於是 100 人約比較 1 萬次，1,000 人約 100 萬次 → 畫面上 在世界王、攻城戰等人潮聚集的地方 tick 時間暴增，出現慢動作、卡頓

症狀: 慢動作, 卡頓
因素: 停滯
誰會遇到: 特定地點／頻道, 整個伺服器
何時: 人潮湧入時
負責單位: 主要負責 遊戲開發團隊（伺服器開發）
遊戲開發團隊要做的事: 以格狀或區塊切分、只比較附近的對象；遠處的對象降低更新頻率；限制一個人能看到的人數上限。
數值參考: 假設距離比較加上「看得見／看不見」清單的更新，每兩人一對要花 0.1µs（千萬分之一秒），1,000 人（約 100 萬對）時一個 tick 要花 100ms。這是 20 tick 預算（50ms）的 2 倍。
圖表上: 隨人數／負載上升 · 伺服器 tick 時間、聚集在同一處的人數
查看位置: 把各 zone／頻道的人數與 tick 時間放在同一張圖表上，並看 tick 中視野計算所花時間的單獨量測值。沒有單獨量測時，用 perf top -p 看遊戲處理程序各函式的 CPU 占比
符合的跡象: 同一處的人數變成 2 倍時 tick 時間增加將近 4 倍，視野與距離計算函式占了大部分 CPU 時間
不符合的跡象: tick 時間與人數成正比增加，或傳送、序列化函式的占比很大時，是「廣播量暴增」或「序列化與壓縮的成本」
確認方式: 需要遊戲伺服器／用戶端的 log 與指標

出處

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
NetGames 2006 論文（作者公開版本）。量測所有配對距離的方式在人數增加時無法負荷；切成正方形格子時只需檢查周圍 9 個格子
Replication Graph in Unreal Engine Epic Games
為每個 actor 逐一檢查所有連線的預設方式，在人數與 actor 很多時會成為伺服器 CPU 瓶頸；MMORPG 等會把世界切成格狀，重複使用每個格子的清單
perf-top(1) — Linux manual page perf
依函式（symbol）即時顯示執行中處理程序（-p）或執行緒（-t）的 CPU 使用占比