Etape 4 – Bonus et état du jeu

Un premier problème qui se pose lors de l'évolution de l'état est celui des conflits, qui impliquent deux joueurs ou plus et qui doivent être résolus de manière équitable.

Différents conflits peuvent se présenter lors d'une partie. Par exemple, deux joueurs peuvent arriver au même coup d'horloge au centre d'une case contenant un bonus, auquel cas il faut décider lequel de ces joueurs l'obtient. Ou alors, deux joueurs peuvent tenter de déposer une bombe sur une case (qui peut en contenir au plus une) au même coup d'horloge, et là aussi, il faut décider d'un vainqueur.

On peut imaginer plusieurs techniques de résolution des conflits.

La première, très simple, consiste à ordonner les joueurs d'une manière ou d'une autre, par exemple dans l'ordre de leur numéro (de 1 à 4), puis de résoudre tous les conflits en faveur du joueur ayant le plus petit numéro. Cette technique n'est bien entendu pas équitable, car elle favorise systématiquement certains joueurs, et nous ne la retiendrons donc pas.

Une autre technique consiste à utiliser le hasard : lors de chaque conflit, un vainqueur est désigné aléatoirement. Cette technique a l'avantage d'être équitable, et pourrait très bien être retenue. Elle est d'ailleurs utilisées par de nombreux jeux de société, dans lesquels les dés fournissent les valeurs aléatoires nécessaires.

Nous lui préférerons néanmoins une troisième technique, qui a le petit avantage d'être plus prévisible. Elle consiste à calculer toutes les permutations des joueurs, puis à utiliser à chaque coup d'horloge une autre de ces permutations pour résoudre les conflits, de manière cyclique.

Par exemple, admettons que le jeu ne comporte que trois joueurs. Dans ce cas, il y a 6 permutations des joueurs : (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) et (3, 2, 1).

Au coup d'horloge 0, on utilise la première de ces permutations, (1, 2, 3), pour résoudre les conflits. Ainsi, un conflit entre les joueurs 1 et 2 est résolu en faveur du joueur 1, un conflit entre les joueurs 2 et 3 en faveur du joueur 2, etc. Au coup d'horloge 1, on utilise la permutation suivante, et ainsi de suite jusqu'au coup d'horloge 6, où on utilise à nouveau la première permutation.

Cette technique est équitable, dans le sens où, pour n'importe quel conflit (c-à-d n'importe quel sous-ensemble des joueurs de taille 2 ou plus), la résolution se fait en faveur de chaque membre du conflit le même nombre de fois sur l'ensemble des permutations. Par exemple, dans le cas d'un jeu à trois joueurs, on peut vérifier qu'un conflit impliquant les joueurs 2 et 3 est résolu :

• 3 fois en faveur du joueur 2 (permutations (1, 2, 3), (2, 1, 3) et (2, 3, 1)), et
• 3 fois en faveur du joueur 3 (permutations (1, 3, 2), (3, 1, 2) et (3, 2, 1)).

Il en va de même pour toute autre paire ou triplet de joueurs en conflit.

Dans le cadre de cette étape, nous nous intéresserons à l'évolution d'un seul élément du jeu : les particules d'explosion. L'évolution des autres éléments est laissée aux étapes ultérieures, entre autres car leur mise en œuvre nécessite des concepts qui n'ont pas encore été vus au cours.

Deux éléments sont à prendre en compte lors du calcul de l'évolution des particules d'explosion :

1. les particules déjà présentes sur le plateau et occupant la même position qu'un bloc libre se déplacent, tandis que celles occupant un autre bloc (mur ou bonus) ne peuvent s'en échapper et disparaissent,
2. les explosions actives produisent de nouvelles particules.

Cela implique que, pour déterminer les particules de l'état suivant, il faut (et il est suffisant de) connaître : les particules en cours de déplacement, la configuration du plateau et les explosions.

Une question se pose néanmoins à ce stade déjà : quelles versions du plateau de jeu et des explosions utiliser ? Celles de l'état courant, ou celles de l'état suivant ?

