Como a compactação delta reduz a quantidade de dados enviados pela rede?

26

Muitos jogos usam a técnica de compactação delta para diminuir a carga de dados enviada. Não consigo entender como essa técnica realmente reduz a carga de dados?

Por exemplo, digamos que eu quero enviar uma posição. Sem compactação delta, envio um vector3com a posição exata da entidade, por exemplo (30, 2, 19). Com compactação delta, envio um vector3com números menores (0.2, 0.1, 0.04).

Eu não entendo como reduz a carga de dados se ambas as mensagens são vector3- 32 bits para cada float - 32 * 3 = 96 bits!

Eu sei que você pode converter cada flutuador em um byte e depois convertê-lo novamente de um byte em flutuante, mas causa erros de precisão visíveis.

user101051
fonte
Sempre que você cria redes com um jogo que usa qualquer forma de compactação delta, você precisa ser perfeitamente determinístico (falha e obtém dessincronização). Se a "conversão de byte para float" (ou o que for) causa erros de precisão não é importante - a condição necessária é ter tudo exatamente igual em todas as máquinas / jogos sincronizados. Se houver "erros de precisão" (inevitável, mesmo que você use flutuações completas - sua CPU não usa as mesmas flutuações da minha CPU), elas precisam ser iguais em todas as máquinas - e, portanto, não são visíveis. Você escolheu os tipos para evitar efeitos visíveis.
Luaan 15/05
2
@Luaan ou você pode adicionar um estado absoluto parcial de vez em quando, por exemplo, você pode selecionar algumas poucas entidades e passar a posição absoluta, preferindo selecionar entidades próximas ao player.
catraca aberração
De alguma forma, eu estava esperando essa pergunta ser sobre algum parente de rsync ...
Samb
Codificação de Huffman.
Ben Voigt
Basta usar homem do meio
John Demetriou

Respostas:

41

Há momentos em que você não pode evitar o envio do estado completo do jogo - como no carregamento de um jogo multiplayer salvo ou quando é necessária uma ressincronização. Mas o envio do estado completo geralmente é evitável, e é aí que entra a codificação delta . Geralmente, é sobre isso que trata a compactação delta; seu exemplo não descreve realmente essa situação. A razão pela qual a compactação delta é mencionada é porque as implementações ingênuas geralmente enviam estado, em vez de deltas, porque geralmente é o estado que qualquer implementação ingênua de jogo armazena de qualquer maneira. Deltas são então uma otimização.

Com os deltas, você nunca enviava as posições das unidades que não se moviam . Esse é o espírito disso.

Imagine que éramos amigos por anos e eu perdi minha memória (e havia descartado todas as suas cartas depois de lê-las). Em vez de simplesmente continuar com sua série de cartas normalmente, você teria que me escrever toda a história de sua vida em uma carta maciça, mais uma vez, para que eu pudesse acompanhar.

No seu caso, pode (dependendo da sua base de código) ser possível usar um número menor de bits para codificar os deltas, em oposição aos grandes intervalos de bits necessários para enviar o estado completo. Digamos que o mundo tenha muitos quilômetros de extensão, talvez seja necessário um flutuador de 32 bits para codificar com precisão as posições, digamos, um centímetro em um determinado eixo. No entanto, dada a velocidade máxima aplicável às entidades, que pode ser apenas alguns metros por tick, ela pode ser executada em apenas 8 bits (2 ^ 8 = 256, o suficiente para armazenar no máximo 200 cm). Obviamente, isso pressupõe o uso de ponto fixo em vez de ponto flutuante ... ou algum tipo de flutuação de meio / quarto como no OpenGL, se você não quiser aborrecimentos de ponto fixo.

