Alguma vez você já jogou um game como Starcraft ou Supreme Commander e obteve uma mensagem de erro que dizia “Desync Detected” seguida do encerramento do jogo? Você quer saber o que isso significa? Ela deriva de arquiteturas de certos mecanismos comumente usados por games RTS.

Minha experiência nessa área vem de trabalhar com o mecanismo Supreme Commander no Gas Powered Games. Starcraft e Warcraft 3 tiveram bugs de dessincronização durante os períodos beta, por isso é seguro dizer que eles trabalham de forma similar. Para simplificar, eu vou discutir o mecanismo SupCom especificamente deste ponto em diante. Já encontrar semelhanças entre o mecanismo SupCom e outros jogos eu vou deixar como um exercício para o leitor. 🙂

Requisitos

Quais são os requisitos para o nosso jogo? Para ajudar a dar uma ideia, aqui está o trailer de anúncio do Supreme Commander 1 (2006).

Ele deve suportar 8 jogadores no modo multiplayer, na internet, com centenas de unidades por exército. Isso são milhares de unidades em um único jogo. Caramba! A típica arquitetura cliente-servidor FPS não irá funcionar claramente. Com tantas unidades, seriam necessárias várias unidades múltiplas que demandariam largura de banda além do aceitável.

Como podemos realizar essa façanha?

Mecanismo da arquitetura síncrona

Com uma arquitetura inflexível totalmente síncrona! Em um mecanismo síncrono, cada cliente executa exatamente o mesmo código na mesma frame rate. Em um game de 8 jogadores de SupCom, cada jogador tem uma cópia idêntica do estado do jogo e segue um caminho de código idêntico. Em vez de transferir mais informações por unidade de estado (posição, saúde etc.) através da rede, apenas o input do jogador precisa ser enviado. Se todos os jogadores têm um estado de jogo idêntico e processam a mesma entrada, então seu estado de saída também deve ser idêntico.

É o mesmo princípio dos replays instantâneos em muitos jogos, incluindo atiradores. Alguma vez você já se perguntou por que o tamanho dos arquivos de replays instantâneos é tão pequeno? É porque o arquivo de replay só precisa armazenar entradas de jogadores. Simplesmente execute novamente o jogo alimentando as entradas do arquivo de replay e você obterá o mesmo resultado. É por isso também que replays param de trabalhar3 quando o jogo é modificado e porque muitas vezes você não pode retrocedê-los4. É também por isso que alguns jogos RTS não permitem entrar em uma partida em andamento. Para um jogador entrar durante o jogo, todo o estado do jogo teria que ser sincronizados. Se ele tiver 3 mil unidades, é simplesmente demais.

Camadas

Dê uma olhada no vídeo, se você já não tiver feito isso. Em qual frame rate você acha que o jogo está sendo executado? A resposta correta é 10 quadros por segundo. Espere, o quê? Parece muito mais suave do que 10 fps. É e não é. O jogo realmente está sendo executado em duas frame rates separadas.

O mecanismo SupCom utiliza duas camadas – simulação e usuário. A camada de simulação é executada num valor fixo de 10 fps o tempo todo. Isto é o que você poderia considerar o “jogo real”. Todas as unidades, toda IA e toda a física estão atualizando dentro de uma função SimTick rodando em 10 hz. Cada SimTick precisa ser executado dentro de 100ms ou o jogo irá rodar em câmera lenta. Em um jogo multiplayer, se um jogador é totalmente incapaz de processar o SimTick em 100ms, então todos os outros jogadores podem se tornar um obstáculo e ter que esperar.

A camada de usuário é executada em full frame rate. Essa camada pode ser considerada como estritamente visual. Interface de usuário, renderização, animação, e até mesmo posição da unidade podem funcionar em um 60fps macio e sedoso. Cada UserTick atualiza em um delta de tempo variável, que é usado para interpolar o estado do jogo (tais como posições da unidade). É por isso que o jogo pode parecer suave quando é secretamente lento no background.

Determinismo

