Etape 8 – Sérialisation de l'état

Le codage par plages (run length encoding) est une technique de représentation de séquences de valeurs qui permet de compresser celles qui contiennent de nombreuses répétitions. Son idée est de représenter les parties répétitives (les plages) de la séquence à encoder par leur longueur et la valeur qui les constitue.

Par exemple, la séquence de 19 lettres ci-dessous est constituée de quatre plages successives, chacune formée d'un certain nombre de répétitions d'une seule et même lettre :

aaaaaaaabbbcccccccd

En codant cette séquence par plages, on en obtient une représentation beaucoup plus compacte :

8a3b7c1d

qui exprime le fait qu'elle est constituée de 8 répétitions de la lettre a, 3 de la lettre b, 7 de la lettre c et 1 de la lettre d.

Cette technique de codage compresse de manière très efficace les séquences contenant de nombreuses (et longues) répétitions, ce qui est justement le cas de la représentation du plateau de jeu et des bombes et explosions.

Le plateau de jeu et les bombes et explosions sont représentés par des séquences d'octets — les numéros des images à utiliser pour les dessiner — et non pas par des séquences de lettres comme dans l'exemple ci-dessus. Néanmoins, il n'est pas difficile d'adapter l'idée du codage par plages à ces séquences.

La technique que nous utiliserons ici est une version un peu améliorée de celle suggérée plus haut. Elle tire parti du fait que les octets composant les séquences représentant le plateau de jeu et les explosions sont tous positifs et inférieurs à 127 (le plus grand entier positif représentable avec un octet, en complément à deux). On peut s'en persuader en regardant les numéros attachés aux images représentant ces éléments, fournis lors de l'étape précédente.

Dès lors, il est possible d'utiliser les valeurs négatives pour encoder les longueurs des plages, et représenter sans encodage les plages de longueur 1 ou 2. On garantit ainsi que la séquence encodée n'est jamais plus longue que la séquence originale, propriété qui n'est pas vraie du codage par plages en général.

Dans cette version du codage par plages, les plages de longueur 1 ou 2 sont donc représentées par le(s) octet(s) qui les constituent, tandis que les plages plus longues sont représentées par une paire d'octets : le premier est négatif et sa valeur absolue est égale à la longueur de la plage moins 2, tandis que le second est positif et donne l'octet constituant la plage.

Par exemple, la séquence d'octets ci-dessous :

10, 10, 10, 20, 20, 30, 20, 30, 40, 40, 40, 40, 40, 40

est encodée par cette technique en :

-1, 10, 20, 20, 30, 20, 30, -4, 40

Sachant que le plus petit octet négatif vaut -128, toute plage de longueur inférieure ou égale à 130 peut être représentée par une paire d'octets, les autres en nécessitent deux ou plus.

Certains éléments de l'état à sérialiser peuvent avoir une valeur supérieure à 127. Par exemple, la coordonnée x de la position du joueur est comprise entre 0 et 239. A première vue, cela peut sembler impliquer qu'il n'est pas possible de représenter une telle valeur au moyen d'un seul octet, car un octet ne peut représenter qu'une valeur comprise entre -128 et 127, en complément à deux.

Toutefois, étant donné qu'il n'y a que 240 coordonnée x différentes, et qu'un octet permet de représenter 255 valeurs, il est clairement possible de n'utiliser qu'un octet pour la représenter. Pour cela, il suffit simplement de changer de point de vue et de considérer que certains octets de l'état sérialisé doivent être interprétés comme des valeurs non signées, tandis que d'autres doivent être interprétées comme des valeurs signées (en complément à deux).

Par exemple, l'octet constitué des 8 bits 11111111 peut être interprété de deux manières :

1. en valeur non signée, il représente l'entier 255,
2. en valeur signée (complément à deux), il représente l'entier -1.

Il est important de savoir quels octets de l'état doivent être interprétés comme signés ou non, car cela influence la manière dont ils doivent être traités lors du décodage. Dès lors, dans ce qui suit, nous distinguerons explicitement ces deux types d'octets.

L'état d'une partie de XBlast est sérialisé en plaçant les uns après les autres les quatre éléments suivants :

1. le plateau de jeu, compressé,
2. les explosions et bombes, compressées,
3. l'état des quatre joueurs,
4. le temps restants.

La version compressée du plateau et des explosions est sérialisée comme suit :

• un octet non signé, qui donne la taille, en octets, de la séquence compressés qui suit,
• tous les octets signés composant la séquence compressée.

La classe Level du paquetage ch.epfl.xblast.server, publique, finale et immuable, représente un niveau de jeu XBlast. Un niveau n'est rien d'autre qu'une paire composée d'un peintre de plateau — qui donne le style graphique du niveau — et d'un état de jeu initial — qui donne ses autres paramètres : positions et capacités initiales des joueurs, etc.

Cette classe offre un constructeur, prenant en argument le peintre de plateau (de type BoardPainter) et l'état initial (de type GameState), et deux accesseurs, un pour chacune de ces valeurs.

