Como projetar um sistema de repetição

Então, como eu projetaria um sistema de repetição?

Você pode conhecê-lo em certos jogos como Warcraft 3 ou Starcraft, onde é possível assistir ao jogo novamente depois que ele já foi jogado.

Você acaba com um arquivo de repetição relativamente pequeno. Então, minhas perguntas são:

• Como salvar os dados? (formato personalizado?) (tamanho pequeno)
• O que deve ser salvo?
• Como torná-lo genérico para que possa ser usado em outros jogos para gravar um período (e não uma correspondência completa, por exemplo)?
• Tornar possível avançar e retroceder (o WC3 não pôde retroceder tanto quanto me lembro)

Este excelente artigo aborda muitos dos problemas: http://www.gamasutra.com/view/feature/2029/developing_your_own_replay_system.php

Algumas coisas que o artigo menciona e faz bem:

• seu jogo tem que ser determinístico.
• ele registra o estado inicial dos sistemas de jogo no primeiro quadro e apenas a entrada do jogador durante o jogo.
• quantize entradas para diminuir o número de bits. Ou seja. representam flutuadores dentro de vários intervalos (por exemplo, [0, 1] ou [-1, 1] dentro de menos bits. Entradas quantizadas também devem ser obtidas durante o jogo real.
• use um único bit para determinar se um fluxo de entrada possui novos dados. Como alguns fluxos não mudam frequentemente, isso explora a coerência temporal nas entradas.

Uma maneira de melhorar ainda mais a taxa de compactação para a maioria dos casos seria desacoplar todos os fluxos de entrada e codificá-los de forma totalmente independente. Será uma vitória sobre a técnica de codificação delta se você codificar sua corrida em 8 bits e a corrida exceder 8 quadros (muito provavelmente, a menos que seu jogo seja um verdadeiro espremedor de botões). Eu usei essa técnica em um jogo de corrida para compactar 8 minutos de entradas de 2 jogadores enquanto corria em uma pista até algumas centenas de bytes.

Em termos de tornar esse sistema reutilizável, fiz com que o sistema de reprodução lidasse com fluxos de entrada genéricos, mas também forneci ganchos para permitir que a lógica específica do jogo agrupasse a entrada do teclado / gamepad / mouse nesses fluxos.

Se você quiser retroceder rapidamente ou procurar aleatoriamente, poderá salvar um ponto de verificação (seu estado completo do jogo) a cada N quadros. N deve ser escolhido para minimizar o tamanho do arquivo de repetição e também para garantir que o tempo de espera do reprodutor seja razoável enquanto o estado é repetido no ponto escolhido. Uma maneira de contornar isso é garantir que buscas aleatórias possam ser feitas apenas nesses locais exatos dos pontos de verificação. Rebobinar é uma questão de definir o estado do jogo no ponto de verificação imediatamente antes do quadro em questão e, em seguida, reproduzir as entradas até chegar ao quadro atual. No entanto, se N for muito grande, você poderá engatar em alguns quadros. Uma maneira de amenizar esses problemas é pré-armazenar em cache de forma assíncrona os quadros entre os 2 pontos de verificação anteriores enquanto você estiver reproduzindo um quadro em cache da região atual do ponto de verificação.

Além da solução "certifique-se de que as teclas sejam reproduzidas", o que pode ser surpreendentemente difícil, você pode gravar o estado do jogo inteiro em todos os quadros. Com um pouco de compactação inteligente, você pode compactá-lo significativamente. É assim que o Braid lida com seu código de retrocesso de tempo e funciona muito bem.

Como você precisará de um ponto de verificação para rebobinar, tente implementá-lo da maneira mais simples antes de complicar as coisas.

Você pode visualizar seu sistema como se ele fosse composto por uma série de estados e funções, onde uma função f[j]com entrada x[j]altera o estado do sistema s[j]em estado s[j+1], da seguinte forma:

s[j+1] = f[j](s[j], x[j])

Um estado é a explicação de todo o seu mundo. A localização do jogador, a localização do inimigo, a pontuação, a munição restante, etc. Tudo o que você precisa para desenhar um quadro do seu jogo.

Uma função é qualquer coisa que possa afetar o mundo. Uma mudança de quadro, um pressionamento de tecla, um pacote de rede.

A entrada são os dados que a função utiliza. Uma mudança de quadro pode levar a quantidade de tempo desde que o último quadro passou, o pressionamento de tecla pode incluir a tecla real pressionada, bem como se a tecla shift foi pressionada ou não.

Para fins desta explicação, farei as seguintes suposições:

Suposição 1:

A quantidade de estados para uma determinada execução do jogo é muito maior que a quantidade de funções. Você provavelmente possui centenas de milhares de estados, mas apenas várias dezenas de funções (mudança de quadro, pressionamento de tecla, pacote de rede etc.). Obviamente, a quantidade de entradas deve ser igual à quantidade de estados menos um.

Suposição 2:

O custo espacial (memória, disco) de armazenar um único estado é muito maior que o de armazenar uma função e sua entrada.

Suposição 3:

O custo temporal (tempo) de apresentar um estado é semelhante, ou apenas uma ou duas ordens de magnitude mais longas que o cálculo de uma função sobre um estado.

Dependendo dos requisitos do seu sistema de reprodução, existem várias maneiras de implementar um sistema de reprodução, para que possamos começar pelo mais simples. Também farei um pequeno exemplo usando o jogo de xadrez, gravado em pedaços de papel.

Método 1:

Loja s[0]...s[n] . Isso é muito simples, muito direto. Por causa da suposição 2, o custo espacial disso é bastante alto.

Para o xadrez, isso seria realizado ao desenhar o tabuleiro inteiro para cada jogada.

Método 2:

Se você precisar apenas executar a reprodução direta, poderá simplesmente armazenar s[0]e depois armazenar f[0]...f[n-1](lembre-se, este é apenas o nome do ID da função) e x[0]...x[n-1](qual foi a entrada para cada uma dessas funções). Para reproduzir, basta começar s[0]e calcular

s[1] = f[0](s[0], x[0])
s[2] = f[1](s[1], x[1])

e assim por diante...

Quero fazer uma pequena anotação aqui. Vários outros comentaristas disseram que o jogo "deve ser determinístico". Qualquer um que disser que precisa fazer o Computer Science 101 novamente, porque, a menos que seu jogo seja executado em computadores quânticos, TODOS OS PROGRAMAS DO COMPUTADOR SÃO DETERMINÍSTICOS¹. É isso que torna os computadores tão incríveis.

No entanto, como seu programa provavelmente depende de programas externos, variando de bibliotecas até a implementação real da CPU, certifique-se de que suas funções se comportem da mesma maneira entre as plataformas.

Se você usar números pseudo-aleatórios, poderá armazenar os números gerados como parte de sua entrada xou o estado da função prng como parte do seu estado se sua implementação como parte da função f.

Para o xadrez, isso seria realizado desenhando o quadro inicial (que é conhecido) e depois descrevendo cada jogada dizendo qual peça foi para onde. É assim que eles realmente fazem, a propósito.

Método 3:

Agora, é provável que você queira pesquisar sua reprodução. Ou seja, calcule s[n]para um arbitrário n. Usando o método 2, você precisa calcular s[0]...s[n-1]antes de poder calculars[n] , o que, de acordo com a suposição 2, pode ser bastante lento.

Para implementar isso, o método 3 é uma generalização dos métodos 1 e 2: armazene f[0]...f[n-1]e, x[0]...x[n-1]assim como o método 2, mas também armazene s[j], para todos, j % Q == 0para uma determinada constante Q. Em termos mais fáceis, isso significa que você armazena um marcador em um de cada Qestado. Por exemplo, para Q == 100, você armazenas[0], s[100], s[200]...

Para calcular s[n]para um arbitrário n, primeiro você carrega o armazenado anteriormente s[floor(n/Q)]e depois calcula todas as funções de floor(n/Q)até n. No máximo, você calculará Qfunções. Valores menores de Qsão mais rápidos de calcular, mas consomem muito mais espaço, enquanto valores maiores deQ consomem menos espaço, mas levam mais tempo para serem calculados.

O método 3 com Q==1é o mesmo que o método 1, enquanto o método 3 comQ==inf é o mesmo que o método 2.

Para o xadrez, isso seria realizado ao desenhar cada movimento e um em cada 10 tabuleiros (para Q==10).

Método 4:

Se você quiser reverter replay, você pode fazer uma pequena variação do método 3. Suponha Q==100, e você deseja calcular s[150]através s[90]no sentido inverso. Com o método não modificado 3, você precisará fazer 50 cálculos para obter s[150]e mais 49 cálculos para obter s[149]e assim por diante. Mas como você já calculou o s[149]recebimento s[150], é possível criar um cache s[100]...s[150]quando calcular s[150]pela primeira vez, e então você jás[149] no cache quando precisar exibi-lo.

Você só precisa regenerar o cache toda vez que precisar calcular s[j], j==(k*Q)-1para qualquer dado k. Dessa vez, aumentar Qresultará em tamanho menor (apenas para o cache), mas em períodos mais longos (apenas para recriar o cache). Um valor ideal paraQ pode ser calculado se você souber os tamanhos e tempos necessários para calcular estados e funções.

Para o xadrez, isso seria realizado desenhando todos os movimentos, assim como um em cada 10 tabuleiros (para Q==10), mas também seria necessário desenhar em um pedaço de papel separado, os últimos 10 tabuleiros que você calculou.

Método 5:

Se os estados simplesmente consomem muito espaço ou as funções consomem muito tempo, você pode criar uma solução que realmente implemente (e não falsifique) a reprodução reversa. Para fazer isso, você deve criar funções reversas para cada uma das funções que possui. No entanto, isso requer que cada uma de suas funções seja uma injeção. Se isso for possível, para f'denotar o inverso da função f, o cálculo s[j-1]é tão simples quanto

s[j-1] = f'[j-1](s[j], x[j-1])

Observe que aqui, a função e a entrada são ambas j-1, não j. Essa mesma função e entrada seriam as que você usaria se estivesse calculando

s[j] = f[j-1](s[j-1], x[j-1])

Criar o inverso dessas funções é a parte complicada. No entanto, você geralmente não pode, pois alguns dados de estado geralmente são perdidos após cada função em um jogo.

Esse método, como está, pode reverter o cálculo s[j-1], mas somente se você tiver s[j]. Isso significa que você só pode assistir a reprodução ao contrário, a partir do ponto em que decidiu reproduzir ao contrário. Se você deseja reproduzir novamente de um ponto arbitrário, misture isso com o método 4.

No xadrez, isso não pode ser implementado, pois, com um determinado tabuleiro e o movimento anterior, você pode saber qual peça foi movida, mas não para onde foi movida.

Método 6:

Finalmente, se você não pode garantir que todas as suas funções sejam injeções, pode fazer um pequeno truque para fazer isso. Em vez de cada função retornar apenas um novo estado, você também pode retornar os dados descartados, assim:

s[j+1], r[j] = f[j](s[j], x[j])

Onde r[j]estão os dados descartados. E então crie suas funções inversas para que eles tomem os dados descartados, assim:

s[j] = f'[j](s[j+1], x[j], r[j])

Além de f[j]e x[j], você também deve armazenar r[j]para cada função. Mais uma vez, se você deseja procurar, deve armazenar marcadores, como no método 4.

No xadrez, isso seria o mesmo que o método 2, mas, diferentemente do método 2, que diz apenas qual peça vai para onde, você também precisa armazenar de onde veio cada peça.

Implementação:

Como isso funciona para todos os tipos de estados, com todos os tipos de funções, para um jogo específico, você pode fazer várias suposições, que facilitarão a implementação. Na verdade, se você implementar o método 6 com todo o estado do jogo, não apenas poderá reproduzir os dados, mas também voltar no tempo e retomar a reprodução a qualquer momento. Isso seria incrível.

Em vez de armazenar todo o estado do jogo, você pode simplesmente armazenar o mínimo necessário para desenhar um determinado estado e serializar esses dados a cada período fixo de tempo. Seus estados serão essas serializações e sua entrada será agora a diferença entre duas serializações. A chave para que isso funcione é que a serialização deve mudar pouco se o estado mundial mudar pouco também. Essa diferença é completamente reversível, portanto, a implementação do método 5 com indicadores é muito possível.

Eu já vi isso implementado em alguns jogos importantes, principalmente para reprodução instantânea de dados recentes quando ocorre um evento (um frag em fps ou uma pontuação em jogos esportivos).

Espero que essa explicação não tenha sido muito chata.

¹ Isso não significa que alguns programas agem como se fossem não determinísticos (como o MS Windows ^^). Agora, falando sério, se você pode criar um programa não determinístico em um computador determinístico, pode ter certeza de que ganhará simultaneamente a medalha Fields, o prêmio Turing e provavelmente até um Oscar e um Grammy por tudo o que vale a pena.

Uma coisa que outras respostas ainda não abordaram é o perigo de carros alegóricos. Você não pode criar um aplicativo totalmente determinístico usando carros alegóricos.

Usando carros alegóricos, você pode ter um sistema completamente determinístico, mas apenas se:

• Usando exatamente o mesmo binário
• Usando exatamente a mesma CPU

Isso ocorre porque a representação interna dos carros alegóricos varia de uma CPU para outra - mais dramaticamente entre as CPUs AMD e Intel. Desde que os valores estejam nos registros da FPU, eles são mais precisos do que parecem do lado C, portanto, qualquer cálculo intermediário é feito com maior precisão.

É bastante óbvio como isso afetará o AMD vs o bit Intel - digamos que um use flutuadores de 80 bits e o outro 64, por exemplo - mas por que o mesmo requisito binário?

Como eu disse, a maior precisão está em uso desde que os valores estejam nos registros da FPU . Isso significa que sempre que você recompilar, a otimização do compilador poderá trocar valores dentro e fora dos registros FPU, resultando em resultados sutilmente diferentes.

Você pode ajudar nisso definindo sinalizadores _control87 () / _ controlfp () para usar a menor precisão possível. No entanto, algumas bibliotecas também podem tocar nisso (pelo menos alguma versão do d3d fez).

Salve o estado inicial dos seus geradores de números aleatórios. Em seguida, salve, com carimbo de data e hora, cada entrada (mouse, teclado, rede, o que for). Se você tem um jogo em rede, provavelmente já possui tudo isso.

Redefina os RNGs e reproduza a entrada. É isso aí.

Isso não resolve o enrolamento, para o qual não há solução geral, além de reproduzir desde o início o mais rápido possível. Você pode melhorar o desempenho, verificando todo o estado do jogo a cada X segundos; depois, você só precisará repetir tantos, mas todo o estado do jogo também pode ser proibitivamente caro.

Os detalhes do formato do arquivo não importam, mas a maioria dos mecanismos já possui uma maneira de serializar comandos e declarar - para rede, economia ou qualquer outra coisa. Apenas use isso.

Eu votaria contra a repetição determinística. É MUITO mais simples e muito menos propenso a erros salvar o estado de cada entidade a cada 1/3 de segundo.

Salve exatamente o que deseja mostrar na reprodução - se for apenas posição e título, tudo bem, se você também quiser mostrar estatísticas, salve isso também, mas, em geral, salve o mínimo possível.

Ajuste a codificação. Use o mínimo de bits possível para tudo. A repetição não precisa ser perfeita, desde que pareça boa o suficiente. Mesmo se você usar um float para, digamos, título, poderá salvá-lo em um byte e obter 256 valores possíveis (precisão de 1,4º). Isso pode ser suficiente ou até demais para o seu problema específico.

Use codificação delta. A menos que suas entidades se teletransportem (e, se o fizerem, tratem o caso separadamente), codifique as posições como a diferença entre a nova posição e a antiga - para movimentos curtos, você pode se livrar com muito menos bits do que precisaria para posições completas .

Se você quiser rebobinar com facilidade, adicione quadros-chave (dados completos, sem deltas) a cada N quadro. Dessa forma, você pode obter menos precisão para deltas e outros valores, os erros de arredondamento não serão tão problemáticos se você redefinir os valores "verdadeiros" periodicamente.

Finalmente, gzip a coisa toda :)