Engenheiro
fonte
7
Sua resposta não está clara para mim. Sinto que não enviar as informações de um objeto não em movimento é apenas um efeito colateral da codificação delta e não "O espírito dele". O verdadeiro motivo para usar a codificação delta parece ser destacado melhor na resposta do catraca.
Etsitpab Nioliv
14
@EtsitpabNioliv "O Espírito" é simplesmente "não envie o que você não precisa". Isso pode ser levado ao nível de bit - "use apenas a largura de banda necessária para obter a mensagem necessária por fio". Essa resposta parece evidente o suficiente para todos os outros. Obrigado.
Engenheiro de
4
@EtsitpabNioliv Já aprendeu sobre como o SVN armazena arquivos no lado do servidor? Ele não armazena o arquivo inteiro a cada confirmação. Ele armazena deltas , as alterações que cada confirmação contém. O termo "delta" é frequentemente usado em matemática e programação para se referir à diferença entre dois valores. Não sou programador de jogos, mas ficaria surpreso se o uso for muito diferente nos jogos. A idéia então faz sentido: você "comprime" a quantidade de dados que deve enviar enviando apenas as diferenças, em vez de tudo. (Se qualquer parte dele é confuso para mim, é a palavra "compressa".)
jpmc26
11
Além disso, números pequenos têm um número maior de zero bits e o uso do algoritmo de compactação adequado para codificar / decodificar as informações enviadas pode levar a uma carga útil ainda menor a ser enviada pela rede.
Liggiorgio 16/05
22

Você tem o delta errado. Você está olhando para o delta dos elementos individuais. Você precisa pensar no delta de toda a cena.

Suponha que você tenha 100 elementos em sua cena, mas apenas 1 deles foi movido. Se você enviar 100 vetores de elementos, 99 deles serão desperdiçados. Você realmente só precisa enviar 1.

Agora, digamos que você tenha um objeto JSON que armazena todos os seus vetores de elementos. Este objeto é sincronizado entre seu servidor e seu cliente. Em vez de decidir "fez isso e então mudou?" você pode gerar seu próximo jogo em um objeto JSON, criar um diff tick100.json tick101.jsone enviar esse diff. No lado do cliente, você aplica o diff ao vetor do seu tick atual e está pronto.

Com isso, você aproveita as décadas de experiência em detectar diferenças de texto (ou binárias!) E não precisa se preocupar em perder nada. Agora, idealmente, você também usa uma biblioteca que faz isso nos bastidores para torná-lo ainda mais fácil para você como desenvolvedor.

corsiKa
fonte
2
Usando diffsons como um hack ineficiente. Manter a cadeia JSON no lado de recebimento, corrigindo e desserializando-a toda vez é desnecessário. Calcular a diferença de dois dicionários de valores-chave não é uma tarefa complicada; basicamente, basta percorrer todas as chaves e verificar se os valores são iguais. Caso contrário, adicione-os ao dict de valor-chave resultante e, finalmente, envie o dict serializado para JSON. Simples, não são necessários anos de experiência. Ao contrário do diffs, este método: 1) não inclui dados antigos (substituídos); 2) joga mais bem com o UDP; 3) não depende de novas linhas
gronostaj 15/05
8
@gronostaj Este foi um exemplo para passar o ponto. Na verdade, eu não defendo o uso do diff para JSON - é por isso que diz "suponha".
CorsiKa
2
"Ao fazer isso, você aproveita as décadas de experiência em detectar diferenças de texto (ou binárias!) E não precisa se preocupar em perder nada. Agora, idealmente, você também usa uma biblioteca que faz isso nos bastidores para torná-lo ainda mais uniforme. mais fácil para você como desenvolvedor ". Definitivamente, essa parte faz parecer que você está sugerindo o uso de um diff ou uma biblioteca que usa um diff quando ninguém faria isso razoavelmente. Eu não chamaria de compressão delta "diffing", é apenas a compressão delta, as semelhanças são superficiais
Selali Adobor
Um diff ótimo e uma compressão delta ideal são os mesmos. Embora o utilitário diff na linha de comando seja voltado para arquivos de texto e provavelmente não forneça um resultado ideal, eu recomendaria pesquisar bibliotecas que fazem a compactação delta para você. Não há nada extravagante na palavra delta - delta e diff, nesse sentido, significam literalmente a mesma coisa. Isso parece ter sido perdido ao longo dos anos.
CorsiKa
9

Muitas vezes, outro mecanismo de compressão é combinado com a codificação delta, como por exemplo, compressão aritmética.

Esses esquemas de compactação funcionam muito melhor quando os possíveis valores são agrupados de forma previsível. A codificação delta agrupará os valores em torno de 0.

catraca arrepiante
fonte
11
Outro exemplo: se você tiver 100 naves espaciais, cada uma com sua própria posição, mas viajando no mesmo vetor de velocidade, precisará enviar a velocidade apenas uma vez (ou pelo menos comprimir muito bem); caso contrário, você precisará enviar 100 posições. Deixe os outros fazerem a adição. Se você considera as simulações de etapa de bloqueio de estado compartilhado uma forma agressiva de compactação delta, nem envia as velocidades - apenas os comandos provenientes do player. Mais uma vez, deixe que todos façam suas próprias contribuições.
Luaan 15/05
Concordo. A compactação é relevante na resposta.
Leopoldo Sanczyk 22/10
8