Espere um momento, os leitores espertos choraram! Se cada jogador está atualizando o estado do jogo independentemente, isso significa que a simulação do jogo deve ser totalmente determinista? Com certeza. Isso não é difícil? É. É ainda mais difícil no mundo moderno do multi-threading.

Uma grande dificuldade na criação de um jogo determinístico vem dos números com pontos flutuantes. Em vez de abordar este tema em profundidade prefiro citar aos leitores o artigo da fantástica Glenn Fiedler sobre o assunto – Floating Point Determinism.

Nos comentários, Elias discute especificamente o Supreme Commander. Definindo o cpu para seguir rigorosamente o padrão IEEE754 resolve o trabalho. Ele vem com um custo de desempenho e o jogo nunca pode executar uma operação com um resultado indefinido, mas você não deveria fazer isso de qualquer maneira agora, não é?

Latência inerente

Existem algumas desvantagens distintas para um jogo multiplayer síncrono. Além da complexidade da criação de uma simulação em massa determinística, existe alguma latência necessária na entrada. Fui até a forma como cada usuário em um jogo multiplayer está atualizando um estado de jogo idêntico, e eles só precisam processar a entrada. Isso significa que, para qualquer nova peça de entrada, ela não pode ser processada até que todos os clientes concordem em que local processá-lo!

Por exemplo, três jogadores – A, B e C – estão todos rodando em SimTick 1. Durante esse tempo, o Jogador A emite um comando de ataque. A interface do usuário pisca instantaneamente em resposta como atualizações UserTick a 60Hz. Em um jogo single player, esse comando de ataque seria processado em SimTick 2 (0-100ms de latência). No entanto, todos os três jogadores devem executar o comando durante o mesmo SimTick para obter os mesmos resultados. Em vez de tentar processar o comando em SimTick 2, o Jogador A envia um pacote de rede para os jogadores B e C, com os dados para executar em SimTick4 (200-300ms de latência). Isso dá tempo suficiente para que todos os jogadores recebam o comando. O jogo pode ser forçado a parar, se as informações de entrada não forem recebidas e /ou reconhecida de alguma forma. Eu não sei o que esse mecanismo era exatamente para SupCom, mas eu vou atualizar este artigo se eu conseguir descobrir. O número exato de SimTicks para o futuro para executar um comando pode ser dinamicamente determinado com base na topologia peer-to-peer5.

A latência do clique do jogador para unidade de resposta sempre vai ser no mínimo 0-100ms (o próximo SimTick 2). Isso pode ser mascarado de algumas formas. A resposta da interface do usuário, geralmente algo piscando, é imediata. Há frequentemente uma resposta de áudio também. “My life for Aiur!” “Zug Zug”

Em um jogo single-player, isso é bom, mas no multiplayer pode se tornar perceptível, já que o atraso é de provavelmente várias centenas de milissegundos. Eu sempre quis experimentar respostas imediatas de animação UserTick. Por exemplo, se você emitir um comando de movimento, a unidade poderia começar a se mover lentamente na camada de usuário imediatamente e, em seguida, misturar-se na verdadeira localização da camada sim quando o comando é executado de fato. Isso seria muito útil para mais agitados, tais como Demigod ou DOTA. Existem alguns casos extremos muito feios para lidar, embora eu nunca tivesse tido a chance.

Desyncs – os erros do inferno

Um dos erros mais vis do universo é o bug de dessincronização. Eles são uns filhos da mãe! A grande hipótese para a arquitetura de todo o mecanismo é todos os jogadores estarem completamente síncronos. O que acontece se não estiverem? E se as simulações divergem? Caos. Raiva. Sofrimento.

Em SupCom, o estado do jogo inteiro é marcado uma vez por segundo. Se todos os clientes discordam sobre o hash, é isso. Game over. O fim. Uma caixa de erro aparece que diz “Desync Detected” e você tem que sair. Algo em seus SimTicks variou e agora os jogos são diferentes. Eles divergiram e só vão ficar mais distantes a partir deste ponto. Não existe um mecanismo de recuperação.

