Previsão de movimento para não-atiradores

35

Estou trabalhando em um jogo 2D isométrico com multiplayer de escala moderada, aproximadamente 20 a 30 jogadores conectados ao mesmo tempo a um servidor persistente. Eu tive algumas dificuldades para implementar uma boa previsão de movimento.

Física / Movimento

O jogo não tem uma implementação física verdadeira, mas usa os princípios básicos para implementar o movimento. Em vez de pesquisar continuamente as entradas, as alterações de estado (por exemplo, eventos de mouse / down / up / move) são usadas para alterar o estado da entidade do personagem que o jogador está controlando. A direção do jogador (ie / nordeste) é combinada com uma velocidade constante e transformada em um verdadeiro vetor 3D - a velocidade da entidade.

No loop principal do jogo, "Update" é chamado antes de "Draw". A lógica de atualização aciona uma "tarefa de atualização física" que rastreia todas as entidades com velocidade diferente de zero e usa uma integração muito básica para alterar a posição das entidades. Por exemplo: entity.Position + = entity.Velocity.Scale (ElapsedTime.Seconds) (onde "Seconds" é um valor de ponto flutuante, mas a mesma abordagem funcionaria para valores inteiros em milissegundos).

O ponto principal é que nenhuma interpolação é usada para o movimento - o mecanismo de física rudimentar não tem conceito de "estado anterior" ou "estado atual", apenas posição e velocidade.

Mudança de estado e pacotes de atualização

Quando a velocidade da entidade do personagem que o jogador está controlando muda, um pacote "move avatar" é enviado ao servidor contendo o tipo de ação da entidade (stand, walk, run), direção (nordeste) e posição atual. Isso é diferente de como os jogos em primeira pessoa 3D funcionam. Em um jogo em 3D, a velocidade (direção) pode mudar de quadro para quadro conforme o jogador se move. Enviar todas as alterações de estado transmitiria efetivamente um pacote por quadro, o que seria muito caro. Em vez disso, os jogos 3D parecem ignorar as alterações de estado e enviar pacotes de "atualização de estado" em um intervalo fixo - digamos, a cada 80-150ms.

Como as atualizações de velocidade e direção ocorrem com muito menos frequência no meu jogo, posso enviar todas as alterações de estado. Embora todas as simulações de física ocorram na mesma velocidade e sejam determinísticas, a latência ainda é um problema. Por esse motivo, envio pacotes de atualização de posição de rotina (semelhantes a um jogo em 3D), mas com muito menos frequência - agora a cada 250ms, mas suspeito que com uma boa previsão, posso facilmente aumentá-lo para 500ms. O maior problema é que agora eu me desviei da norma - todas as outras documentações, guias e amostras online enviam atualizações de rotina e interpolam entre os dois estados. Parece incompatível com minha arquitetura e preciso criar um algoritmo de previsão de movimento melhor que seja mais próximo de uma arquitetura (muito básica) de "física em rede".

O servidor recebe o pacote e determina a velocidade do jogador a partir do seu tipo de movimento, com base em um script (o jogador pode executar? Obtenha a velocidade de execução do jogador). Uma vez que tenha a velocidade, combina-a com a direção para obter um vetor - a velocidade da entidade. Ocorre alguma detecção de fraude e validação básica, e a entidade no lado do servidor é atualizada com a velocidade, direção e posição atuais. A otimização básica também é executada para impedir que os jogadores inundem o servidor com solicitações de movimentação.

Após atualizar sua própria entidade, o servidor transmite um pacote "atualização da posição do avatar" para todos os outros jogadores dentro do alcance. O pacote de atualização de posição é usado para atualizar as simulações de física do lado do cliente (estado mundial) dos clientes remotos e executar a previsão e a compensação de atraso.

Previsão e compensação de atraso