Você está correto, mas está faltando um ponto importante.

As entidades de um jogo são descritas por muitos atributos, dos quais a posição é apenas uma .

Que tipo de atributos? Sem ter que pensar muito, em um jogo em rede, isso pode incluir:

  • Posição.
  • Orientação.
  • Número do quadro atual.
  • Informações sobre cores / iluminação.
  • Transparência.
  • Modelo para usar.
  • Textura para usar.
  • Efeitos especiais.
  • Etc.

Se você escolher cada uma delas isoladamente, certamente poderá defender que, em qualquer quadro específico, ele precise ser alterado, e deverá ser retransmitido na íntegra.

No entanto, nem todos esses atributos mudam na mesma taxa .

Modelo não muda? Sem compactação delta, ela deve ser retransmitida de qualquer maneira. Com a compressão delta, não precisa ser assim.

Posição e orientação são dois casos mais interessantes, sendo comumente compostos por 3 carros alegóricos cada. Entre dois quadros, existe a possibilidade de que apenas 1 ou 2 de cada conjunto de 3 flutuadores possam mudar. Movendo-se em uma linha reta? Não está rodando? Não pule? Esses são todos os casos em que, sem a compactação delta, você deve retransmitir por completo, mas, com a compactação delta, é necessário retransmitir apenas o que muda.

Maximus Minimus
fonte
8

Você está certo de que um cálculo delta ingênuo por si só, com o resultado armazenado na mesma estrutura de dados de tamanho dos operandos e transmitido sem nenhum processamento adicional, não salvaria nenhum tráfego.

No entanto, existem duas maneiras pelas quais um sistema bem projetado, baseado em deltas, pode economizar tráfego.

Em primeiro lugar, em muitos casos, o delta será zero. Você pode criar seu protocolo de forma que, se o delta for zero, você não o envie. Obviamente, há alguma sobrecarga nisso, pois você precisa indicar o que está enviando ou não, mas no geral é provável que seja uma grande vitória.

Em segundo lugar, os deltas geralmente terão uma faixa de valores muito menor que os números originais. e esse intervalo será centrado em zero. Isso pode ser explorado usando um tipo de dados menor para a maioria dos deltas ou passando o fluxo de dados completo por meio de um algoritmo de compactação de uso geral.

Peter Green
fonte
6

Embora a maioria das respostas fale sobre como a codificação delta trata apenas de enviar as alterações ao estado como um todo, há outra coisa chamada "codificação delta" que pode ser usada como um filtro para reduzir a quantidade de dados que você precisa compactar no estado completo atualização também, que pode ser de onde vem a confusão na pergunta, conforme solicitado.

Ao codificar um vetor de números, você pode, em alguns casos (por exemplo, números inteiros, enumerações, etc.) usar uma codificação de bytes variáveis ​​para os elementos individuais e, em alguns desses casos, é possível reduzir ainda mais a quantidade de dados que cada elemento precisa se você armazená-lo como somas em execução ou como o valor mínimo e a diferença entre cada valor e esse mínimo.

Por exemplo, se você quiser codificar o vetor {68923, 69012, 69013, 69015}, poderá delta-codificar como {68923, 89, 1, 2}. Usando uma codificação trivial de bytes variáveis, na qual você armazena 7 bits de dados por byte e usa um bit para indicar que há outro byte chegando, cada um dos elementos individuais da matriz precisaria de 3 bytes para transmiti-los, mas a versão codificada em delta exigiria apenas 3 bytes para o primeiro elemento e 1 byte para os elementos restantes; dependendo do tipo de dados que você está serializando, isso pode levar a uma economia bastante impressionante.

No entanto, isso é mais uma otimização de serialização e não é o que geralmente significa quando falamos de "codificação delta" quando se trata de transmitir dados arbitrários como parte do estado do jogo (ou vídeo ou algo semelhante); outras respostas já fazem um trabalho adequado para explicar isso.

fofo
fonte
4

Também vale a pena notar que os algoritmos de compactação funcionam melhor no diff. Como outras respostas mencionam, a maioria dos seus elementos permanece a mesma entre 2 estados ou os valores mudam em uma pequena fração. Nos dois casos, a aplicação de um algoritmo de compressão à diferença do seu vetor de números proporciona uma economia significativa. Mesmo se você não aplicar nenhuma lógica extra ao seu vetor, como remover os 0 elementos.

