Teoria de jogos Multiplayer – Previsão de Movimento e Reconciliação

Teoria de jogos multiplayer - Previsão de Movimento e ReconsiliaçãoEsta é a segunda parte de uma série da série de artigos “Teoria de jogos Multiplayer” onde irei explicar os conceitos e algoritmos fundamentais e para a criação de jogos multiplayer rápidos e fluídos. Se já alguma vez tentou criar um jogo Multiplayer, deverá saber que na internet os delays podem ser muito grandes, na ordem de algumas décimas de segundo. Estes delays podem tornar o jogo pouco fluído e no pior cenário poderá ser mesmo impossível jogá-lo. Neste artigo vamos falar de algumas formas, nomeadamente a previsão de movimento e reconciliação com o servidor, para acabar com este problema.

 

Previsão de movimento pelo cliente

Embora existam alguns jogadores batoteiros (cheaters), na maioria do tempo o servidor estará a processar pedidos válidos, de jogadores que não são cheaters ou que não estão a tentar fazer batota naquele momento. Isto significa que a maioria do input’s recebidos pelo servidor serão comandos válidos e o estado do jogo será actualizado com esperado. Ou seja, a personagem de um jogo está na posição (0,0), quando jogador clica na seta para a esquerda, a personagem será movida para a posição (-1,0).

Este tipo de eventos deterministas podem ser utilizados em nossa vantagem pois permitem a aplicação de técnicas de previsão de movimento. Note-se que um mundo é determinista quando dado um estado do jogo e um conjunto de inputs, o estado seguinte  é completamente previsível.

 

Exemplo sem previsão de movimento

Vamos supor agora que temos lag de 100ms. Vamos também supor que a animação da personagem ao mover de um quadrado para o outro demora também 100ms. Utilizando uma implementação ingénua toda a acção de mover a personagem de uma posição para a outra demoraria 200ms.

Previsão de movimento pelo cliente
O cliente envia uma acção para o servidor: “Pressiona a seta para a esquerda”. O servidor lê, processa o comando e de seguida envia o novo estado do jogo para o cliente. Quando o novo estado do jogo chega ao cliente esta começa a mostrar no ecrã a animação da personagem a mover-se um quadrado para a esquerda. Desde a  acção do jogador até os resultados começarem a aparecer no ecrã passam 100ms.

 

Exemplo com previsão de movimento

Uma vez que o mundo é determinista, podemos assumir que os inputs que enviamos para o servidor serão executados com sucesso. Assumindo isto, o cliente pode prever o estado do jogo depois dos inputs serem processados, sendo que na maioria das vezes esta previsão estará correcta.

Em alternativa a enviar os inputs e esperar pelo novo estado do jogo para começar a renderizar a animação da personagem, podemos enviar o input ao servidor e começar imediatamente a animação da personagem, assumindo que os nossos inputs serão aceites com sucesso pelo servidor.

 

A animação é renderizada enquanto o cliente espera que o servidor confirme a acção. Não existe qualquer tempo de espera desde a  acção do jogador até os resultados começarem a aparecer no ecrã.

Utilizando a abordagem acima, deixará de existir qualquer tipo de delay entre a acção do jogador e os resultados no ecrã. Mesmo desta forma o servidor continua a ser autoritário. Se o cliente tentasse hacker o jogo, enviando inputs inválidos, seria renderizado no ecrã no hacker o que ele queria mas isto não iria afectar o estado do servidor (que é o que os outros jogadores vêm).

 

Problemas de sincronização

