Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Sous prétexte de mettre en œuvre une fonctionnalité d'un petit jeu, cet exercice a trois buts distincts. Le premier but est d'apprendre à manipuler des structures de données. Le second but est de concevoir des tableaux extensibles et des listes chaînées. Ces structures de données classiques permettent de gérer des ensembles homogènes non bornés. Le troisième but est de vous amener pas à pas vers une conception modulaire, qui nous servira à introduire la programmation orientée objet dans les prochains cours.

Durée des exercices obligatoires : 2h en présentiel

Dans notre petit jeu, légèrement influencé par un triple A de 2016, des joueurs se promènent dans le monde réel avec leur téléphone portable pour capturer des monstres virtuels géo-localisés. Ces monstres servent ensuite aux joueurs à conquérir des lieux spéciaux, ce qui permet aux joueurs d'interagir.

Le but de l'exercice n'est pas de mettre entièrement le jeu en œuvre mais uniquement la partie du jeu qui gère les armées de monstres. Cette mise en œuvre est rendue difficile car les scénaristes fantaisistes du jeu ont prévu que chaque joueur puisse acquérir un nombre non borné de monstres. Pour cette raison, utiliser un tableau de taille fixe pour stocker les monstres est impossible. Nous allons donc étudier des structures de données permettant de gérer un nombre non borné d'éléments.

L'exercice est séparé en quatre parties :

Pour les étudiants qui ont déjà l'habitude de la programmation, certains choix de conception proposés dans cet exercice pourront vous paraître inadéquats. Ces choix sont effectivement inadéquats, mais visent à montrer aux étudiants qui n'ont pas encore l'habitude de programmer qu'il faut concevoir une application de façon modulaire. Pour commencer, créez un projet nommé monsters contenant une unique classe nommée Main avec une méthode main. Créez une nouvelle classe nommée Monster et contenant les champs suivant :
  • name : une chaîne de caractères donnant le nom du monstre.
  • health : un entier donnant le nombre de points de vie du monstre. Lorsque ce nombre tombe à zéro, le monstre meurt.
Vous pourriez bien sûr imaginer ajouter d'autres champs à cette classe, comme, par exemple, une image représentant le monstre, mais nous nous contenterons dans cet exercice d'une version minimaliste de nos monstres.
Dans la méthode main, allouez un premier monstre que vous stockerez dans une variable nommée aMonster. Affectez le nom du monstre à "Pikachu", son nombre de points de vie à 0, puis affichez le nom du monstre sur le terminal. Vérifiez que votre programme affiche bien "Pikachu". Dans la classe Main, écrivez une méthode de classe createMonster prenant en argument un nom et un nombre de points de vie. Cette méthode doit renvoyer une référence vers une nouvelle instance de Monster initialisée de façon adéquate. Supprimez le code qui alloue et initialise un monstre dans la méthode main. Remplacez ce code par un appel à createMonster pour créer le monstre "Pikachu". Vérifiez que votre programme affiche toujours "Pikachu". Dans la classe Main, écrivez une méthode displayMonster prenant en paramètre un monstre. Cette méthode doit afficher Monster<name>, où name est le nom du monstre passé en paramètre. Au lieu de directement afficher le champ name du monstre dans la méthode main, utilisez displayMonster pour afficher votre monstre. Vérifiez que Monster<Pikachu> est bien affiché sur le terminal. Avant de mettre en œuvre la structure de données stockant une armée de monstres, nous allons créer plusieurs monstres. Remplacez la création et l'affichage de Pikachu par une boucle créant et affichant 8 monstres dont les noms vont de Pikachu0 à Pikachu7. Vérifiez que votre programme affiche bien vos 8 Pikachus dans la console et que leur noms sont corrects.

Conservez bien le code qui crée les 8 Pikachus jusqu'à la fin de l'exercice car vous en aurez besoin dans les questions suivantes.
Félicitations, vous venez de créer vos premiers objets !
Dans cette partie nous utilisons des tableaux extensibles pour stocker nos monstres. Dans un premier temps, avant de nous occuper de rendre nos tableaux extensibles, nous commençons par utiliser des tableaux à taille fixe.

