Etape 1 – Cases et sous-cases

1 Introduction

Le but de cette première étape est de définir les classes permettant d'identifier la position des différents éléments du jeu sur le plateau. Celui-ci est découpé à deux niveaux de granularité, que nous nommerons les cases et les sous-cases. Les joueurs sont positionnés à la granularité des sous-cases, tandis que tous les autres éléments du jeu sont positionnés à la granularité des cases.

1.1 Cases

Au niveau de granularité le plus grossier, le plateau de jeu est découpé en 13 lignes de 15 cases chacune, pour un total de 195 cases.

Chaque case du plateau est identifiée par sa position sur le plateau, donnée par une paire de coordonnées entières (x, y). La première de ces coordonnées (x) désigne la colonne, la seconde (y) désigne la ligne. Chacune de ces composantes est positive, 0 désignant la première colonne ou ligne. La case (0,0) se trouve dans le coin nord-ouest (haut-gauche) du plateau.

Ces conventions sont illustrées sur l'image ci-dessous qui montre le découpage du plateau en cases, ainsi que les coordonnées des quatre cases des coins.

Sorry, your browser does not support SVG.

Figure 1 : Découpage du plateau de jeu en 195 cases (13 lignes, 15 colonnes)

Chaque case possède quatre voisines : une au nord (en haut), une à l'est (à droite), une au sud (en bas) et une à l'ouest (à gauche). Cela est vrai même pour les cases se trouvant dans les bords du plateau, leur voisines étant par convention celles du bord opposé. Cela revient à considérer que le plateau est un tore.

Par exemple, les quatre cases voisines de la case (0,0) sont :

  1. la case (0,12) au nord,
  2. la case (1,0) à l'est,
  3. la case (0,1) au sud,
  4. la case (14,0) à l'ouest.

1.2 Sous-cases

Au niveau de granularité le plus fin, chaque case du plateau est subdivisée en 16 lignes de 16 colonnes de sous-cases.

L'image ci-dessous montre le découpage en sous-cases des quatre cases du coin nord-ouest du plateau, ainsi que les coordonnées des sous-cases aux quatre coins. Attention, étant donné que le plateau n'est pas montré en entier, la sous-case dans le coin bas-droite de l'image n'est pas la sous-case bas-droite du plateau. Cette dernière a les coordonnées (239,207).

Sorry, your browser does not support SVG.

Figure 2 : Découpage des cases en 256 cases (16 lignes de 16 colonnes)

La sous-case se trouvant à 8 lignes et 8 colonnes du coin nord-ouest de la case la contenant est définie comme étant la sous-case centrale de sa case, même si elle ne se trouve bien entendu pas exactement au centre. Sur l'image ci-dessus, les sous-cases centrales des quatre cases visibles sont coloriées en jaune.

Tout comme les cases, les sous-cases possèdent chacune exactement quatre voisines, une dans chaque direction.

1.3 Ordonnancement des cases

Il est parfois utile d'ordonner les cases du plateau en une séquence linéaire. Il existe un très grand nombre de manières d'ordonner les cases en une séquence linéaire, mais nous n'en utiliserons que deux dans ce projet :

  1. l'ordre de lecture,
  2. l'ordre en spirale.

L'ordre de lecture consiste à partir de la case de coordonnées (0,0) et à poursuivre dans l'ordre dans lequel on lit les caractères sur une page, c-à-d de gauche à droite et de haut en bas. En informatique, cette manière d'ordonner les éléments d'un tableau bidimensionnel est souvent appelé row-major order, terminologie que nous utiliserons ici.

L'ordre en spirale consiste à partir de la case de coordonnées (0,0) puis à continuer en spirale, en commençant par la première ligne.

Ces deux manières d'ordonner les cases sont présentées dans la figure ci-dessous pour un petit plateau de 3 lignes de 4 colonnes chacune. Le numéro inscrit dans chaque case correspond à son index dans l'ordre illustré, la première case ayant l'index 0.

Sorry, your browser does not support SVG.

Figure 3 : Ordre de lecture (à gauche) et en spirale (à droite)

2 Mise en œuvre Java

Les différents concepts utiles à la réalisation de cette étape ayant été décrits, il reste à voir comment les mettre en œuvre en Java. Les sections ci-dessous énumèrent les différentes classes, interface et énumérations à écrire dans ce but.

