CI3 : L'armée de monstres
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 :
- Exercice 1 : obligatoire (facile, ∼40mn)
- Exercice 2 : obligatoire (moyen, ∼1h)
- Exercice 3 : obligatoire (facile, ∼15mn)
- Exercice 4 : entraînement (difficile, ∼45mn)
- Dans une première partie, nous concevons la structure de données qui représente un monstre.
- Dans une seconde partie, nous utilisons des tableaux extensibles pour stocker nos monstres. Un tableau extensible est une structure de données reposant sur un tableau, mais permettant de réallouer dynamiquement le tableau de façon à l'étendre. Dans cette partie, ainsi que dans la précédente, nous concevons notre application de façon non modulaire, c'est-à-dire que nous mettons en vrac l'ensemble des méthodes de notre programme dans la même classe.
- Dans une troisième partie, nous constatons que cette conception non modulaire ne permet pas de réutiliser le code. Pour cette raison, nous modifions le design de notre application.
- Dans une quatrième partie, nous observons qu'un tableau extensible n'est pas la structure de données la plus efficace en terme de performance si le nombre de monstres devient grand. Pour cette raison, nous modifions notre application de façon à utiliser des listes chaînées pour stocker nos monstres.
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.
Les monstres (∼45mn – facile – obligatoire)
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.
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 !
Le tableau extensible (∼60mn – moyen – obligatoire)
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.
Conception modulaire (∼15mn – facile – obligatoire – exercice très important !)
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.
Félicitations, vous venez de mettre en œuvre votre première application modulaire !
La liste chaînée (∼45mn – difficile – entraînement)
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ûr 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 correct 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 cet 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 exécuter cur = cur.next.
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.
bonus
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.