Como mencionado acima, os clientes têm autoridade para sua própria posição. Exceto em casos de trapaça ou anomalias, o avatar do cliente nunca será reposicionado pelo servidor. Nenhuma extrapolação ("mover agora e corrigir depois") é necessária para o avatar do cliente - o que o jogador vê está correto. No entanto, é necessário algum tipo de extrapolação ou interpolação para todas as entidades remotas que estão se movendo. Algum tipo de previsão e / ou compensação de atraso é claramente necessário no mecanismo de simulação / física local do cliente.

Problemas

Eu tenho lutado com vários algoritmos e tenho várias perguntas e problemas:

  1. Devo extrapolar, interpolar ou ambos? Meu "pressentimento" é que eu deveria estar usando pura extrapolação com base na velocidade. A mudança de estado é recebida pelo cliente, o cliente calcula uma velocidade "prevista" que compensa o atraso e o sistema físico regular faz o resto. No entanto, parece contrário a todos os outros exemplos de código e artigos - todos parecem armazenar vários estados e executar interpolação sem um mecanismo de física.

  2. Quando um pacote chega, tentei interpolar a posição do pacote com a velocidade do pacote por um período de tempo fixo (por exemplo, 200 ms). Então, tomo a diferença entre a posição interpolada e a atual posição de "erro" para calcular um novo vetor e colocá-lo na entidade em vez da velocidade que foi enviada. No entanto, a suposição é de que outro pacote chegará nesse intervalo de tempo e é incrivelmente difícil "adivinhar" quando o próximo pacote chegará - especialmente porque nem todos eles chegam em intervalos fixos (ou seja, alterações de estado). O conceito é fundamentalmente falho ou está correto, mas precisa de algumas correções / ajustes?

  3. O que acontece quando um player remoto para? Eu posso parar imediatamente a entidade, mas ela será posicionada no local "errado" até que ela se mova novamente. Se eu estimar um vetor ou tentar interpolar, tenho um problema porque não armazeno o estado anterior - o mecanismo de física não tem como dizer "você precisa parar depois de atingir a posição X". Ele simplesmente entende uma velocidade, nada mais complexo. Estou relutante em adicionar as informações de "estado de movimento de pacotes" às entidades ou ao mecanismo de física, uma vez que viola os princípios básicos de design e sangra o código de rede no restante do mecanismo de jogo.

  4. O que deve acontecer quando as entidades colidem? Existem três cenários: o jogador controlador colide localmente, duas entidades colidem no servidor durante uma atualização de posição ou uma atualização remota de entidade colide no cliente local. Em todos os casos, não tenho certeza de como lidar com a colisão - além de trapacear, os dois estados estão "corretos", mas em períodos diferentes. No caso de uma entidade remota, não faz sentido desenhá-lo caminhando através de uma parede, então eu executo a detecção de colisão no cliente local e faço com que ele "pare". Com base no ponto 2 acima, eu poderia calcular um "vetor corrigido" que tenta continuamente mover a entidade "através da parede", que nunca será bem-sucedida - o avatar remoto fica preso até que o erro fique muito alto e "se encaixe" posição. Como os jogos resolvem isso?

ShadowChaser
fonte
1
O que um jogo em 3D ou 2D tem a ver com o tipo de servidor que você usa? e por que um servidor não autoritário funciona para o seu jogo?
AttackingHobo
1
@Roy T. tradeoffs de largura de banda. A largura de banda é o recurso mais valioso nos sistemas de computadores atuais.
FXIII
1
Isso é falso, os jogos online são amplamente dominados pelo tempo de resposta, por exemplo, em uma linha de 10 Mbits (1,25 MB / s), a latência entre o servidor-cliente é de 20ms, o envio de um pacote de 1,25kb leva 20ms + 1ms. O envio de um pacote de 12,5kb leva 30ms. Em uma linha duas vezes mais rápida, um pacote de 1,25kb ainda levará 20ms + 0,5ms e 20ms + 5ms para o pacote de 12kb. Latência é o fator limitante, não a largura de banda. De qualquer forma, não sei quantos dados existem, mas o envio de 50 vetores3 (posição 25x + rotação 25x) é de apenas 600 bytes, o envio a cada 20ms custará 30kb / s. (+ sobrecarga de pacotes).
Roy T.
2
O mecanismo do Quake tem previsão desde a primeira versão. A previsão de terremotos é descrita lá e em alguns outros lugares. Confira.
user712092
1
Você faz esta posição + = velocidade * deltatime para cada entidade em paralelo (imperativamente: no código Você tem 2 matrizes de parâmetros físicos de entidades, um quadro à parte, atualiza o antigo para ser mais novo e os troca)? Existem alguns problemas com a iteração de Sean Barret, que criou a base do mecanismo Thief 1 .
user712092

