Como os jogos determinísticos são possíveis diante do não determinismo de ponto flutuante?

52

Para criar um jogo como um RTS em rede, já vi várias respostas sugerir tornar o jogo completamente determinístico; então você só precisa transferir as ações dos usuários e atrasar o que é exibido um pouco para "bloquear" a entrada de todos antes que o próximo quadro seja renderizado. Então, coisas como posições, saúde, etc. da unidade não precisam ser constantemente atualizadas na rede, porque a simulação de cada jogador será exatamente a mesma. Eu também ouvi a mesma coisa sugerida para fazer replays.

No entanto, como os cálculos de ponto flutuante não são determinísticos entre as máquinas, ou mesmo entre diferentes compilações do mesmo programa na mesma máquina, isso é realmente possível? Como podemos evitar que esse fato cause pequenas diferenças entre jogadores (ou replays) que se propagam ao longo do jogo ?

Ouvi algumas pessoas sugerindo evitar números de ponto flutuante e usar intpara representar o quociente de uma fração, mas isso não me parece prático - e se eu precisar, por exemplo, assumir o cosseno de um ângulo? Preciso seriamente reescrever uma biblioteca de matemática inteira?

Observe que eu estou interessado principalmente em C #, que, até onde eu sei, tem exatamente os mesmos problemas que o C ++ a esse respeito.

BlueRaja - Danny Pflughoeft
fonte
5
Esta não é uma resposta para sua pergunta, mas para resolver o problema de rede do RTS, eu recomendaria ocasionalmente sincronizar posições e saúde da unidade para corrigir qualquer desvio. Exatamente quais informações precisam ser sincronizadas dependerão do jogo; você pode otimizar o uso da largura de banda, não se preocupando em sincronizar itens como efeitos de status.
Jhocking 13/07
@jhocking No entanto, é provavelmente a melhor resposta.
11137 Jonathan Connell
Os infacti de starcraft II são sincronizados exatamente sempre, e olhei para a repetição da jogabilidade com meus amigos, cada computador lado a lado e onde havia diferenças (também significativas), especialmente com alto atraso (1 segundo). Eu tive algumas unidades que onde 6/7 mapa quadrados longe brindes na minha tela que diz respeito à sua própria
GameDeveloper

Respostas:

15

Os pontos flutuantes são determinísticos?

Eu li muito sobre esse assunto alguns anos atrás, quando queria escrever um RTS usando a mesma arquitetura de trava de segurança que você faz.

Minhas conclusões sobre pontos flutuantes de hardware foram:

  • O mesmo código de montagem nativo é provavelmente determinístico, desde que você tenha cuidado com sinalizadores de ponto flutuante e configurações do compilador.
  • Havia um projeto RTS de código aberto que alegava ter obtido compilações C / C ++ determinísticas em diferentes compiladores usando uma biblioteca de wrapper. Não confirmei essa reivindicação. (Se bem me lembro, era sobre a STREFLOPbiblioteca)
  • O .net JIT é permitido bastante margem de manobra. Em particular, é permitido usar maior precisão do que o necessário. Além disso, ele usa conjuntos de instruções diferentes no x86 e no AMD64 (acho que no x86 ele usa o x87, o AMD64 usa algumas instruções SSE cujo comportamento é diferente para denorms).
  • Instruções complexas (incluindo função trigonométrica, exponenciais, logaritmos) são especialmente problemáticas.

Concluí que é impossível usar os tipos de ponto flutuante embutidos no .net de maneira determinística.

Soluções possíveis