Prenez bien garde à écrire exactement ce qui vous est demandé, jusque dans les moindres détails. Par exemple, si une classe est décrite comme étant « finale », la vôtre doit l'être. Et si une méthode est décrite comme levant une exception donnée dans une certaine situation, votre méthode doit faire de même.

Toutes les classes et interfaces de ce projet appartiendront au paquetage ch.epfl.xblast ou à l'un de ses sous-paquetages.

Attention : avant de créer votre projet, il vous faut absolument configurer Eclipse en fonction des instructions données dans ce document. N'oubliez surtout pas de le faire, faute de quoi votre projet sera refusé par notre système de rendu et vous n'obtiendrez aucun point !

2.1 Enumération Direction

L'énumération Direction du paquetage ch.epfl.xblast, publique, définit les quatre directions utilisées dans le jeu, à savoir (dans l'ordre) :

  1. N, pour nord,
  2. E, pour est,
  3. S, pour sud,
  4. W, pour ouest (west en anglais).

Cette énumération définit de plus les méthodes suivantes :

  • Direction opposite(), qui retourne la direction opposée de celle à laquelle on l'applique (S pour N, W pour E, etc.),
  • boolean isHorizontal(), qui retourne vrai si et seulement si la direction à laquelle on l'applique est horizontale à l'écran (E ou W),
  • boolean isParallelTo(Direction that), qui retourne vrai si et seulement si la direction à laquelle on l'applique est parallèle à la direction that (une direction n'est parallèle qu'à elle-même et à sa direction opposée).

2.2 Classe Cell

La classe Cell du paquetage ch.epfl.xblast, publique, finale et immuable, représente une case. Elle possède plusieurs attributs publics et statiques. Les trois premiers d'entre eux, de type int, donnent des informations concernant les dimensions du plateau :

  • COLUMNS, le nombre de colonnes du plateau (15),
  • ROWS, le nombre de lignes du plateau (13),
  • COUNT, le nombre total de cases du plateau (le produit de COLUMNS et ROWS).

Les deux attributs suivants sont des tableaux dynamiques de cases, de type List<Cell> (et non pas ArrayList<Cell>, pour une raison expliquée plus bas), contenant la totalité des cases du plateau, ordonnées selon les ordres décrits précédemment :

  • ROW_MAJOR_ORDER, la totalité des cases du plateau en ordre de lecture,
  • SPIRAL_ORDER, la totalité des cases du plateau en ordre spirale.

La technique à utiliser pour initialiser ces attributs est décrite plus bas, de même que le type List.

En plus de ces attributs statiques, la classe Cell offre un unique constructeur publique :

  • Cell(int x, int y), qui construit la case avec les coordonnées x et y données ; des valeurs quelconques sont acceptées pour les coordonnées, mais elles sont normalisées avant d'être stockées, c-à-d ramenées à un entier compris entre 0 et 14 (inclus) pour x, et entre 0 et 12 (inclus) pour y (voir plus bas).

Finalement, la classe Cell offre les méthodes publiques suivantes :

  • int x(), qui retourne la coordonnée x normalisée de la case,
  • int y(), qui retourne la coordonnée y normalisée de la case,
  • int rowMajorIndex(), qui retourne l'index de la case dans l'ordre de lecture,
  • Cell neighbor(Direction dir), qui retourne la case voisine, dans la direction donnée ; sachant que le plateau de jeu est (conceptuellement) torique, cette voisine existe toujours.
  • boolean equals(Object that), qui redéfinit la méthode equals de Object et retourne vrai si et seulement si l'objet that est une case et ses coordonnées normalisées sont identiques à celles de la case réceptrice,
  • String toString(), qui redéfinit la méthode toString de Object et retourne une représentation textuelle de la case, constituée de ses coordonnées entre parenthèses, p.ex. (14,12) pour la case du coin sud-est.

La redéfinition de la méthode toString n'est pas indispensable, mais peut faciliter le déboguage et les tests.

Notez que cette classe n'est pas complète, il lui manque encore une redéfinition de la méthode hashCode. Il vous sera demandé de l'ajouter dans une étape ultérieure, une fois que son utilité aura été étudiée dans le cours.

2.2.1 Initialisation de ROW_MAJOR_ORDER et SPIRAL_ORDER

Pour initialiser ROW_MAJOR_ORDER et SPIRAL_ORDER, il est conseillé de définir deux méthodes statiques privées calculant et retournant le tableau dynamique des cases dans l'ordre désiré, puis de le rendre non modifiable avant de le stocker dans l'attribut statique.