Aqui está um exemplo em Python:

import numpy as np
import zlib
import json
import array


state1 = np.random.random(int(1e6))

diff12 = np.r_[np.random.random(int(0.1e6)), np.zeros(int(0.9e6))]
np.random.shuffle(diff12) # shuffle so we don't cheat by having all 0s one after another
state2 = state1 + diff12

state3 = state2 + np.random.random(int(1e6)) * 1e-6
diff23 = state3 - state2

def compressed_size(nrs):
    serialized = zlib.compress(array.array("d", nrs).tostring())
    return len(serialized)/(1024**2)


print("Only 10% of elements change for state2")
print("Compressed size of diff12: {:.2f}MB".format(compressed_size(diff12)))
print("Compressed size of state2: {:.2f}MB".format(compressed_size(state2)))

print("All elements change by a small value for state3")
print("Compressed size of diff23: {:.2f}MB".format(compressed_size(diff23)))
print("Compressed size of state3: {:.2f}MB".format(compressed_size(state3)))

O que me dá:

Only 10% of elements change for state2
Compressed size of diff12: 0.90MB
Compressed size of state2: 7.20MB
All elements change by a small value for state3
Compressed size of diff23: 5.28MB
Compressed size of state3: 7.20MB
csiz
fonte
Belo exemplo. A compressão desempenha um papel aqui.
Leopoldo Sanczyk 22/10
0

Se sua posição estiver armazenada no vetor3, mas a entidade real poderá mover apenas um número inteiro por vez. Em seguida, enviar seu delta em bytes seria melhor do que enviá-lo em número inteiro.

Posição atual: 23009.0, 1.0, 2342.0 (3 float)
Nova posição: 23010.0, 1.0, 2341.0 (3 float)
Delta: 1, 0, -1 (3 bytes)

Em vez de enviar a posição exata sempre, enviamos o delta.

the_lotus
fonte
0

A compactação delta é uma compactação dos valores codificados em delta. A codificação delta é uma transformação que produz diferentes distribuições estatísticas de números. Se a distribuição é favorável ao algoritmo de compactação escolhido, diminui a quantidade de dados. Funciona muito bem em um sistema como um jogo em que as entidades se movem apenas um pouco entre duas atualizações.

Digamos que você tenha 100 entidades em 2D. Em uma grade grande, 512 x 512. Considerando apenas números inteiros por exemplo. São dois números inteiros por entidade ou 200 números.

Entre duas atualizações, todas as nossas posições mudam em 0, 1, -1, 2 ou -2. Houve 100 instâncias de 0, 33 instâncias de 1 e -1 e apenas 17 instâncias de 2 e -2. Isso é bastante comum. Escolhemos a codificação Huffman para compactação.

A árvore Huffman para isso será:

 0  0
-1  100
 1  101
 2  110
-2  1110

Todos os seus 0 serão codificados como um único bit. Isso é apenas 100 bits. 66 valores serão codificados como 3 bits e apenas 34 valores como 4 bits. Isso é 434 bits ou 55 bytes. Mais algumas pequenas despesas gerais para salvar nossa árvore de mapeamento, pois a árvore é pequena. Observe que, para codificar 5 números, você precisa de 3 bits. Trocamos aqui a capacidade de usar 1 bit para '0' pela necessidade de usar 4 bits para '-2'.

Agora compare isso com o envio de 200 números arbitrários. Se suas entidades não podem estar no mesmo bloco, você tem quase certeza de obter uma distribuição estatística ruim. O melhor caso seria 100 números únicos (todos no mesmo X com Y diferente). Isso é pelo menos 7 bits por número (175 bytes) e muito difícil para qualquer algoritmo de compactação.

A compactação delta funciona no caso especial quando suas entidades mudam apenas um pouco. Se você tiver muitas alterações exclusivas, a codificação delta não ajudará.


Observe que a codificação e compactação delta também são usadas em outras situações com outras transformações.

O MPEG divide a imagem em pequenos quadrados e, se parte da imagem se mover, apenas o movimento e a mudança de brilho serão salvos. Em um filme de 25fps, muitas alterações entre os quadros são muito pequenas. Novamente, codificação delta + compactação. Funciona melhor para cenas estáticas.

MartinTeeVarga
fonte