Ce choix est important, car il influence le comportement du jeu de manière subtile. Pour l'illustrer, considérons le cas d'un mur destructible en train de s'écrouler qui disparaît au coup d'horloge t (car il a terminé sa période d'écroulement et il est remplacé par un bloc libre) et une particule d'explosion qui occupe la même case au même coup d'horloge. Si on utilise l'état du plateau au coup d'horloge t pour calculer les particules au coup t + 1, alors la particule en question est bloquée par le mur, qui n'a pas encore disparu. Par contre, si on utilise l'état du plateau au coup d'horloge t + 1 (c-à-d le prochain état du plateau), la particule continue sa course.

Ces deux variantes sont illustrées dans la figure ci-dessous. La première, consistant à d'abord (tenter de) déplacer les particules sur le plateau actuel puis à calculer le nouveau plateau, est illustrée en haut. La seconde, consistant à d'abord calculer le nouveau plateau, puis à y déplacer les particules, est illustrée en bas.

Le choix de l'ordre dans lequel calculer les composantes du nouvel état est en grande partie arbitraire, dans le sens où il n'y a pas de solution qui soit meilleure que les autres. Nous avons donc choisi un ordre, décrit dans cette étape et les suivantes, et il est capital que vous le respectiez à la lettre, faute de quoi votre jeu aura un comportement non conforme.

Dans le cas des particules d'explosion, nous avons choisi d'effectuer le calcul des particules au temps t + 1 en fonction du plateau et des explosions au temps t. Dès lors, une interaction telle que celle illustrée à la figure 2 résultera en l'arrêt de la particule (variante du haut).

Le calcul de la liste des permutations d'une liste se fait élégamment de manière récursive, sachant que :

• la liste des permutations d'une liste vide est une liste comportant un seul élément : la liste vide,
• la liste des permutations d'une liste non vide s'obtient en calculant récursivement les permutations de la queue de cette liste (c-à-d la liste amputée de son premier élément), puis en insérant son élément de tête dans chacune des permutations ainsi obtenues, à chaque position possible.

Par exemple, pour calculer les permutations de la liste [1, 2, 3], on procède ainsi :

• la liste [1, 2, 3] n'étant pas vide, on calcule récursivement les permutations de sa queue, c-à-d la liste [2, 3], et on obtient la liste de permutations [[2, 3], [3, 2]],
• pour chaque permutation de la queue, on insère l'élément de tête, 1, à chaque position possible, ce qui donne :
  • pour la permutation [2, 3] : [[1, 2, 3], [2, 1, 3], [2, 3, 1]],
  • pour la permutation [3, 2] : [[1, 3, 2], [3, 1, 2], [3, 2, 1]],
• en combinant ces deux listes, on obtient bien le résultat escompté, à savoir la liste [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]].

Pour traduire cet algorithme en Java, pensez à utiliser la méthode subList de l'interface List.

La méthode applyTo pourrait être définie directement dans l'énumération Bonus, p.ex. au moyen d'un énoncé switch, mais il est plus propre d'en définir une version différente pour chacune des deux valeurs de l'énumération, ce qui est possible en Java. Etant donné que la syntaxe pour faire cela n'a pas été vue au cours, le squelette de la définition de cette énumération est donné ci-dessous :

public enum Bonus {
  INC_BOMB {
    @Override
    public Player applyTo(Player player) { /* … code */ }
  },

  INC_RANGE {
    @Override
    public Player applyTo(Player player) { /* … code */ }
  };

  abstract public Player applyTo(Player player);
}

Pour associer un bonus à un bloc, plusieurs solutions existent. Celle que nous vous proposons d'utiliser consiste à ajouter un attribut privé à l'énumération Block, de type Bonus, et contenant le bonus correspondant au bloc, ou null s'il n'y en a pas. Cet attribut doit être initialisé lors de la construction des blocs.

L'ajout d'attributs et de constructeurs (privés uniquement) aux énumérations est autorisé en Java, mais n'a pas été présenté au cours. Pour cette raison, un squelette vous est à nouveau fourni ci-dessous :