Le principe, à cette étape, est d'allouer un tableau suffisamment grand pour accueillir nos 8 monstres, et d'utiliser un indice indiquant le niveau de remplissage du tableau. Initialement cet indice d'insertion vaut 0. L'ajout du premier monstre se fait donc à cet indice dans le tableau, et l'indice d'insertion est augmenté de 1. De façon similaire, si l'indice d'insertion vaut N, l'ajout d'un nouveau monstre se fait dans la case d'indice N du tableau et l'indice d'insertion est ensuite augmenté de 1.

Au début de l'exercice, nous considérons que le tableau a toujours une taille suffisante pour accueillir un nouveau monstre, et nous ne nous préoccuperons de gérer le problème du débordement du tableau qu'à la fin de l'exercice. Créez une classe nommée Army contenant deux champs : un tableau de monstres nommé monsters et un entier nommé top indiquant jusqu'à quel indice le tableau est occupé. Écrivez aussi une méthode Army createArmy() dans la classe Main. Cette méthode doit (i) créer une instance de la classe Army, (ii) allouer un tableau de taille 100 et l'affecter au champ monsters de l'instance nouvellement créée, (iii) fixer la valeur initiale du champ top de l'instance à 0 puisque l'armée est initialement vide, et (iv) renvoyer l'instance de la classe Army. Écrivez, dans la classe Main, une méthode nommée addMonster prenant en argument une armée et un monstre, et permettant d'ajouter le monstre à l'armée. Dans cette version préliminaire de addMonster, nous considérons que le tableau monsters est suffisamment grand pour accueillir un nouveau monstre. Pour tester addMonster, modifiez la boucle de la méthode main qui crée les 8 Pikachus de façon à les ajouter à une armée au lieu de les afficher. Écrivez, dans la classe Main, une méthode nommée void displayArmy(Army army). Cette méthode doit utiliser displayMonster pour afficher les monstres actuellement enregistrés dans l'armée. Vérifiez que votre programme est correct en appelant displayArmy à la fin de la méthode main. Cet appel devrait afficher les 8 Pikachus qui se trouvent dans l'armée. Techniquement, displayArmy doit afficher les monstres se trouvant aux indices allant de 0 (inclus) à top (non inclus) du tableau monsters. Nous pouvons maintenant rendre notre tableau de monstres extensible. Dans createArmy, au lieu de créer un tableau à 100 entrées lorsque vous créez une armée, créez un tableau à 4 entrées. Lancez votre programme, que constatez-vous ? Affichage d'un ArrayIndexOutOfBoundsException. Cet affichage indique qu'une erreur s'est produite. Vous apprendrez dans la suite du module que cette erreur s'appelle une exception. Pour le moment, il vous suffit de savoir que vous pouvez cliquer sur le message pour trouver l'endroit dans le code qui a généré l'erreur. Modifiez votre méthode addMonster de façon à traiter le cas où top est plus grand ou égal que le taille du tableau de monstres. Dans ce cas, vous devez allouer un tableau plus grand avant de recopier l'ancien contenu. En détail, vous devez :
  • Allouer un nouveau tableau nommé tmp. Ce tableau doit avoir une taille plus grande que le tableau de monstres original (par exemple, en doublant la taille du tableau original).
  • Recopier le tableau original de monstres dans le tableau tmp.
  • Affecter tmp au champ monsters de l'armée.

Pour les étudiants curieux, vous pouvez remarquer que vous n'avez jamais libéré la mémoire occupée par l'ancien tableau de monstres. En Java, le développeur n'a pas à se soucier de libérer la mémoire car l'environnement d'exécution s'en occupe pour le développeur. Pour votre culture, le mécanisme qui libère la mémoire s'appelle un ramasse-miette (garbage collector en anglais). Ce mécanisme de libération automatique de la mémoire est présent dans la plupart des langages modernes (Java, C#, Javascript, Python, Bash...), ce qui est une des raisons qui explique le succès de ces langages.
Face au succès phénoménal de votre jeu, votre PDG, toujours aussi visionnaire, souhaite lancer une nouvelle franchise basée sur le film Black Sheep relatant les passionnantes aventures de moutons zombies. Dans ce nouveau jeu, un joueur se promène dans le monde réel et rencontre des moutons zombies géo-localisés qui se mettent à l'attaquer. Le joueur doit collectionner des pieux en argent pour vaincre les moutons zombies, ce qui lui rapporte des pièces lui permettant d'acheter des vêtements de luxe, le but du jeu étant d'avoir le personnage le plus chic du monde. Souhaitant limiter le temps de développement, votre géniale PDG vous suggère de réutiliser la structure de données représentant les monstres du précédent jeu de façon à modéliser un mouton zombie. Pour quelle raison le design non-modulaire que nous avons choisi se prête mal à cette opération ? Car le code qui manipule les instances de Monster est placé de façon aléatoire en vrac dans d'autres classes (ici Main). Au résultat, il est difficile d'extraire ce code pour le réutiliser. Comme vous l'avez probablement compris, le design que nous avons utilisé limite la réutilisabilité du code. Ce manque de réutilisabilité oblige à re-développer inutilement du code, ce qui a un coût financier non négligeable. Pour cette raison, avant de passer à la suite, nous redesignons pas à pas notre application de façon à pouvoir en extraire facilement des parties pour d'autres projets.