Portanto, eu precisava de soluções alternativas. Eu considerei:

  1. Implemente FixedPoint32em C #. Embora isso não seja muito difícil (eu tenho uma implementação parcialmente concluída), o intervalo muito pequeno de valores torna irritante o uso. Você deve ter cuidado o tempo todo para não transbordar nem perder muita precisão. No final, achei isso não mais fácil do que usar números inteiros diretamente.
  2. Implemente FixedPoint64em C #. Achei isso bastante difícil de fazer. Para algumas operações, números inteiros intermediários de 128 bits seriam úteis. Mas .net não oferece esse tipo.
  3. Use código nativo para as operações matemáticas, que são determinísticas em uma plataforma. Incorre na sobrecarga de uma chamada de delegado em todas as operações matemáticas. Perde a capacidade de executar várias plataformas.
  4. Use Decimal. Mas é lento, consome muita memória e gera facilmente exceções (divisão por 0, estouros). É muito bom para uso financeiro, mas não serve para jogos.
  5. Implemente um ponto flutuante personalizado de 32 bits. Pareceu bastante difícil no começo. A falta de uma intrínseca BitScanReverse causa alguns aborrecimentos ao implementar isso.

My SoftFloat

Inspirado em sua postagem no StackOverflow , eu comecei a implementar um tipo de ponto flutuante de 32 bits em software e os resultados são promissores.

  • A representação de memória é compatível com binários com os flutuadores IEEE, para que eu possa reinterpretar a conversão ao enviá-los para o código gráfico.
  • Ele suporta SubNorms, infinitos e NaNs.
  • Os resultados exatos não são idênticos aos do IEEE, mas isso geralmente não importa para os jogos. Nesse tipo de código, importa apenas que o resultado seja o mesmo para todos os usuários, não que seja preciso até o último dígito.
  • O desempenho é decente. Um teste trivial mostrou que ele pode fazer cerca de 75MFLOPS em comparação com 220-260MFLOPS com floatadição / multiplicação (thread único em um i3 de 2,66 GHz ). Se alguém tiver boas referências de ponto flutuante para .net, envie-as para mim, pois meu teste atual é muito rudimentar.
  • O arredondamento pode ser melhorado. Atualmente, ele trunca, o que corresponde aproximadamente ao arredondamento para zero.
  • Ainda está muito incompleto. Atualmente, faltam divisões, elencos e operações matemáticas complexas.

Se alguém quiser contribuir com testes ou melhorar o código, entre em contato comigo ou faça uma solicitação pull no github. https://github.com/CodesInChaos/SoftFloat

Outras fontes de indeterminismo

Existem também outras fontes de indeterminismo no .net.

  • iterando sobre Dictionary<TKey,TValue>ou HashSet<T>retorna os elementos em uma ordem indefinida.
  • object.GetHashCode() difere de corrida para corrida.
  • A implementação da Randomclasse incorporada não é especificada, use o seu próprio.
  • Multithreading com bloqueio ingênuo leva a reordenar e resultados diferentes. Tenha muito cuidado para usar os threads corretamente.
  • Quando WeakReferences perdem, seu objetivo é indeterminado, pois o GC pode ser executado a qualquer momento.
CodesInChaos
fonte
23

A resposta a esta pergunta é do link que você postou. Especificamente, você deve ler a citação de Gas Powered Games:

Eu trabalho na Gas Powered Games e posso dizer em primeira mão que a matemática de ponto flutuante é determinística. Você só precisa do mesmo conjunto de instruções e compilador e, é claro, o processador do usuário adere ao padrão IEEE754, que inclui todos os nossos clientes de PC e 360. O mecanismo que executa o DemiGod, Supreme Commander 1 e 2 depende do padrão IEEE754. Sem mencionar provavelmente todos os outros jogos RTS ponto a ponto do mercado.

E então abaixo desse é o seguinte:

Se você armazenar replays como entradas do controlador, eles não poderão ser reproduzidos em máquinas com diferentes arquiteturas de CPU, compiladores ou configurações de otimização. No MotoGP, isso significava que não podíamos compartilhar replays salvos entre Xbox e PC.

Um jogo determinístico só será determinístico ao usar os arquivos compilados de forma idêntica e rodar em sistemas que cumpram os padrões IEEE. Simulações ou replays sincronizados de rede entre plataformas não serão possíveis.