É difícil. Antes de tudo, leia as respostas de Jari Komppa.

Uma reprodução feita no meu computador pode não funcionar no seu computador, porque o resultado da flutuação é ligeiramente diferente. É um grande negócio.

Mas depois disso, se você tiver números aleatórios, é para armazenar o valor inicial na repetição. Em seguida, carregue todos os estados padrão e defina o número aleatório para essa semente. A partir daí, você pode simplesmente registrar o estado atual da chave / mouse e o período de tempo que fica assim. Em seguida, execute todos os eventos usando isso como entrada.

Para pular arquivos (o que é muito mais difícil), você precisará despejar THE MEMORY. Como, onde cada unidade está, dinheiro, tempo passa, todo o estado do jogo. Em seguida, avance rapidamente, mas reproduza tudo, exceto pular a renderização, o som etc. até chegar ao destino de tempo desejado. Isso pode acontecer a cada minuto ou 5 minutos, dependendo da velocidade da transmissão.

Os principais pontos são - Lidando com números aleatórios - Copiando entrada (s) e remota (s) - Estado de despejo para pular arquivos e ... - TER FLUTUANTE NÃO QUEBRA COISAS (sim, eu tive que gritar)

Estou um pouco surpreso que ninguém tenha mencionado essa opção, mas se o seu jogo tiver um componente multiplayer, você já deve ter feito muito trabalho duro necessário para esse recurso. Afinal, o que é multijogador senão uma tentativa de reproduzir os movimentos de outra pessoa em um momento (ligeiramente) diferente no seu próprio computador?

