CSC 3101 – Algorithmique et langage de programmation

CSC3101 – Contrôle Final 1 – Année 2018/2019

Durée: 2h, tout document papier autorisé

Le barème est donné à titre indicatif

Lorsque vous écrivez du code, essayez d'avoir un indentation à peu près correcte (une indentation trop incorrecte vous ferait perdre des points). Sauf si explicitement demandé, il n'est pas nécessaire :

de gérer les cas d'erreurs,
de donner la visibilité des champs, méthodes et constructeurs (en particulier, on supposera tous les champs publics),
d'indiquer les packages et les imports,
d'indiquer quelles exceptions peuvent être levées par une méthode dans sa signature (c'est-à-dire sa déclaration).

Le but de cette série d'exercice est de concevoir un jeu vidéo dans lequel le joueur doit construire des villes et détruire celles de ses adversaires. Le joueur possède donc des unités pouvant se déplacer sur une carte en deux dimensions. Ces unités servent à conquérir les villes adverses ou à créer de nouvelles villes. La carte est conçue comme une grille NxM, et chaque case de la grille représente un terrain (forêt, montagne, colline, plaine, mer). Le principe du jeu est assez simple : certaines unités spéciales permettent de fonder de nouvelles villes, et les villes servent principalement à fabriquer de nouvelles unités.

Les cases et la grille (5 points)

Pour commencer, nous concevons une case de la grille. Une case (classe Case) possède un type de terrain, une collection d'unité et une ville. On suppose, pour le moment, qu'on dispose d'une classe Terrain représentant un terrain quelconque, d'une classe Unité représentant une unité quelconque et d'une classe Ville représentant une ville.

1,5 point

Donnez le code de la classe Case avec ses champs. Ajoutez un constructeur à la classe Case s'occupant :

d'initialiser le terrain et la ville à null,
et d'initialiser la collection d'unités (c'est-à-dire, d'allouer une collection d'unités et d'affecter la référence vers cette collection au champs représentant les unités se trouvant dans la case).

On vous rappelle que, en Java, l'interface Collection<T> représente une collection quelconque, et que ArrayList<T> ou LinkedList<T> sont des mises en œuvre de cette interface.

1 point

Ajoutez une méthode ajouteUnité à la classe Case permettant d'ajouter une unité à la collection d'unités se trouvant sur la case.

2,5 points

Le plateau de jeu (classe Plateau) représente l'ensemble du jeu. Cette classe possède trois champs :

Des champs lignes et colonnes de type entier donnant la taille de la carte,
Un champs grille représentant la grille. Techniquement, ce champs est un tableau à deux dimensions : ce champs référence un tableau de lignes éléments, où chaque élément est lui-même une référence vers un tableau de colonnes références vers des cases.

La classe Plateau doit aussi posséder un constructeur permettant d'allouer et d'initialiser l'ensemble de la grille. Donnez le code complet de la classe Plateau, en sachant que le constructeur de Plateau doit affecter une référence vers un nouvelle instance de la classe Case à chaque case de la grille.

Les unités (5 points)

Maintenant que nous avons conçu les cases, nous pouvons nous intéresser à la conception des unités. Il existe deux catégories d'unités : les unités combattantes qui permettent d'envahir les villes et les unités d'exploration qui permettent de fonder de nouvelles villes ou d'établir des routes commerciales pour booster la productivité des villes. Ces deux catégories d'unités n'ont pas les mêmes contraintes de déplacements : une case peut héberger au plus une unité de combat mais peut héberger plusieurs unités d'exploration pourvu qu'elles appartiennent au même joueur. Comme les contraintes de déplacement ne sont pas les mêmes pour toutes les catégories d'unités, on vous propose l'arbre d'héritage suivant (dans lequel quelques unités sont représentées pour illustrer) :

           Unité
          /    \
         /      \
 Combattant    Explorateur
     /  \        /      \
    /    \    Caravane  Colon
   /      \
Archer  Infanterie

On commence par concevoir la classe Unité. Cette classe possède un champ de type Joueur indiquant à quel joueur appartient l'unité et une champ Image permettant d'afficher l'unité. On suppose les classes Joueur et Image fournies, et en particulier, on suppose que la classe Image offre une méthode void affiche(int x, int y) permettant d'afficher l'image de l'unité en (x, y).

Outre les champs, la classe Unité possède aussi trois méthodes :

un constructeur permettant d'initialiser les champs Joueur et Image de la classe,
une méthode void affiche(int x, int y) permettant d'afficher l'image en (x, y),
une méthode boolean peutEntrer(Case case) permettant de savoir si l'unité peut entrer dans la case case.

0,5 points

Parmi les méthodes de Unité, lesquelles est-il souhaitable de laisser abstraites et pourquoi ? (répondez succinctement en quelques lignes maximum).

2 points

Donnez le code complet de la classe Unité.

2,5 points

À cette question, on vous demande de concevoir la classe Combattant modélisant n'importe quelle unité combattante. Pour concevoir cette classe, il faut savoir que :

le constructeur de la classe Combattant prend en argument un joueur et une image,
une unité combattante ne peut entrer dans une case que si cette dernière ne contient aucune autre unité combattante.

Donnez le code complet de la classe Combattant.

On vous rappelle que x instanceof C renvoie vrai si x référence un objet qui hérite de la classe C. On vous rappelle aussi qu'on suppose que tous les champs de toutes les classes sont publics.

Génération de la carte – les continents (7 points)