Respostas:

3

A única coisa a dizer é que 2D, isométrico, 3D, são todos iguais no que diz respeito a esse problema. Como você vê muitos exemplos de 3D e está usando apenas um sistema de entrada 2D limitado a octantes com velocidade instantânea, isso não significa que você pode descartar os princípios de rede que evoluíram nos últimos 20 anos.

Princípios de design sejam condenados quando o jogo for comprometido!

Ao jogar fora o anterior e o atual, você está descartando as poucas informações que poderiam resolver seu problema. Nesses dados, eu adicionaria carimbos de data e hora calculados, para que a extrapolação possa prever melhor onde estará o jogador e a interpolação para suavizar melhor as mudanças de velocidade ao longo do tempo.

O exposto acima é um grande motivo pelo qual os servidores parecem enviar muitas informações de estado e não controlar entradas. Outro grande motivo é baseado no protocolo que você está usando. UDP com perda de pacotes aceita e entrega fora de ordem? TCP com entrega garantida e novas tentativas? Com qualquer protocolo, você obterá pacotes em momentos estranhos, atrasados ​​ou empilhados uns sobre os outros em uma enxurrada de atividades. Todos esses pacotes estranhos precisam se encaixar em um contexto para que o cliente possa descobrir o que está acontecendo.

Finalmente, mesmo que suas entradas sejam muito limitadas a 8 direções, a mudança real pode acontecer a qualquer momento - impor um ciclo de 250ms apenas frustrará os jogadores rápidos. 30 jogadores não é nada grande para qualquer servidor lidar. Se você está falando de milhares ... mesmo assim, grupos deles são divididos em várias caixas para que servidores individuais carreguem apenas uma carga razoável.

Você já criou um perfil de um mecanismo de física como Havok ou Bullet em execução? Eles são realmente bastante otimizados e muito, muito rápidos. Você pode estar caindo na armadilha de assumir que a operação ABC será lenta e otimizar algo que não precisa.

Patrick Hughes
fonte
Conselho sábio definitivo aqui! É fácil perder de vista o quadro geral. Estou usando o TCP neste caso. A questão das "8 direções" não é tão problemática em termos de entradas - é mais um problema de interpolação e extrapolação. Os gráficos são limitados a esses ângulos e usam sprites animados - a jogabilidade "parece estranha" se o jogador se mover em um ângulo ou velocidade diferente, muito longe da norma.
ShadowChaser
1

Então seu servidor é essencialmente um "árbitro"? Nesse caso, acredito que tudo no seu cliente deve ser determinístico; você precisa ter certeza de que tudo em cada cliente sempre dará o mesmo resultado.

Para sua primeira pergunta, uma vez que o jogador local receba a direção dos outros jogadores, além de ser capaz de desacelerar seu movimento ao longo do tempo e aplicar colisões, não vejo como você poderia prever em que direção o jogador seguirá, especialmente em uma partida. Ambiente de 8 direções.