Par exemple, ROW_MAJOR_ORDER pourrait être initialisée ainsi :

public static final List<Cell> ROW_MAJOR_ORDER =
  Collections.unmodifiableList(rowMajorOrder());
private static ArrayList<Cell> rowMajorOrder() { /* … */ }

La méthode unmodifiableList de Collections permet de rendre le tableau dynamique retourné par rowMajorOrder non modifiable, ce qui garantit que son contenu ne changera jamais. Le type de retour de cette méthode est List et non pas ArrayList, mais pour l'instant vous pouvez considérer que les deux sont équivalents. La différence entre ces deux types sera expliquée dans le cours sur les listes.

2.2.2 Calcul de SPIRAL_ORDER

Si la construction de la liste contenant les cases dans l'ordre de lecture (row-major) est facile, celle de la liste les contenant dans l'ordre en spirale ne l'est pas vraiment.

Pour comprendre comment la construire, il est important de faire la constatation suivante : la première ligne du plateau contient le début de cette liste. On peut assez facilement en tirer parti pour construire l'ordre spirale, conceptuellement en tout cas, ainsi :

  1. on ampute le plateau de sa première ligne, dont les cases sont déjà dans le bon ordre (l'ordre spirale),
  2. on tourne le plateau d'un quart de tour dans le sens contraire des aiguilles d'une montre,
  3. on recommence jusqu'à ce que tout le plateau ait été ainsi consommé.

Cette procédure est partiellement illustrée dans la figure ci-dessous pour un petit plateau de 3 lignes et 4 colonnes. De gauche à droite, on y voit :

  1. le plateau original, dont on désire ordonner les cases en spirale,
  2. la première ligne du plateau, qui est le début de la liste des cases en spirale, et le plateau amputé de cette ligne,
  3. le plateau amputé et tourné d'un quart de tour dans le sens contraire des aiguilles d'une montre.

Sorry, your browser does not support SVG.

Figure 4 : Calcul de l'ordre en spirale

Il est facile de voir qu'en appliquant cette technique jusqu'au bout au plateau de la figure ci-dessus, on obtient bien les cases dans l'ordre spirale, à savoir :

[(0,0), (1,0), (2,0), (3,0), (3,1), (3,2),
 (2,2), (1,2), (0,2), (0,1), (1,1), (2,1)]       

Cette technique de construction peut être transformée en l'algorithme ci-dessous (en pseudo-code), qui calcule la liste des cases d'un plateau de jeu en ordre spirale. Les paramètres de cet algorithme sont width et height, les dimensions du plateau, et son résultat est le tableau spiral qui contient les cases en spirale.

 1: ix = [ 0, 1, …, width - 1 ]
 2: iy = [ 0, 1, …, height - 1 ]
 3: horizontal = vrai
 4: spiral = []
 5: tant que ni ix, ni iy n'est vide :
 6:   i1 = ix si horizontal, iy sinon
 7:   i2 = iy si horizontal, ix sinon
 8:   c2 = premier élément de i2 (supprimé de i2)
 9:   pour tout c1 de i1 :
10:     c = (c1, c2) si horizontal, (c2, c1) sinon
11:     spiral = spiral + c
12:   i1 = inverse(i1)
13:   horizontal = !horizontal

Cet algorithme s'inspire de la technique décrite plus haut, mais sans réellement créer, amputer et tourner le plateau. Au lieu de cela, la rotation est mise en œuvre par la combinaison de :

  • la variable horizontal, qui est vraie lorsqu'une ligne doit être amputée, et fausse lorsqu'il s'agit d'une colonne,
  • l'inversion de la liste des indices à la ligne 12.

L'amputation de la première ligne est quant à elle effectuée par la suppression du premier élément d'une des deux listes d'index (ix ou iy), à la ligne 8.

Pour écrire la version Java de cet algorithme, vous pouvez vous aider des méthodes suivantes :

  • la méthode reverse de la classe Collections, qui inverse l'ordre des éléments du tableau dynamique lui passe,
  • la méthode remove de la classe ArrayList, qui supprime l'élément à la position donnée, en décalant d'un cran vers la gauche tous les éléments se trouvant à droite de celui supprimé.

2.2.3 Normalisation des coordonnées

La normalisation des coordonnées de la case doit être faite dans le constructeur. Cette solution est nettement préférable, car plus efficace, que celle consistant à normaliser les coordonnées dans les méthodes d'accès (x() et y()), car celles-ci peuvent être appelées souvent pour une case donnée.

Pour effectuer la normalisation, on pourrait penser utiliser l'opérateur de reste de la division entière Java (%) et écrire, dans le constructeur, quelque chose comme :

this.x = x % COLUMNS;

Malheureusement, cela est incorrect, car si x est négatif, l'expression x % COLUMNS est également négative (ou nulle).

Pour résoudre ce problème, il faut utiliser la méthode floorMod de la classe java.lang.Math. Cette méthode calcule le reste d'une autre version de la division entière que celle offerte par l'opérateur de division (/) en Java. Le reste de cette autre division a l'avantage de toujours avoir le même signe le diviseur, ce qui est souvent souhaitable. En particulier, cette méthode permet ici de normaliser correctement les valeurs de x et y passées au constructeur. Par exemple, -1 % 15 vaut -1, tandis que floorMod(-1, 15) vaut 14.

2.3 Classe SubCell

La classe SubCell du paquetage ch.epfl.xblast, publique, finale et immuable, représente une sous-case. Elle offre une unique méthode publique et statique :

  • SubCell centralSubCellOf(Cell cell), qui retourne la sous-case centrale de la case donnée.

En plus de cette méthode statique, la classe SubCell offre le constructeur public suivant :

  • SubCell(int x, int y), qui construit la sous-case de coordonnées x et y données ; comme pour les cases, des valeurs quelconques sont acceptées pour ces coordonnées, mais elles sont normalisées avant d'être stockées, en ramenant la coordonnée x à un entier compris entre 0 et 239, et la coordonnée y à un entier compris entre 0 et 207.

Cette classe possède de plus les méthodes publiques suivantes :

  • int x(), qui retourne la coordonnée x normalisée de la sous-case,
  • int y(), qui retourne la coordonnée y normalisée de la sous-case,
  • int distanceToCentral(), qui retourne la distance de Manhattan à la sous-case centrale la plus proche (voir plus bas),
  • boolean isCentral(), qui retourne vrai si et seulement si la sous-case est une sous-case centrale,
  • SubCell neighbor(Direction d), qui retourne la sous-case voisine, dans la direction donnée ; comme pour les cases, cette voisine existe toujours,
  • Cell containingCell(), qui retourne la case contenant cette sous-case.
  • boolean equals(Object that), qui redéfinit la méthode equals de Object et retourne vrai si et seulement si l'objet that est une sous-case et ses coordonnées normalisées sont identiques à celles de la sous-case réceptrice,
  • String toString(), qui redéfinit la méthode toString de Object et retourne une représentation textuelle de la sous-case, constituée de ses coordonnées entre parenthèses, p.ex. (239,207) pour la sous-case du coin sud-est.

Comme pour la classe des cases, il faudra ultérieurement ajouter une redéfinition de la méthode hashCode à la classe des sous-cases.

2.3.1 Distance de Manhattan entre sous-cases

La distance de Manhattan entre deux sous-cases est le plus petit nombre de sous-cases qu'il faut parcourir pour aller de l'une à l'autre, en se déplaçant uniquement horizontalement ou verticalement.

La figure ci-dessous illustre ce concept en donnant, pour chaque sous-cases d'un ensemble de 25 d'entre elles, la distance de Manhattan les séparant de la sous-case centrale, coloriée en jaune.

Sorry, your browser does not support SVG.

Figure 5 : Distance de Manhattan à une sous-case centrale (en jaune)

Notez que la formule permettant de calculer cette distance est très simple, et implique uniquement l'addition, la soustraction, le reste de la division et la valeur absolue. Cette dernière s'obtient au moyen de la méthode abs de la classe Math.

2.4 Tests

Pour vous aider à démarrer ce projet, nous vous fournissons exceptionnellement une archive Zip contenant des tests unitaires JUnit pour cette étape.

Pour pouvoir utiliser ces tests, il vous faut tout d'abord les importer dans votre projet en suivant les indications d'importation d'archive Zip dans Eclipse, puis ajouter la bibliothèque JUnit à votre projet, en suivant les explications à ce sujet.

Attention : nous ne garantissons pas l'exhaustivité de ces tests et nous nous réservons le droit d'utiliser des tests plus complets que ceux-ci pour noter votre projet.

En plus des tests unitaires, l'archive ci-dessus contient un fichier nommé NameCheck01.java. Les méthodes de la classe qu'il définit font référence à la totalité des noms des classes et méthodes de cette étape. Cela vous permet de vérifier que vous avez correctement nommé les différentes entités qu'il vous est demandé de programmer. Cela est très important, car la moindre faute dans un nom nous empêcherait d'exécuter nos tests unitaires lors du rendu testé de la mi-semestre.

Nous vous fournirons de tels fichiers pour toutes les étapes jusqu'au rendu testé, et il vous faut penser à vérifier qu'Eclipse en signale aucune erreur dans l'un de ces fichiers avant de faire un rendu, faute de quoi celui-ci se verrait refusé par notre système.

2.5 Documentation

Une fois les tests exécutés avec succès, il reste à documenter la totalité des entités publiques (classes, attributs et méthodes) définies dans cette étape, au moyen de commentaires Javadoc. Vous pouvez écrire ces commentaires en français ou en anglais, en fonction de votre préférence, mais vous ne devez utiliser qu'une seule langue pour tout le projet.

Les commentaires Javadoc sont des commentaires structurés que l'on peut attacher aux différentes entités d'un programme (classes, interfaces, attributs et méthodes). On les reconnaît au fait qu'ils commencent par une barre oblique suivie de deux astérisques (/**).

Les commentaires Javadoc peuvent inclure des étiquettes (tag), qui commencent par un arobas (@). Même s'il existe de nombreuses étiquettes, les plus importantes sont :

  1. L'étiquette @author, qui est suivie du nom d'un des auteurs de la classe ou interface à laquelle elle est attachée. Peut apparaître plusieurs fois s'il y a plus d'un auteur.
  2. L'étiquette @param, qui est suivie du nom d'un paramètre de l'entité à laquelle on l'attache (méthode ou constructeur) et d'une description de la signification de ce paramètre.
  3. L'étiquette @throws, qui est suivie du nom d'une exception qui peut être levée par la méthode à laquelle on l'attache et d'une description des cas dans lesquels elle est levée.
  4. L'étiquette @return, qui est suivie d'une description de la valeur retournée par la méthode à laquelle on l'attache.

Pour ce projet, vous avez l'obligation de lister la totalité des auteurs de chaque classe, interface ou énumération publique que vous rendez. Le prénom et le nom de chaque auteur doit être suivi de son numéro SCIPER entre parenthèses.

Pour illustrer l'utilisation des différentes étiquettes mentionnées plus haut, voici ce à quoi la documentation d'une classe modélisant un nombre rationnel pourrait ressembler :

/**
 * Un nombre rationnel.
 *
 * @author Marie Durand (654321)
 * @author Jean Dupond (123456)
 */
public final class Rational {
  private final int numerator, denominator;

  /**
   * Construit un nombre rationnel avec le numérateur
   * et le dénominateur donnés.
   *
   * @param numerator
   *            le numérateur
   * @param denominator
   *            le dénominateur (doit être non nul)
   * @throws IllegalArgumentException
   *             si le dénominateur est nul
   */
  public Rational(int numerator, int denominator) {
    if (!(denominator != 0))
      throw new IllegalArgumentException();
    this.numerator = numerator;
    this.denominator = denominator;
  }

  /**
   * Retourne le numérateur de ce nombre rationnel.
   * @return le numérateur de ce nombre rationnel
   */
  public int numerator() {
    return numerator;
  }

  // … méthodes
}

Deux commandes Eclipse sont d'une grande aide lorsqu'on rédige des commentaires Javadoc :

  1. Dans le menu Source, l'entrée Generate Element Comment permet de générer un squelette de commentaire Javadoc pour l'élément sous le curseur.
  2. Dans le menu Source, l'entrée Format Element permet de reformatter l'élément sous le curseur. Lorsqu'on l'utilise dans un commentaire Javadoc, celui est reformatté de manière plaisante.

3 Résumé

Pour cette étape, vous devez :

  • configurer Eclipse selon les indications données dans le document consacré à ce sujet,
  • écrire les classes Cell et SubCell ainsi que l'énumération Direction en fonction des spécifications données plus haut,
  • vérifier que les tests que nous vous fournissons s'exécutent sans erreur, et dans le cas contraire, corriger votre code,
  • documenter la totalité des entités publiques que vous avez définies,
  • (optionnel mais vivement recommandé) rendre votre code au plus tard le 26 février 2016 à 17h30, via le système de rendu.

Ce premier rendu n'est pas noté, mais celui de la prochaine étape le sera. Dès lors, il vous est fortement conseillé de faire un rendu de test cette semaine afin de vous familiariser avec la procédure à suivre.