AttackingHobo
fonte
2
Como mencionei, estou interessado principalmente em C #; como o JIT faz a compilação real, não posso garantir que ele seja "compilado com as mesmas configurações de otimização", mesmo ao executar o mesmo executável na mesma máquina!
BlueRaja - Danny Pflughoeft
2
Às vezes, o modo de arredondamento é definido de forma diferente no processador, em algumas arquiteturas o processador possui um registro interno maior que a precisão para cálculos ... enquanto o IEEE754 não dá margem de manobra no modo como as operações de FP devem funcionar, ele não ' especifica como qualquer função matemática específica deve ser implementada, o que pode expor as diferenças arquiteturais.
Stephen
4
@ 3nixios Com esse tipo de configuração, o jogo não é determinístico. Somente jogos com um timestap fixo podem ser determinísticos. Você está argumentando que algo já não é determinístico ao executar uma simulação em uma única máquina.
AttackingHobo
4
@ 3nixios: "Eu estava afirmando que, mesmo com um timestep fixo, nada garante que o timestep sempre permaneça fixo." Você está completamente errado. O ponto de um instante temporal fixo é sempre ter ao mesmo tempo delta para cada carrapato na atualização
AttackingHobo
3
@ 3nixios A utilização de um timestep fixo garante que o timestep seja corrigido porque nós, os desenvolvedores, não permitimos o contrário. Você está interpretando mal como o atraso deve ser compensado ao usar uma etapa de tempo fixo. Cada atualização do jogo deve usar o mesmo tempo de atualização; portanto, quando a conexão de um par fica atrasada, ele ainda deve calcular cada atualização individual que perdeu.
Keeblebrox
3