Isso também oferece os benefícios de um tamanho menor de arquivo como efeito colateral, supondo novamente que você esteja trabalhando em um código de rede compatível com a largura de banda.

De várias maneiras, combina as opções "seja extremamente determinístico" e "mantenha um registro de tudo". Você ainda precisará de determinismo - se a sua reprodução for essencialmente um bots jogando o jogo exatamente da maneira como você o jogou originalmente, quaisquer que sejam as ações que eles executem que possam ter resultados aleatórios, terão o mesmo resultado.

O formato dos dados pode ser tão simples quanto um despejo do tráfego da rede, embora eu imagine que não faria mal limpá-lo um pouco (afinal de contas, você não precisa se preocupar com o atraso na reprodução). Você pode reproduzir apenas uma parte do jogo usando o mecanismo de ponto de verificação que outras pessoas mencionaram - normalmente um jogo multiplayer envia um estado completo da atualização do jogo de vez em quando, então, novamente, você já deve ter feito esse trabalho.

Para obter o menor arquivo de repetição possível, você precisa se certificar de que seu jogo é determinístico. Geralmente, isso envolve olhar para o seu gerador de números aleatórios e ver onde ele é usado na lógica do jogo.

Você provavelmente precisará ter um RNG de lógica de jogo e um RNG de tudo o mais para coisas como GUI, efeitos de partículas, sons. Depois de fazer isso, você precisa registrar o estado inicial da lógica do jogo RNG e, em seguida, o comando do jogo de todos os jogadores em cada quadro.

