- Dans un environnement FPS rapide, les informations d’état arrivées trop tard ont peu de valeur, donc Quake 3 a choisi une conception centrée sur UDP/IP pour réduire la latence
- NetChannel abstrait la communication au-dessus d’UDP, où les pertes sont possibles, et le serveur recalcule uniquement les différences d’état nécessaires grâce à un historique de snapshots par client
- Le serveur utilise ensemble le Master Gamestate, les 32 gamestates les plus récents et un dummy gamestate pour produire mises à jour complètes et mises à jour delta avec la même procédure
- En l’absence d’ACK du client, le serveur compare le dernier snapshot confirmé à l’état courant pour inclure dans un même message les changements manqués et les nouveaux changements
- Même sans introspection intégrée en C, Quake 3 repère les différences de champs avec
netField_t et des macros, et NetChannel pré-segmente en 1400 octets pour éviter la fragmentation par les routeurs
Un modèle réseau pensé pour UDP/IP
- Le modèle réseau de Quake 3 est considéré comme l’une des parties les plus élégantes du moteur et, au niveau bas, il abstrait la communication avec le module NetChannel, apparu pour la première fois dans Quake World
- Dans un jeu rapide, une information manquée lors du premier envoi devient vite obsolète, il est donc plus avantageux d’envoyer l’état le plus récent que de retransmettre l’ancien
- C’est pourquoi le moteur ne porte aucune trace de TCP/IP, la latence induite par un transport fiable étant jugée trop coûteuse
- Deux couches mutuellement exclusives s’ajoutent à la pile réseau
- Chiffrement à l’aide d’une clé pré-partagée
- Compression à l’aide d’une clé Huffman précalculée
- Le serveur réduit la taille des datagrammes UDP tout en compensant leur absence de fiabilité
- Il génère des paquets delta à partir d’un historique de snapshots
- Il n’envoie que les champs modifiés grâce à une forme d’introspection mémoire
Rôle du serveur et du client
- Le flux côté client est simple
- À chaque frame, il envoie des commandes au serveur
- Il reçoit du serveur les mises à jour du gamestate
- Le serveur doit propager le Master Gamestate à chaque client tout en tenant compte des paquets UDP perdus
- Le mécanisme central repose sur trois éléments
- Master Gamestate : l’état global du jeu considéré comme vrai ; les commandes client arrivent via NetChannel, sont converties en
event_t, puis modifient l’état du jeu sur le serveur
- Les 32 gamestates récents propres à chaque client : les états envoyés sur le réseau sont stockés dans un tableau circulaire et appelés snapshots
- dummy gamestate : un état dont tous les champs valent 0, utilisé comme base de génération delta lorsqu’il n’existe pas d’état précédent
- Le serveur construit avec ces trois éléments le message de mise à jour transmis à NetChannel
- Comme il faut conserver beaucoup de gamestates par client, l’usage mémoire augmente fortement
- D’après la mesure fournie, 8 Mo sont utilisés pour 4 joueurs
Produire des mises à jour complètes et partielles avec les snapshots
- L’exemple décrit l’envoi d’une mise à jour à Client1, avec un état de Client2 composé de quatre champs :
pos[X], pos[Y], pos[Z] et health
- La communication se fait via UDP/IP et, sur Internet, les messages peuvent être fréquemment perdus
-
Première frame serveur
- Le serveur applique au Master Gamestate toutes les mises à jour reçues des clients, puis propage cet état à Client1
- Le module réseau suit toujours la même procédure
- Il copie le Master Gamestate dans le prochain emplacement de l’historique du client
- Il compare ce snapshot copié à un autre snapshot
- Lors de la première mise à jour, aucun snapshot valide n’existe dans l’historique de Client1, la comparaison se fait donc avec le dummy snapshot
- Tous les champs du dummy snapshot valent 0, le résultat est donc une mise à jour complète
- Chaque champ est précédé d’un marqueur binaire indiquant s’il a changé
- Dans l’exemple, la mise à jour complète utilise 132 bits
- Le format est
[1 A_on32bits 1 B_on32bits 1 B_on32bits 1 C_on32bits]
-
Deuxième frame serveur
- À la frame suivante, Client2 se déplace sur l’axe Y et la valeur de
pos[1] devient E
- Client1 a accusé réception de la mise à jour précédente, donc Snapshot1 passe à l’état ACK
- Le serveur copie le Master Gamestate dans l’emplacement suivant pour créer Snapshot2, puis le compare à Snapshot1, qui est valide
- Au final, seul le champ modifié
pos[1] = E est transmis sur le réseau
- Comme chaque champ possède un marqueur binaire, cette mise à jour partielle utilise 36 bits
- Le format est
[0 1 32bitsNewValue 0 0]
-
Troisième frame serveur
- À la frame suivante, Client2 perd de la santé et
health = H
- Client1 n’accuse pas réception de la dernière mise à jour
- Le paquet UDP du serveur a pu être perdu, ou bien l’ACK du client a pu être perdu
- Dans les deux cas, ce snapshot ne peut pas être utilisé
- Le serveur copie le Master Gamestate dans l’emplacement suivant pour créer Snapshot3, puis le compare au dernier Snapshot1 ayant reçu un ACK
- Le message transmis est une mise à jour partielle qui contient à la fois l’ancien changement
pos[1] = E et le nouveau changement health = H
- Si Snapshot1 est trop ancien pour être réutilisé, le moteur repart du dummy snapshot et renvoie une mise à jour complète
Comment la même procédure compense les pertes
- La simplicité du système de snapshots vient du fait qu’un même algorithme prend automatiquement en charge deux tâches
- Générer une mise à jour complète ou partielle
- Réexpédier dans un même message les informations précédentes non reçues et les nouvelles
- Au lieu de traiter la perte de paquets UDP via un flux séparé et complexe, le système compense en calculant la différence entre le dernier snapshot ayant reçu un ACK et le Master Gamestate courant
- Lorsqu’il n’existe pas d’état précédent, ou qu’il n’est plus exploitable, le système repart du dummy snapshot pour envoyer l’état complet et restaurer la cohérence
Comment trouver les différences de champs en C
- Quake 3 ne dispose pas d’introspection en C, mais la position de chaque champ est préparée à l’avance via un tableau
netField_t et des directives du préprocesseur
netField_t contient le nom du champ, son offset et son nombre de bits- La macro
NETF(x) utilise l’opérateur de stringification et le calcul d’offset sur entityState_t pour écrire ces informations plus brièvement
- Voici la structure d’exemple
typedef struct { char *name; int offset; int bits; } netField_t;
// using the stringizing operator to save typing...
#define NETF(x) #x,(int)&((entityState_t*)0)->x
netField_t entityStateFields[] = {
{ NETF(pos.trTime), 32 },
{ NETF(pos.trBase[0]), 0 },
{ NETF(pos.trBase[1]), 0 },
...
}
- L’implémentation complète se trouve dans une partie de MSG_WriteDeltaEntity
- Quake 3 n’interprète pas la signification des objets comparés ; il suit simplement l’index, l’offset et la taille définis dans
entityStateFields pour transmettre les différences sur le réseau
Pourquoi découper à l’avance en 1400 octets
- Le module NetChannel découpe les messages en morceaux de 1400 octets alors que la taille maximale d’un datagramme UDP est de 65507 octets
- Le code concerné se trouve dans Netchan_Transmit
- Comme le MTU de la plupart des réseaux est de 1500 octets, ce découpage à 1400 octets vise à éviter la fragmentation des paquets par les routeurs sur le trajet Internet
- Il y a deux raisons d’éviter cette fragmentation par les routeurs
- À l’entrée du réseau, le routeur doit retenir le paquet le temps de le fragmenter
- À la sortie du réseau, il faut attendre tous les fragments du datagramme puis effectuer un réassemblage coûteux
Les messages qui doivent absolument être livrés
- Le système de snapshots compense la perte des datagrammes UDP sur le réseau, mais certains messages et certaines commandes doivent absolument être transmis
- C’est par exemple le cas lorsqu’un joueur quitte la partie ou quand le serveur demande au client de charger un nouveau niveau
- Cette garantie est abstraite par NetChannel
Lectures liées
Aucun commentaire pour le moment.