Use aritmética de ponto fixo. Ou escolha um servidor autorizado e sincronize o estado do jogo de vez em quando - é isso que o MMORTS faz. (Pelo menos, o Elements of War funciona assim. Também está escrito em C #.) Dessa forma, os erros não têm chance de se acumular.

deixa pra lá
fonte
Sim, eu poderia torná-lo um servidor cliente e lidar com as dores de cabeça da previsão e extrapolação do lado do cliente. Esta pergunta é sobre arquiteturas ponto a ponto, que deveriam ser mais fáceis ...
BlueRaja - Danny Pflughoeft
Bem, você não precisa fazer previsões em um cenário "todos os clientes executam o mesmo código". A função do servidor é ser a autoridade somente na sincronização.
Nevermind
Servidor / cliente é apenas um método de criar um jogo em rede. Outro método popular (especialmente para jogos, por exemplo. RTS, como C & C ou Starcraft) é peer-to-peer, em que não é nenhum servidor autorizado. Para que isso seja possível, todos os cálculos devem ser completamente determinísticos e consistentes em todos os clientes - daí a minha pergunta.
BlueRaja - Danny Pflughoeft
Bem, não é como se você absolutamente tivesse que fazer o jogo estritamente p2p sem servidores / clientes elevados. Se você absolutamente precisar, no entanto - use ponto fixo.
Nevermind
3

Edit: Um link para uma classe de ponto fixo (Comprador, cuidado! - Não usei ...)

Você sempre pode recorrer à aritmética de ponto fixo. Alguém (fazendo rts, nada menos) já fez o trabalho de perna no stackoverflow .

Você pagará uma penalidade de desempenho, mas isso pode ou não ser um problema, pois o .net não será especialmente eficiente aqui, pois não usará instruções simd. Referência!

NB: Aparentemente, alguém da intel parece ter uma solução para permitir que você use a biblioteca de primitivas de desempenho da intel em c #. Isso pode ajudar a vetorizar o código de ponto fixo para compensar o desempenho mais lento.

LukeN
fonte
decimalfuncionaria bem para isso também; mas isso ainda tem os mesmos problemas do uso int- como faço para disparar com ele?
BlueRaja - Danny Pflughoeft
11
A maneira mais fácil seria criar uma tabela de pesquisa e enviá-la ao lado do aplicativo. Você pode interpolar entre valor se a precisão for um problema.
13137 LukeN
Como alternativa, você poderá substituir chamadas trigonométricas por números imaginários ou quaternions (se 3D). Esta é uma excelente explicação
Luken
Isso também pode ajudar.
13137 LukeN
Na empresa em que trabalhei, construímos uma máquina de ultrassom usando matemática de ponto fixo, para que ela funcione definitivamente para você.
13137 LukeN
3

Eu trabalhei em vários títulos grandes.

Resposta curta: é possível se você é incrivelmente rigoroso, mas provavelmente não vale a pena. A menos que você esteja em uma arquitetura fixa (leia-se: console), é exigente, quebradiço e vem com uma série de problemas secundários, como a associação tardia.

Se você ler alguns dos artigos mencionados, notará que, embora possa definir o modo da CPU, existem casos bizarros, como quando um driver de impressão alterna o modo da CPU porque estava no mesmo espaço de endereço. Eu tive um caso em que um aplicativo estava bloqueado por quadro em um dispositivo externo, mas um componente defeituoso estava causando a aceleração da CPU devido ao calor e relatado de maneira diferente pela manhã e à tarde, tornando-a uma máquina diferente após o almoço.

Essas diferenças de plataforma estão no silício, não no software, portanto, para responder sua pergunta, o C # também é afetado. Instruções como FMA (multiply-add fundido) vs ADD + MUL alteram o resultado porque ele arredonda internamente apenas uma vez em vez de duas vezes. C oferece a você mais controle para forçar a CPU a fazer o que você deseja basicamente excluindo operações como o FMA para tornar as coisas "padrão" - mas ao custo da velocidade. Os intrínsecos parecem ser os mais propensos a diferir. Em um projeto, tive que desenterrar um livro de 150 anos de tabelas acos para obter valores de comparação para determinar qual CPU estava "certa". Muitas CPUs usam aproximações polinomiais para funções trigonométricas, mas nem sempre com os mesmos coeficientes.

Minha recomendação:

Independentemente de você seguir passo inteiro de bloqueio ou sincronização, lide com a mecânica do jogo principal separadamente da apresentação. Torne o jogo preciso, mas não se preocupe com a precisão na camada de apresentação. Lembre-se também de que você não precisa enviar todos os dados mundiais em rede na mesma taxa de quadros. Você pode priorizar suas mensagens. Se sua simulação corresponder a 99,999%, você não precisará transmitir com tanta frequência para permanecer emparelhado. (Prevenir fraudes à parte.)

Há um bom artigo sobre o mecanismo de origem que explica uma maneira de sincronizar: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Lembre-se, se você estiver interessado em ingressar tarde, terá que acertar e sincronizar de qualquer maneira.

lisa
fonte
1

Observe que eu estou interessado principalmente em C #, que, até onde eu sei, tem exatamente os mesmos problemas que o C ++ a esse respeito.

Sim, o C # tem os mesmos problemas que o C ++. Mas também tem muito mais.

Por exemplo, considere esta declaração de Shawn Hawgraves:

Se você armazenar replays como entradas do controlador, eles não poderão ser reproduzidos em máquinas com diferentes arquiteturas de CPU, compiladores ou configurações de otimização.

É "fácil o suficiente" garantir que isso aconteça em C ++. No C # , no entanto, será muito mais difícil lidar com isso. Isso é graças ao JIT.

O que você acha que aconteceria se o intérprete executasse seu código interpretado uma vez, mas o executasse na segunda vez? Ou talvez o interprete duas vezes na máquina de outra pessoa, mas o JIT é depois disso?

O JIT não é determinístico, porque você tem muito pouco controle sobre ele. Essa é uma das coisas que você desiste de usar o CLR.

E Deus o ajude se uma pessoa estiver usando o .NET 4.0 para executar seu jogo, enquanto outra pessoa estiver usando o CLR Mono (usando as bibliotecas .NET, é claro). Mesmo o .NET 4.0 vs. .NET 5.0 pode ser diferente. Você simplesmente precisa de mais controle sobre os detalhes de baixo nível de uma plataforma para garantir esse tipo de coisa.

Você deve ser capaz de se safar da matemática de ponto fixo. Mas é isso aí.

Nicol Bolas
fonte
Além da matemática, o que mais pode ser diferente? Presumivelmente, ações de "entrada" estão sendo enviadas como ações lógicas em um rts. Por exemplo, mova a unidade "a" para a posição "b". Eu vejo um problema com a geração aleatória de números, mas isso obviamente também precisa ser enviado como entrada de simulação.
Luken
@LukeN: O problema é que a posição de Shawn sugere fortemente que as diferenças do compilador podem ter efeitos reais na matemática de ponto flutuante. Ele saberia mais do que eu; Estou simplesmente extrapolando seu aviso para o domínio da compilação / interpretação de JIT e C #.
Nicol Bolas
O C # possui sobrecarga de operador e também possui um tipo interno para matemática de ponto fixo. No entanto, isso tem os mesmos problemas do uso de um int- como faço para disparar com ele?
BlueRaja - Danny Pflughoeft
11
> O que você acha que aconteceria se o intérprete executasse seu código> interpretado uma vez, mas depois o executasse na segunda vez? Ou talvez o interprete duas vezes na máquina de outra pessoa, mas o JIT é depois disso? 1. O código CLR é sempre emitido antes da execução. 2. O .net usa o IEEE 754 para carros alegóricos, é claro. > O JIT não é determinístico, porque você tem muito pouco controle sobre ele. Sua conclusão é uma causa bastante fraca de falsas declarações falsas. > E que Deus o ajude se uma pessoa estiver usando o .NET 4.0 para executar o seu jogo, enquanto outra pessoa estiver usando o CLR Mono (usando as bibliotecas .NET, é claro). Mesmo. NET
Romanenkov Andrey
@Romanenkov: "Você conclui que é uma causa bastante fraca de falsas declarações falsas." Por favor, diga-me quais afirmações são falsas e por quê, para que possam ser corrigidas.
Nicol Bolas
1

Depois de escrever essa resposta, percebi que ela realmente não responde à pergunta, que era especificamente sobre não-determinismo de ponto flutuante. Mas talvez isso seja útil para ele, de qualquer maneira, se ele for criar um jogo em rede dessa maneira.

Juntamente com o compartilhamento de entrada que você está transmitindo para todos os jogadores, pode ser muito útil criar e transmitir uma soma de verificação de estado importante do jogo, como posições do jogador, saúde etc. Ao processar a entrada, afirme que o estado do jogo verifica somas todos os players remotos estão sincronizados. Você tem a garantia de ter bugs fora de sincronia (OOS) para corrigir e isso tornará mais fácil - você terá um aviso prévio de que algo deu errado (o que ajudará você a descobrir as etapas de reprodução) e poderá adicionar mais estado do jogo registrando código suspeito para permitir que você suporte o que está causando o OOS.

Giro
fonte
0

Acho que a ideia do blog vinculada a ainda precisa de sincronização periódica para ser viável - já vi bugs suficientes em jogos RTS em rede que não adotam essa abordagem.

As redes são com perdas, lentas, têm latência e podem até poluir seus dados. "Determinismo de ponto flutuante" (que soa bastante enérgico para me deixar cético) é a menor das suas preocupações na realidade ... especialmente se você usar uma etapa de tempo fixo. com etapas de tempo variável, você precisará interpolar entre etapas de tempo fixo para evitar problemas de determinismo também. Eu acho que isso é geralmente o que se entende por comportamento não determinístico de "ponto flutuante" - apenas que as etapas de tempo variável causam divergências nas integrações - nada a ver com bibliotecas matemáticas ou funções de baixo nível.

A sincronização é a chave.

jheriko
fonte
-2

Você os torna determinísticos. Para um ótimo exemplo, consulte a Apresentação da GDC do Dungeon Siege sobre como eles tornaram os locais do mundo em rede.

Lembre-se também de que o determinismo também se aplica a eventos 'aleatórios'!

Doug-W
fonte
11
É isso que o OP quer saber como fazer, com ponto flutuante.
The Duck comunista