Para muitos jogos, existe um nível de abstração entre a entrada e a lógica do jogo em que a entrada é transformada em comando. Por exemplo, pressionar o botão A no controlador resulta em um comando digital de "salto" sendo definido como verdadeiro e a lógica do jogo reage aos comandos sem verificar o controlador diretamente. Ao fazer isso, você precisará gravar apenas os comandos que afetam a lógica do jogo (não é necessário gravar o comando "Pausar") e, provavelmente, esses dados serão menores do que os dados do controlador. Você também não precisa se preocupar em gravar o estado do esquema de controle, caso o jogador decida remapear os botões.

Rebobinar é um problema difícil usando o método determinístico, além de usar o instantâneo do estado do jogo e avançar rapidamente para o momento em que você deseja observar, não há muito o que fazer além de gravar todo o estado do jogo em cada quadro.

Por outro lado, o avanço rápido é certamente possível. Desde que a sua lógica do jogo não seja dependente da sua renderização, você poderá executá-la quantas vezes quiser antes de renderizar um novo quadro do jogo. A velocidade do avanço rápido será limitada pela sua máquina. Se você quiser pular adiante em grandes incrementos, precisará usar o mesmo método de captura instantânea necessário para rebobinar.

Possivelmente, a parte mais importante de escrever um sistema de repetição que se baseia no determinismo é registrar um fluxo de dados de depuração. Esse fluxo de depuração contém uma captura instantânea do máximo de informações possível a cada quadro (sementes RNG, transformações de entidade, animações etc.) e pode testar esse fluxo de depuração registrado contra o estado do jogo durante as repetições. Isso permitirá que você saiba rapidamente incompatibilidades no final de qualquer quadro. Isso economizará inúmeras horas em querer arrancar seus cabelos de insetos não determinísticos desconhecidos. Algo tão simples quanto uma variável não inicializada vai estragar tudo na 11ª hora.