No exemplo acima, os números são escolhidos com cuidado para que tudo funcione correctamente. Considere agora o seguinte cenário: Existe um lag de 250ms entre o cliente e o servidor. A animação de mover a personagem de um quadrado para o outro demora 100ms. Considere que o jogador desta vez clica na seta para a esquerda duas vezes seguidas (tenta mover-se dois quadrados para a esquerda.

Utilizando as técnicas discutidas acima, o resultado seria o seguinte:

 

Dessincronização entre estados
Dessincronização entre o estado previsto (pela previsão de movimento) e o estado autoritário do servidor.

No exemplo acima existe um problema em t = 250 (a vermelho), quando o novo estado do jogo chega ao cliente. O estado previsto pelo cliente indica que a personagem deverá estar na posição x = -2, mas por outro lado o servidor diz ao cliente que a personagem está na posição x = -1. Uma vez que o servidor é autoritário, o cliente deverá mover a personagem de volta para a posição (-1, 0). Logo a seguir, no momento t=350ms, o cliente recebe um novo estado do jogo que diz que a personagem está na posição x = -2, então a personagem salta de novo para a posição (-2, 0).

 

Ponto de vista do jogador

Tendo em conta o exemplo acima, e no ponto de vista do jogador o que aconteceu foi  seguinte:

  1. O jogador clicou duas vezes na seta para a esquerda;
  2. A personagem moveu-se dois quadrados para a esquerda e permaneceu lá durante 50ms;
  3. A personagem saltou um quadrado para a direita e permaneceu durante 100ms;
  4. A personagem saltou um quadrado para a esquerda.

Isto no ponto de vista do jogador é inaceitável, sendo provavelmente impossível de desfrutar do jogo desta forma.

 

Reconciliação com o servidor

A solução para corrigir o problema descrito acima é percebermos que o jogador vê os acontecimentos do jogo em tempo real mas que devido ao lag, os estados que recebe do servidor são relativos ao jogo no passado. 

Este problema é fácil de resolver. O cliente deve adicionar um número (ID) a cada comando que envia ao servidor. No exemplo acima, o comando #1 seria a primeira vez que a seta para a esquerda foi pressionada. O comando #2 seria a segunda vez que esta tecla foi pressionada. Quando o servidor responde ao pedido do cliente, deverá incluir o numero do último comando processado.

Precisão de movimento e reconciliação com o servidor
Previsão de movimento e reconciliação com o servidor.

Agora, no momento t = 250ms, o servidor diz ao cliente: “tendo em conta o teu pedido #1, a tua posição é x = -1“. Como o servidor é autoritário, a personagem é movida para a posição (-1, 0). Assumimos que o cliente guarda uma cópia de todos os pedidos que enviou ao servidor. Tendo em conta o último estado recebido pelo servidor, o cliente sabe que o servidor já processou o pedido #1 portanto pode eliminar a cópia guardada deste pedido. O cliente desta forma sabe que o servidor ainda tem de processar o pedido #2. Aplicando a previsão de movimento outra vez, o cliente consegue calcular o estado presente do jogo baseando-se no último estado autoritário vindo do servidor mais os inputs que faltam processar.

 

Acontecimentos passo a passo

No momento t = 250ms, o cliente recebe a mensagem: “posição: (-1, 0), último pedido processado: #1“. Ele remove todas as cópias de comandos enviados até ao #1, mantendo ainda uma cópia do comando #2 que ainda não foi processado pelo servidor. O cliente actualiza o estado do jogo tendo em conta a última mensagem vinda do servidor e aplica todos os comandos que ainda não foram processados pelo servidor. Neste caso o comando #2. O resultado final será posição = (-2, 0), que é o resultado correcto.

No momento t = 350ms, uma nova mensagem vem do servidor. Esta mensagem indica: “posição: (-2, 0), último pedido processado: #2“. Neste momento o cliente elimina todas as cópias dos comandos enviados até ao #2 e actualiza o estado do jogo. Como não existem mais nenhuns comandos por processar na lista, nenhuma previsão do estado do jogo será necessária e o resultado final será aquele enviado pelo servidor, que neste caso é o correcto.

 

Notas finais

O exemplo mostrado acima foi aplicado ao movimento de uma personagem, mas os mesmos princípios podem ser aplicados noutras situações. Por exemplo num jogo de tiros como o Counter Strike, quando um jogador dispara noutro jogador, podemos mostrar imediatamente a animação de sangue e a quantidade de vida retirada, mas não devemos actualizar a vida da personagem até ao servidor autorizar.

Devido à complexidade dos estados do jogo que podem não ser facilmente reversiveis, devemos evitar eliminar uma personagem/jogador até que o servidor autorize, mesmo quando a vida dessa personagem é menor do que 0. Note-se, mesmo quando o mundo do jogo é completamente determinista é possível que a precisão do cliente e o estado do servidor não correspondam mesmo com o uso de reconciliação. Este cenário é impossível (como mostrado acima) num jogo com um só jogador, mas pode facilmente acontecer quando vários jogadores estão ligados ao mesmo tempo. Este será um dos tópicos do próximo artigo.

 

Gostou deste artigo sobre previsão de movimento e reconciliação com o servidor? Então partilhe com os seus amigos e deixe um comentário abaixo!

Deixar uma resposta