Explosão N² no cálculo de visibilidade (AOI) Area-of-interest explosion

ID da causa sp-aoi · Responsável principal Desenvolvimento do servidor (Equipe de desenvolvimento)

Abrir o card interativo, com figuras e simulações →

Se o servidor compara todos com todos para saber quem pode ver quem, quando o número de jogadores aumenta 10 vezes, o cálculo aumenta 100 vezes.

Por quê Compara a distância entre todos os personagens, ou, mesmo dividindo em grade (grid), centenas de jogadores se juntam perto de uma célula → Efeito Com 100 jogadores são cerca de 10 mil comparações; com 1.000, cerca de 1 milhão → Na tela Em aglomerações, como world boss e guerra de castelo, o tick dispara: câmera lenta e engasgos

Sintomas: Câmera lenta, Engasgos
Fatores: Paralisação
Quem é afetado: Local ou canal específico, Servidor inteiro
Quando: Quando junta muita gente
Responsável: Responsável principal Desenvolvimento do servidor (Equipe de desenvolvimento)
O que fazer (Equipe de desenvolvimento): Dividir em grade ou setores e comparar só com quem está perto, atualizar com menos frequência quem está longe, limitar o número de jogadores que cada um vê.
Números de referência: Somando a comparação de distância e a atualização das listas de quem vê e quem não vê, se cada par de jogadores custa 0,1 µs (um décimo de milionésimo de segundo), 1.000 jogadores (cerca de 1 milhão de pares) dão 100 ms por tick. É o dobro do orçamento de 20 ticks (50 ms).
No gráfico: Sobe com a carga · Tempo de tick do servidor, jogadores reunidos num só lugar
Onde olhar: Jogadores por zona ou canal e tempo de tick no mesmo gráfico, com o tempo gasto no cálculo de visibilidade medido à parte dentro do tick. Sem essa medição, a fatia de CPU por função do processo do jogo com perf top -p
Confirma se: Quando o número de jogadores reunidos num lugar dobra, o tempo de tick quase quadruplica, e as funções de visibilidade e de distância ocupam a maior parte do tempo de CPU
Descarta se: Tempo de tick crescendo na proporção do número de jogadores, ou funções de envio e serialização com fatia grande: explosão de broadcast ou custo de serialização e compressão
Como verificar: Exige logs e métricas do servidor ou do cliente do jogo

Fontes

Comparing Interest Management Algorithms for Massively Multiplayer Games ACM
Artigo do NetGames 2006 (versão publicada pelos autores). Medir a distância de todos os pares não aguenta o aumento de jogadores; com uma grade quadrada, basta verificar as 9 células em volta
Replication Graph in Unreal Engine Epic Games
O modelo padrão, que avalia todas as conexões para cada ator, vira gargalo de CPU no servidor com muitos jogadores e atores; MMORPGs e similares dividem o mundo em grade e reutilizam as listas por célula
perf-top(1) — Linux manual page perf
Mostra em tempo real a fatia de uso de CPU por função (símbolo) de um processo (-p) ou thread (-t) em execução

Veja também

Mesma camada: L9 Processo do jogo no servidor

Mesmo sintoma (Câmera lenta) em outras camadas

Espiral de recuperação do timestep fixo L1 Processo do jogo no cliente
Desbalanceamento do load balancer e health check enganoso L5 Equipamentos de rede do data center
Excesso de threads e troca de contexto L7 SO do servidor (kernel)
Throttling de CPU em contêiner (cota do CFS) L7 SO do servidor (kernel)
Picos de latência pelo gerenciamento de energia do servidor (C-states e ajuste de frequência) L7 SO do servidor (kernel)
Tarefas agendadas L7 SO do servidor (kernel)
Mudança de desempenho após atualização de SO, kernel, driver ou firmware L7 SO do servidor (kernel)
Envio bloqueante por causa de cliente lento L8 Sockets e protocolos

Ver o card interativo, com figuras e simulações