On s'intéresse maintenant à la génération d'une carte aléatoire. Dans la suite, on suppose qu'on dispose d'une classe Terrain. On suppose aussi que la classe Plateau (celle que vous avez conçue au premier exercice) possède 5 nouveaux champs nommés plaine, foret, colline, montagne et mer. Chacun de ses champs est de type Terrain, et on suppose que ces champs sont correctement initialisés par le constructeur de Plateau.

1 point

Commencez par écrire une méthode void init() dans la classe Plateau permettant d'initialiser chaque case au terrain mer.

Dans la suite de l'exercice, l'inversion des rôles de colonnes et de lignes ne sera pas sanctionné.

5 points

On souhaite maintenant fabriquer des continents. Initialement, un continent est constitué d'un unique type de terrain. Pour générer les continents, on utilise un algorithme de marche aléatoire. Le principe de l'algorithme est le suivant. On choisit aléatoirement un point de départ sur la grille et on se déplace aléatoirement à gauche, à droite, en bas ou en haut jusqu'à avoir rempli suffisamment de cases avec des terrains. Pour obtenir des nombres aléatoires, on suppose que la classe Plateau offre une méthode int rand(int max) permettant de tirer un nombre aléatoire entre 0 et max-1.

Donnez le code de la méthode void construitContinent(Terrain terrain, int n) de la classe Plateau permettant de construire un continent constitué de n terrain terrain. Cette méthode doit commencer par sélectionner une position de départ sur la grille. Cette position doit se trouver dans la mer. Donc, si par hasard, la position tirée se trouve déjà dans un continent, il faut tirer une nouvelle position de départ.

Ensuite, l'algorithme fonctionne de façon itérative :

si la case à la position courante se trouve dans la mer, il faut passer le terrain de la case courante à terrain et décrementer n,
dans ce cas, si n tombe à 0, il faut sortir de la méthode puisque le continent est entièrement construit,
dans tous les cas (que la position soit dans la mer ou non), il faut ensuite tirer un nombre aléatoire compris entre 0 et 3 inclus. Ce nombre donne une direction (par exemple, 0=bas, 1=gauche, 2=haut, 3=droite) et il faut donc déplacer la position courante de façon adéquate (si, par hasard, vous êtes sur un bord et que le déplacement est invalide, ne déplacez bien sûr pas la position courante),
enfin, il faut recommencer au début de la boucle.

On ne vous demande pas de traiter de façon spéciale le cas où un déplacement ferait se rejoindre deux continents. Dans ce cas, on obtiendra simplement un plus gros continent.

1 point

Si la taille du continent est plus grande que la taille de la grille, l'algorithme que nous utilisons ne pourra pas terminer. Il faut donc modifier le code de construitContinent pour lever une exception de type ContinentTropGrand lorsque n est trop grand. Donnez le code de ContinentTropGrand et le code qu'il faut ajouter au début de construitContinent pour lever l'exception quand n est trop grand. Donnez aussi la nouvelle signature (déclaration) de construitContinent.

À cette question, on ne vous demande que de traiter le cas initial où la grille est uniquement constituée de mer.

Génération de la carte – l'ensemble des terrains (3 points)

Maintenant que nous pouvons générer nos continents, nous souhaiterions les décorer un peu avec des montagnes, des collines et des forêts. On peut facilement se rendre compte que de décorer un continent revient pratiquement à générer un sous-continent d'un autre type dans un continent pré-existant&nbsp: quelques petits continents de forêts, de montagne ou de collines dans un continent constitué de plaines. Toutefois, dans ce cas, les contraintes de placement sont différentes : initialement, la position doit se trouver dans un autre continent et la marche aléatoire ne doit pas faire sortir du continent.

Plutôt que de réécrire un méthode construitContinent pour chaque type de terrain, on va modifier notre méthode actuelle et utiliser des interfaces pour spécifier les contraintes.

0,5 point

Écrivez une interface Contrainte définissant deux méthodes prenant en argument un plateau et des coordonnées, et renvoyant un booléen. Ces deux méthodes, appelées boolean initOk(Plateau plateau, int x, int y) et boolean deplOk(Plateau plateau, int x, int y) permettent respectivement de savoir si le choix de la position initiale ou d'un déplacement est possible pour un type de terrain donné.

1 point

Donnez le code de la classe ContrainteAutre mettant en œuvre Contrainte. Cette mise en œuvre s'occupe de s'assurer que les contraintes de placement des autres terrains (ni mer, ni plaine) sont bien respectées. Techniquement, votre mise en œuvre doit donc s'assurer que la position initiale se trouve bien dans un continent et que le déplacement ne fait pas sortir du continent.

1,5 points

Indiquez les modifications que vous apportez à la méthode construitContinent pour assurer que le placement respecte les contraintes données par une mise en œuvre de la classe Contrainte donnée en argument à construitContinent.

À cette question, on vous demande de donner du code Java. Plutôt que de réécrire entièrement la méthode construitContinent, vous pouvez utiliser un système de numéros ou de lettres pour indiquer les zones de codes de la question 3.b que vous remplacez.

Pensez aussi à donner la nouvelle signature de construitContinent (la nouvelle déclaration de la méthode).

2 points (bonus - difficile)

Les montagnes ne permettent pas au joueur de passer. Quand on place les montagnes, il faut donc s'assurer que le joueur peut toujours atteindre toutes les cases du continent (montagnes mises à part). Donnez une mise en œuvre de MontagneContrainte respectant cette contrainte.

Vous pouvez supposer qu'une instance de MontagneContrainte possède deux champs : le nombre total de cases du continent et le nombre de montagnes déjà placées sur le continent.

Civ.java