En plus de ces méthodes, la classe Level offre un champ statique et final, nommé p.ex. DEFAULT_LEVEL et contenant le niveau par défaut. Le peintre de plateau de ce niveau est celui qui permet d'obtenir le dessin présenté dans la vidéo de l'introduction au projet, et son état initial est celui illustré au début de la vidéo de l'énoncé de l'étape 6. (Ces deux niveaux sont les mêmes, mais la première vidéo ne montre pas l'état initial.)

Le résultat du processus de sérialisation est représenté en Java par une liste d'octets, de type List<Byte>. On peut dès lors se poser la question de savoir comment distinger les octets signés et non signés.

En réalité, il s'agit d'un faux problème, car cette distinction ne doit pas être faite au moment de la sérialisation de l'état, mais uniquement au moment de sa désérialisation.

Pour comprendre cela, un exemple est utile. Imaginons que l'on désire représenter la coordonnée x de la position d'un joueur, et que celle-ci vaille 224. Si on tente de stocker cette valeur dans une variable de type byte puis de l'afficher, on obtient -32 :

byte x = (byte)224;
System.out.println(x);          // affiche -32

Il semble donc que l'on ait un problème. Mais il n'en est rien, car les bits qui constituent la valeur sont corrects, ils sont juste interprétés de manière non conforme à nos désirs au moment de l'impression ! En effet, la représentation binaire de -32 en complément à deux est 11100000, tout comme la représentation de 224 (mais pas en complément à deux !).

Java interprète toujours les valeurs des types entiers (char excepté) comme des valeurs signées en complément à deux. Dès lors, du point de vue de Java, la valeur contenue dans la variable x ci-dessus est bien -32. Cela dit, la bibliothèque Java offre des méthodes permettant de convertir une valeur d'un type entier donné en un autre type entier plus grand, en considérant la valeur comme non signée au moment de la conversion.

Ainsi, la méthode toUnsignedInt de la classe Byte permet d'interpréter une valeur de type byte comme un octet non signé, et d'obtenir la valeur de type int correspondant. En l'utilisant, on peut interpréter (et donc imprimer) correctement l'octet non signé ci-dessus :

byte x = (byte)224;
int xUnsigned = Byte.toUnsignedInt(x);
System.out.println(xUnsigned);  // affiche 224

En conclusion, il n'y a aucune distinction à faire entre octets signés et non signés au moment de la sérialisation. Cette distinction devra se faire au moment de la désérialisation — lors d'une étape ultérieure — et sera facilitée par l'existence de la méthode toUnsignedInt.

La classe RunLengthEncoder du paquetage ch.epfl.xblast, publique, finale et non instanciable, représente un codeur/décodeur par plages. Elle offre deux méthodes publiques (et statiques) :

• la première, nommée p.ex. encode, prend en argument une liste d'octets de type List<Byte> et retourne la liste codée par plages (selon la technique décrite plus haut) ou lève IllegalArgumentException si l'un des éléments de la liste reçue est négatif,
• la seconde, nommée p.ex. decode, prend en argument une liste d'octets de type List<Byte> et retourne sa version décodée par plages ou lève IllegalArgumentException si la liste reçue se termine par une valeur négative.

La classe GameStateSerializer du paquetage ch.epfl.xblast.server, publique, finale et non instanciable, représente un sérialiseur d'état de jeu. Elle offre une unique méthode publique (et statique), nommée p.ex. serialize et qui, étant donné un peintre de plateau (de type BoardPainter) et un état de jeu (de type GameState), retourne la version sérialisée de l'état, sous forme d'une liste d'octets de type List<Byte>.

Pour vous aider à tester cette étape, nous vous donnons ci-dessous la liste correspondant à la sérialisation de l'état initial du niveau par défaut. Cette liste contient 144 octets et les quatre groupes correspondant aux principaux éléments — plateau, bombes et explosions, joueurs, temps restant — ont été visuellement séparés pour faciliter la lecture.

[121, -50, 2, 1, -2, 0, 3, 1, 3, 1, -2, 0, 1, 1, 3, 1, 3,
 1, 3, 1, 1, -2, 0, 1, 3, 1, 3, -2, 0, -1, 1, 3, 1, 3, 1,
 3, 1, 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2,
 3, 1, 0, 0, 3, 1, 3, 1, 0, 0, 1, 1, 3, 1, 1, 0, 0, 1, 3,
 1, 3, 0, 0, -1, 1, 3, 1, 1, -5, 2, 3, 2, 3, -5, 2, 3, 2,
 3, 1, -2, 0, 3, -2, 0, 1, 3, 2, 1, 2,

 4, -128, 16, -63, 16,

 3, 24, 24, 6,
 3, -40, 24, 26,
 3, -40, -72, 46,
 3, 24, -72, 66,

 60]

Notez bien que tous les octets ci-dessus ont été interprétés comme signés par Java, et certaines valeurs affichées comme négatives seront interprétées comme positive au moment de la désérialisation. Il en va ainsi de la position des joueurs 2 à 4, par exemple.