public enum Block {
  FREE, // … autres valeurs (murs)
  // BONUS_BOMB similaire à BONUS_RANGE
  BONUS_RANGE(Bonus.INC_RANGE);

  // bonus correspondant, ou null
  private Bonus maybeAssociatedBonus;

  // constructeur principal, utilisé par les blocs bonus
  private Block(Bonus maybeAssociatedBonus) {
    // … stocke l'argument dans l'attribut
  }

  // constructeur par défaut, utilisé par les autres blocs
  private Block() {
    // … stocke null dans l'attribut
  }

  // … autres méthodes
}

La méthode winner a pour but de retourner le vainqueur de la partie, or celui-ci n'existe pas bien entendu pas toujours. Par exemple, au tout début d'une partie il n'y a pas de vainqueur, ni à la fin du temps réglementaire si au moins deux joueurs sont encore vivants.

Dès lors, la méthode winner doit, d'une manière ou d'une autre, pouvoir retourner une valeur indiquant l'absence de vainqueur. Une solution souvent utilisée en Java consiste à retourner null dans ce cas, et nous pourrions l'adopter ici.

Cette solution a toutefois deux défauts :

1. le fait que la méthode winner puisse potentiellement retourner null n'est pas explicite dans son type, et il est donc facile de l'oublier,
2. la valeur null n'est pas un objet, et ne possède donc pas de méthode ; dès lors, certaines opérations que l'on effectue très souvent sur les valeurs potentiellement nulles ne peuvent être mise en œuvre une fois pour toutes sous forme de méthode de ce genre de valeurs.

La bibliothèque Java offre depuis peu la classe java.util.Optional, générique et immuable, qui a pour but de résoudre ces deux problèmes, et représente une valeur potentiellement inexistante. En gros, il s'agit d'une cellule du même genre que celles présentées dans le cours sur la généricité, mais qui d'une part peut être vide, et d'autre part possède plusieurs méthodes fort utiles.

Par exemple, une opération que l'on effectue souvent sur une valeur potentiellement nulle est de tester si elle est effectivement nulle, et si tel est le cas, lui substituer une valeur par défaut. Une manière de faire cela en Java consiste à utiliser l'opérateur ternaire (?:). Ainsi, admettons que l'on ait une variable, maybeName, potentiellement nulle, et que l'on désire définir une autre variable, name, qui ait la valeur anonyme si maybeName est nulle, ou la même valeur que maybeName sinon. Au moyen de l'opérateur ternaire, cela se fait ainsi :

String maybeName = …; // peut être null
String name = (maybeName == null)
  ? "anonyme"
  : maybeName;

Malheureusement, comme on l'a dit, le fait que maybeName puisse être nulle n'est pas apparent dans son type (uniquement dans son nom, choisi en conséquence). De plus, le code ci-dessus n'est pas très facile à lire. En utilisant la classe Optional, on peut l'écrire de manière beaucoup plus claire, grâce à la méthode orElse qu'elle fournit et qui retourne la valeur de la cellule si elle n'est pas vide, ou la valeur passée en argument sinon :

Optional<String> maybeName = …; // peut être vide
String name = maybeName.orElse("anonyme");

Le fait que maybeName et name aient un type différent dans la seconde version est très utile. Par exemple, si on commet l'erreur d'utiliser plus tard la variable maybeName au lieu de la variable name, p.ex. dans le code suivant :

int nameLength = maybeName.length();

l'erreur ne sera pas détectée à la compilation dans le premier cas (une NullPointerException sera levée à l'exécution), alors qu'il le sera dans le second.

Prenez un moment pour bien comprendre la classe Optional en lisant sa documentation, car nous l'utiliserons à plusieurs occasions dans ce projet. Sachez toutefois que pour écrire la méthode winner, vous n'aurez besoin que de ses méthodes of et empty.