Quando você recebe a atualização da "posição real" de cada jogador (que talvez você possa tentar cambalear no servidor), sim, você precisará interpolar a posição e a direção do jogador. Se a posição "adivinhada" estiver muito errada (ou seja, o jogador mudou completamente de direção logo após o envio do último pacote de direção), você terá uma enorme lacuna. Isso significa que o jogador pula de posição ou você pode interpolar para a próxima posição adivinhada . Isso fornecerá interpolação mais suave ao longo do tempo.

Quando as entidades colidem, se você pode criar um sistema determinista, cada jogador pode simular a colisão localmente, e seus resultados não devem estar muito longe da realidade. Cada máquina local deve simular a colisão para ambos os jogadores; nesse caso, assegurando-se de que o estado final seja ininterrupto e aceitável.

Pelo lado do servidor, um servidor árbitro ainda pode fazer cálculos simples para verificar, por exemplo, a velocidade de um jogador em curtos períodos de tempo para usar como um mecanismo simples de anti-fraude. Se você percorrer o monitoramento de cada jogador mais de 1s de cada vez, sua detecção de fraude será escalável, mas levará mais tempo para encontrar trapaceiros.

Jonathan Connell
fonte
Obrigado - isso parece muito próximo do que eu preciso, especialmente no lado do servidor. Um ponto interessante é que, embora os jogadores estejam travados em 8 direções, o movimento interno é um vetor 3D. Pensei um pouco mais sobre isso nos últimos dias e acho que estou lutando contra o fato de não ter interpolação implementada - simplesmente uso uma integração muito básica, definindo a velocidade e atualizando a posição com base no vector cada atualização.
shadowchaser
Não sei como combinar isso com interpolação ou previsão. Tentei tomar a posição atualizada enviada no pacote, integrando-a por um período de tempo fixo (digamos, 200ms) e depois determinando o vetor (velocidade) necessário para atingir esse ponto em 200ms. Em outras palavras, independentemente da posição incorreta atual do jogador no lado do cliente, ele ainda deve atingir a mesma "posição correta estimada" em 200ms. Acabou enviando meu personagem em direções malucas - presumo que os 200ms realmente devem ser o tempo para o próximo pacote, o que não posso estimar.
shadowchaser
Você se certificou de integrar primeiro a posição correta em t a t + 1 antes de integrar a posição errada à posição correta adivinhada em t + 1?
Jonathan Connell
Sim - verifiquei duas vezes se estava usando a posição correta para a integração original. Originalmente isso era um bug, mas corrigi-lo ainda não parecia criar uma melhoria perceptível. Minha suspeita é o "+1" - ele precisa ser muito dependente do tempo entre os pacotes. Há dois problemas: envie alterações de estado além de atualizações regulares (250ms) e não posso prever quando elas ocorrerão. Além disso, estou relutante em bloquear um intervalo específico, pois faz sentido para o servidor enviar menos atualizações para entidades que estão mais distantes do player. O tempo entre os pacotes pode mudar.
shadowchaser
1
Sim, incluir um tipo fixo de timestep provavelmente não é uma boa ideia. Estou preocupado, porém, que a irregularidade do movimento de 8 direções seja muito difícil (se não impossível?) De prever. Mesmo assim, você pode tentar usar a latência média do cliente para prever t + 1 e ter um limite acima do qual você sempre "teleporta" os outros jogadores para suas novas posições.
Jonathan Connell
0

Você não pode incluir a velocidade nas mensagens de mudança de estado e usá-la para prever o movimento? por exemplo, suponha que a velocidade não mude até você receber uma mensagem dizendo que mudou? Eu acho que você já está enviando posições, portanto, se algo "ultrapassar" por causa disso, você terá a posição correta a partir da próxima atualização. Em seguida, você pode percorrer as posições durante as atualizações, como já faz usando a velocidade da última mensagem e substituindo a posição sempre que uma mensagem é recebida com uma nova posição. Isso também significa que, se a posição não mudar, mas a velocidade será necessária para enviar uma mensagem (se esse for um caso válido no seu jogo), mas isso não afetará muito o uso da largura de banda, se for o caso.