Desyncs são geralmente erro do programador. A dessincronização pode reproduzir 5% em jogos que duram mais de 60 minutos. A correção de uma dessincronização geralmente envolve uma busca binária de printf no hash da memória atual, já que o estado foi percorrido. Em baixas taxas de reprodução de desyncs, isso geralmente leva a um spam em massa do hash, enquanto meia dúzia de máquinas fazem o loop do jogo tão rápido quanto eles podem esperar por ele para quebrar. Adicionando insulto à injúria, um dos casos mais comuns é uma variável não inicializada.

Um conto sobre Demigod

Muito do meu trabalho com o motor SupCom era realmente sobre o Demigod, que usou uma versão modificada do mecanismo.

http://www.youtube.com/watch?v=0vd8an0P5LI

Perto do final do desenvolvimento, houve uma dessincronização de longa data, mas muito rara, que foi entregue a mim. No Demigod, há dezenas de quinquilharias minúsculas que são executadas ao longo do mapa. Em ocasiões extremamente raras, a localização de uma quinquilharia poderia variar em poucos centímetros em máquinas diferentes. Parece inofensivo, mas como as asas de uma borboleta, um furacão da desgraça pode acontecer.

Eu me lembro claramente de não estar certo de que poderia consertá-lo e minha liderança dizendo: “Eu estou confiando em você para conseguir consertar isso. Eu sei que você vai. Sem pressão, certo?” Toda manhã, acordávamos às 10h, e todos os dias a minha resposta era a mesma – “caça de dessincronização”. Depois de quase uma semana de espiral de loucura, encontrei o problema.

Se você assistiu ao trailer, vai notar algumas habilidades do herói que batem quinquilharias para o ar. Quando os gigantes andam esmagando castelos, no ponto em que seus martelos estão para baixo, toda a quinquilharia sai voando. O bug foi um ponteiro para uma direção com base na busca do caminho do  componente que pendia até que a quinquilharia caiu no chão e desapareceu.

Para uma dessincronização ocorrer, não foi simples assim. Primeiro, a quinquilharia teve que ser morta por algumas habilidades especiais. Isso apagou o componente de encaminhamento e bagunçou o ponteiro. Com o nosso alocador de memória, o bloco de componente de memória excluído foi simplesmente transferido para uma lista livre, mas permaneceu inalterada. Então, antes de a quinquilharia pousar, uma nova alocação de memória precisa acontecer. Essa alocação tem que ser setada no mesmo bloco de memória usado pelo nosso componente de memória que acabou de ser apagado. Então, e só então, uma dessincronização poderia ocorrer. Configurar o ponteiro apropriadamente para NULL corrigiu o problema.

Considerações finais

Este foi um breve resumo de um mecanismo síncrono como o usado por Supreme Commander. Conheço muitos jogos antigos que trabalharam de maneira semelhante. A última geração pode ser muito extravagante, principalmente em termos de lidar com latência de entrada. Eu sei que o Starcraft 2 pode dessincronizar, por isso é bastante similar. Outros jogos bons de dar uma olhada seriam Heroes of Newarth ou League of Legends. Eles não são tão grandes como SupCom, e não investiguei a fundo para ver quais truques espertos eles possuem.

Notas de rodapé

1. Halo atualmente usa um modelo lockstep síncrono para a campanha co-op e Firefight.
2. Em SupCom, a entrada é tratada como comandos para os grupos de unidades. Comandos para mover, atacar, defender, usar habilidade etc.
3. Replays antigos podem ser suportados se você puder executar o código e os dados do jogo velho.
4. Rebobinamento foi realizado em replays de Halo, armazenando “save points” que armazenam o estado do jogo. Você não pode voltar atrás sem problemas, mas pode ir para todos os save points anteriores e jogar dali para a frente. Eu acho.
5. SupCom usa um sistema de rede totalmente peer-to-peer.
6. Mas nenhum sabre de luz, infelizmente.

?

Texto original disponível em http://www.altdevblogaday.com/2011/07/09/synchronous-rts-engines-and-a-tale-of-desyncs/