Le calcul de l'état du jeu au prochain coup d'horloge est de loin la partie la plus complexe du serveur, et même du projet dans son ensemble. Pour cette raison, ce calcul ne sera pas effectué uniquement dans la méthode (publique) next mentionnée plus haut, mais il sera découpé en plusieurs méthodes privées utilisées par elle.

Etant donné que ce découpage n'est pas trivial, nous vous donnerons des suggestions à son sujet. Sachant qu'elles n'affectent pas l'interface publique de la classe, vous n'êtes pas obligés de les suivre, mais soyez sûrs d'avoir de bonnes raisons avant de choisir une solution différente de la nôtre. De plus, expliquez ces raisons au moyen de commentaires dans votre code, afin de faciliter le travail de correction !

La règle que nous vous suggérons de suivre pour découper la mise à jour de l'état est la suivante : pour chaque composante de l'état (joueurs, bombes, etc.), écrivez une méthode privée et statique chargée de calculer la prochaine valeur de cette composante, en fonction des composantes de l'état actuel ou futur nécessaires.

Par exemple, étant donné ce qui a été dit plus haut concernant l'évolution des particules d'explosion, celle-ci peut être effectuée par la méthode privée et statique suivante :

• List<Sq<Cell>> nextBlasts(List<Sq<Cell>> blasts0, Board board0, List<Sq<Sq<Cell>>> explosions0), qui calcule les particules d'explosion pour l'état suivant étant données celles de l'état courant, le plateau de jeu courant et les explosions courantes.

Le suffixe 0 attaché aux noms d'arguments rappelle qu'il s'agit des valeurs au coup d'horloge actuel, celles du coup d'horloge suivant ayant un suffixe 1. Nous vous conseillons d'adopter cette convention dans votre programme, pour éviter toute ambiguïté.

Pourquoi faire de nextBlasts une méthode statique, ce qui force à lui passer les parties de l'état courant dont elle dépend, alors qu'une méthode non statique pourrait utiliser à sa guise les parties de l'état dont elle dépend ? Premièrement car cela rend explicite les parties de l'état dont elle dépend, ce qui facilite la compréhension du code, et deuxièmement car dans certaines situations il sera nécessaire d'utiliser des composantes du prochain état pour calculer d'autres composantes de ce même prochain état, comme expliqué plus haut.

La méthode nextBlasts n'est pas longue (7-8 lignes), mais étant donné qu'il s'agit de la première méthode utilisant les séquences pour faire évoluer temporairement l'état, il est utile d'en détailler quelque peu le fonctionnement.

Nous l'avons vu, les particules d'explosion au coup d'horloge suivant proviennent de deux sources :

1. les particules en déplacement existant au coup d'horloge actuel, qui se déplacent sauf si elles sont arrêtées par un bloc non libre,
2. les particules émises par les explosions actives au coup d'horloge actuel.

Les particules en déplacement existant au coup d'horloge actuel (le paramètre blasts0 de la méthode nextBlasts) sont, pour mémoire, représentées par des séquences. A chaque particule correspond une séquence, dont la tête représente la position actuelle, et la queue les positions futures.

Déplacer ces particules revient à vérifier tout d'abord que le bloc se trouvant à la position actuelle de la particule est bien libre. Si tel est le cas, la particule est « déplacée » simplement en ajoutant la queue de la séquence qui la représente aux particules du coup d'horloge suivant, à supposer que cette queue ne soit pas vide. Si la queue est vide, cela signifie que la particule a parcouru la distance maximale qu'elle pouvait parcourir, et doit donc disparaître « naturellement ».

Les explosions actives (le paramètre explosions0 de la méthode nextBlasts) sont, pour mémoire, représentées par des séquences de séquences. L'ensemble des particules émises par les explosions au coup d'horloge actuel n'est donc rien d'autre que l'ensemble des têtes des séquences représentant les explosions. Chacune de ces têtes, une séquence de cases, représente une particule en déplacement et doit être ajouté aux particules du coup d'horloge suivant.

Pour mettre ce comportement en œuvre, vous aurez besoin des méthodes isEmpty, head et tail des séquences.