A interpolação não deve importar aqui, isto é, por exemplo, quando você sabe onde algo estará no futuro, se o possui, qual método está usando etc. Você está confuso com extrapolação, talvez? (para o qual eu descrevo é uma abordagem simples)

jheriko
fonte
-1

Minhas primeiras perguntas seriam: O que há de errado em usar um modelo em que o servidor tenha autoridade? Por que importa se o ambiente é 2D ou 3D? Isso facilitaria muito a proteção contra trapaças se o servidor fosse autoritário.

A maioria das amostras que eu vi acopla fortemente a previsão de movimento diretamente nas próprias entidades. Por exemplo, armazenando o estado anterior junto com o estado atual. Eu gostaria de evitar isso e manter as entidades apenas com seu "estado atual". Existe uma maneira melhor de lidar com isso?

Ao executar a previsão, é necessário manter vários estados (ou pelo menos deltas) no cliente para que, quando o estado / delta autorizado for recebido do servidor, ele possa ser comparado aos do cliente e você possa tomar as medidas necessárias. correções. A idéia é manter o máximo possível determinístico para minimizar a quantidade de correções necessárias. Se você não mantiver os estados anteriores, não poderá saber se algo diferente aconteceu no servidor.

O que deve acontecer quando o jogador parar? Não consigo interpolar para a posição correta, pois eles podem precisar andar para trás ou outra direção estranha se a posição deles estiver muito à frente.

Por que você precisa interpolar? O servidor autoritativo deve substituir qualquer movimento incorreto.

O que deve acontecer quando as entidades colidem? Se o jogador atual colidir com alguma coisa, a resposta é simples - basta parar o jogador de se mover. Mas o que acontece se duas entidades ocupam o mesmo espaço no servidor? E se a previsão local fizer com que uma entidade remota colida com o jogador ou outra entidade - eu também os paro? Se a previsão teve a infelicidade de colocá-los na frente de uma parede que o jogador percorreu, a previsão nunca será capaz de compensar e, uma vez que o erro esteja alto, a entidade retornará à nova posição.

Essas são as situações em que haveria um conflito entre o servidor e o cliente e é por isso que você precisa manter estados no cliente para que o servidor possa corrigir quaisquer erros.

Desculpe pelas respostas rápidas, eu tenho que ir embora. Leia este artigo , ele menciona atiradores, mas deve funcionar para qualquer jogo que exija rede em tempo real.

Gyan tcp Gary Buyn
fonte
Algumas respostas: * Se o servidor tiver autoridade, ele será responsável por rastrear todas as entidades em movimento e atualizar suas posições em intervalos regulares. Em outras palavras, ele precisa executar o mecanismo de física - o que pode ficar caro. A escalabilidade é um dos meus principais objetivos de design. * Preciso interpolar no lado do cliente; caso contrário, toda atualização de servidor enviada aos clientes fará com que as entidades pulem. No momento, minha interpolação é feita no mecanismo de física - apenas define a velocidade. Não há estados ou deltas.
shadowchaser
Eu li todos os artigos de Glenn, mas ele afirma nos comentários que eles são apenas voltados para atiradores (ou seja, altas frequências de atualização). Alguns de seus artigos falam sobre clientes com autoridade, que é a implementação pela qual estou me esforçando. Eu não quero fazer qualquer interpolação / física no servidor, mas eu estou disposto a mudar de idéia se essa é realmente a única maneira :)
shadowchaser
1
-1. O que você escreveu apenas toca vagamente sobre o assunto; parece ambíguo. As respostas parecem sub-mínimas quando são essencialmente "lidas neste longo artigo", embora não contenham informações úteis do artigo em questão.
AttackingHobo
1
@AttackingHobo Eu tenho que concordar com você. Eu mencionei que estava com pressa, mas isso não é desculpa. Se eu não tivesse tempo, seria melhor deixá-lo em paz. Lição aprendida.
Gyan aka Gary Buyn