Le problème fondamental du design que nous avons utilisé est que les méthodes qui manipulent les monstres ou l'armée sont difficiles à identifier puisque ces dernières sont mises en vrac dans la classe Main. Pour cette raison, nous allons redesigner notre application de façon modulaire : nous allons mettre les méthodes qui manipulent les monstres dans la classe Monster et les méthodes qui manipulent l'armée dans la classe Army.

Dans la suite de l'exercice, nous vous guidons en supposant que vous utilisez Eclipse. Si vous utilisez un autre logiciel de développement, vous devrez adapter l'énoncé à votre environnement de développement qui, s'il est moderne et bien fait, devrait vous offrir sensiblement les mêmes fonctionnalités.

Déplacer les méthodes createMonster et displayMonster dans la classe Monster. Sous Eclipse, vous pouvez cliquer avec le bouton de droite de la souris sur la méthode, aller dans le sous-menu Refactor et sélectionner Move. De la même façon, déplacez createArmy, addMonster et displayArmy dans la classe Army. Relisez le code de votre main : vous devriez constater que maintenant, par exemple, vous appelez Army.createArmy pour créer une armée puisque la méthode createArmy se trouve dans la classe Army.
Maintenant que nos méthodes sont rangées à leur place, nous pouvons les renommer : il est inutile que la méthode de création de monstre de la classe Monster s'appelle createMonster, puisque le suffixe Monster devient maintenant implicite. Dans la classe Monster, renommez donc la méthode createMonster en create et la méthode displayMonster en display. Lorsque vous souhaitez renommer une méthode avec Eclipse, il vous suffit de cliquer à droite sur le nom de la méthode, d'aller dans le sous-menu Refactor et de sélectionner Rename. De façon similaire, dans la classe Army, renommez la méthode createArmy en create et la méthode displayArmy en display.

Le design de votre application est maintenant correct. Vous pouvez facilement réutiliser la classe Monster pour concevoir un jeu de moutons zombies, ce qui minimise l'effort de développement et donc le coût financier. De façon générale, en Java, vous constaterez au fur et à mesure que vous développerez qu'il est beaucoup plus judicieux de mettre les méthodes qui manipulent une structure de données dans la classe qui définit cette structure de données. Félicitations, vous venez de mettre en œuvre votre première application modulaire !

Avant de commencer, de façon à conserver le code que vous avez écrit jusqu'à présent, nous vous conseillons de dupliquer votre projet monster. Pour cela, il vous suffit de commencer par sélectionner le projet monster et de cliquer avec le bouton de droite de la souris avant de sélectionner Copy. Ensuite, dans le package explorer, il vous suffit de cliquer avec le bouton de droite de la souris avant de sélectionner Paste. À ce moment, Eclipse va vous demander d'entrer un nouveau nom de projet. Vous pouvez par exemple utiliser monster-array.

Suite à l'extraordinaire succès de votre jeu, vous vous mettez à recevoir des centaines de milliers de mails d'utilisateurs mécontents car les performances de votre jeu sont désastreuses. Après une analyse de performance poussée, vous vous apercevez que des joueurs mono-maniaques collectionnent des centaines de milliers de monstres. Lorsque le tableau extensible est étendu pour accueillir les nouveaux monstres de ces joueurs, des centaines de milliers de cases sont copiées de l'ancien tableau vers le nouveau, ce qui écroule les performances de vos serveurs et impacte l'ensemble des joueurs connectés au même serveur (cette anecdote est bien sûre imaginaire, mais ressemble aux problèmes de performances que vous pouvez rencontrer tous les jours dans une entreprise).