NOTA: Se o seu jogo envolve transmissão dinâmica de conteúdo ou você tem lógica de jogo em vários threads ou em núcleos diferentes ... boa sorte.

Para ativar a gravação e a rebobinagem, grave todos os eventos (gerado pelo usuário, gerado pelo timer, gerado pela comunicação, ...).

Para cada hora de registro do evento, o que foi alterado, valores anteriores, novos valores.

Os valores calculados não precisam ser registrados, a menos que o cálculo seja aleatório
(nesses casos, você também pode registrar valores calculados ou alterações na semente após cada cálculo aleatório).

Os dados salvos são uma lista de alterações.
As alterações podem ser salvas em vários formatos (binário, xml, ...).
A mudança consiste no ID da entidade, nome da propriedade, valor antigo, novo valor.

Verifique se o seu sistema pode reproduzir essas alterações (acessar a entidade desejada, alterar a propriedade desejada para o novo estado ou para o antigo).

Exemplo:

Para permitir rebobinar / avançar rapidamente ou gravar apenas determinados intervalos de tempo,
os quadros-chave são necessários - se gravar o tempo todo, de vez em quando, salve todo o estado do jogo.
Se gravar apenas um determinado intervalo de tempo, no início salve o estado inicial.

Se você precisar de idéias sobre como implementar seu sistema de reprodução, pesquise no google como implementar desfazer / refazer em um aplicativo. Pode ser óbvio para alguns, mas talvez não para todos, que desfazer / refazer é conceitualmente o mesmo que reproduzir para jogos. É apenas um caso especial em que você pode retroceder e, dependendo da aplicação, procurar um momento específico.

Você verá que ninguém implementando desfazer / refazer reclama de determinísticas / não determinísticas, variáveis ​​flutuantes ou CPUs específicas.