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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.