De façon à éviter ces recopies de tableaux, nous mettons en œuvre l'armée de monstres avec des listes chaînées. Une liste chaînée est une structure de données classique évitant cette recopie au prix d'un temps de parcours des éléments plus long. Le principe est de construire une chaîne d'éléments homogènes, chacun référençant le suivant de la liste. Pour cela, nous introduisons une nouvelle classe nommée Node permettant de référencer (i) une instance de Monster et (ii) l'instance de Node suivante dans la liste.

La figure ci-après présente la structure sous une forme graphique. Chaque boite représente une instance d'une classe. Le nom en haut de la boite donne le nom de la classe instanciée et les noms en dessous sont les champs les plus importants de l'instance. Les flèches quant à elles représentent les références. Dans cette illustration, l'armée (l'instance de Army) référence le premier nœud de la liste chaînée. Le premier nœud référence un premier monstre (Pikachu) et le deuxième nœud. Le deuxième nœud référence le deuxième monstre (Tortank) et le nœud suivant de la liste, jusqu'à la fin de la liste qui est indiqué par la référence null. Commencez par écrire une classe nommée Node contenant deux champs : un champ monster référençant le monstre associé au nœud et un champ next référençant le nœud suivant de la liste. Ajoutez à cette classe une méthode nommée create prenant en argument un monstre et un nœud suivant, et renvoyant un nouveau nœud initialisé de façon adéquate. Dans la classe Army, ajoutez un champ first de type Node. Dans la méthode create de Army, initialisez first avec la valeur null, ce qui indique à Java que cette référence ne pointe nul part.

Ne supprimez pas encore les anciens champs qui stockent les monstres sous la forme d'un tableau extensible de façon à conserver un code correcte tout au long de l'exercice.
Dans la méthode addMonster de la classe Army, sans supprimer le code qui s'y trouve déjà, modifiez la liste de façon à ajouter le monstre passé en paramètre au début de la liste (à gauche sur la figure ci-dessus). Techniquement, il vous suffit d'appeler la méthode create de Node de façon adéquate et d'affecter le résultat de cette appel au champ first de l'armée. Il faut initialiser le nouveau nœud avec comme argument (i) l'ancienne valeur de first et (ii) le nouveau monstre. Dans la méthode display de la classe Army, en plus d'afficher les monstres se trouvant dans le tableau extensible, affichez le contenu de la liste chaînée. Vérifiez que votre programme affiche maintenant bien deux fois votre armée.

Vous devriez remarquer que, lors du parcours de la liste chaînée, les monstres sont affichés dans l'ordre inverse de celui de leur insertion. Ce phénomène est tout à fait normal puisque vous ajoutez les nouveaux nœuds au début de la liste et que vous affichez votre liste en commençant par le début.

Pour afficher votre liste, il vous suffit d'utiliser une variable locale de type Node nommée cur. Ensuite, vous pouvez utiliser une boucle qui s'arrête lorsque cur vaut null et qui, à chaque pas de la boucle, avance d'un cran dans la liste. Techniquement, à chaque pas de la boucle, il faut affecter cur.next à cur.
Vous pouvez maintenant nettoyer le code et supprimer le tableau extensible qui est devenu inutile. Pour cela, commencez par supprimer les champs monsters et top de la classe Army, et corrigez toutes les erreurs que vous indique votre environnement de développement. Pour les étudiants aventuriers, nous vous proposons d'écrire une méthode delMonster dans la classe Army permettant de supprimer un monstre de l'armée. Cette méthode doit prendre en paramètre une référence vers une armée et une référence vers un monstre. Votre méthode doit traiter trois cas distincts :
  • Si le premier nœud de la liste (first) vaut null, il n'y a rien à faire.
  • Si le premier nœud de la liste référence un nœud qui référence le monstre passé en paramètre (l'opérateur == permet de savoir si deux références sont identiques), alors il faut affecter first à first.next.
  • Sinon, votre méthode doit parcourir la liste de façon à identifier le prédécesseur du nœud qui référence le monstre passé en paramètre. Une fois identifié, si le prédécesseur est stocké dans une variable locale nommée pred, votre méthode doit affecter pred.next.next à pred.next de façon à sauter le nœud que vous souhaitez supprimer.