Tower Defense
Le Tower
Defense est un genre de jeux vidéos dans lequel le joueur
défend un terrain attaqué de manière répétée par des adversaires
décidés à submerger ses défenses. Les adversaires suivent
usuellement un ou plusieurs chemins menant à un emplacement sur
le terrain (considéré comme plus ou moins vulnérable) servant
d'objectif, et sont ralentis par des tours, agissant sur les
adversaires par différents moyens (élimination, bloquage,
ralentissement ...). Sur l'image suivante (tirée du
jeu Kingdom
Rush), on distingue bien une route amenant à l'objectif
situé en bas, route empruntée par de sympathiques arachnides1 ralenties sur leur trajet par des bâtiments et des personnes
leur bloquant le passage 23 :
Les jeux de Tower Defense sont connus pour laisser beaucoup de latitude pour ce qui est des types de personnages, des mouvements possibles, et des moyens pour affecter lesdits mouvements. Il est ainsi envisageable de laisser des personnages sur le terrain pour bloquer le passage (ce qui peut être rendu impossible si les personnages volent), de lancer des sorts (par exemple ralentissant ou accélérant les personnages), et naturellement d'utiliser des moyens très variés pour atteindre sa cible. Il est aussi classique de pouvoir améliorer les caractéristiques des différents protagonistes (rythme et intensité des tirs, zone d'action, résistance et points de vie …). Du point de vue de la programmation, il s'agit d'une occasion de :
|
| (image tirée du jeu Kingdom Rush © Ironhide Games Studio / Armor Games) |
Les jeux de Tower Defense sont connus pour laisser beaucoup de latitude pour ce qui est des types de personnages, des mouvements possibles, et des moyens pour affecter lesdits mouvements. Il est ainsi envisageable de laisser des personnages sur le terrain pour bloquer le passage (ce qui peut être rendu impossible si les personnages volent), de lancer des sorts (par exemple ralentissant ou accélérant les personnages), et naturellement d'utiliser des moyens très variés pour atteindre sa cible. Il est aussi classique de pouvoir améliorer les caractéristiques des différents protagonistes (rythme et intensité des tirs, zone d'action, résistance et points de vie …). Du point de vue de la programmation, il s'agit d'une occasion de :
- gérer des systèmes multi-agents dans lesquels un ensemble de protagonistes interagissent de manière synchronisée;
- concevoir des moyens créer de nombreux types de protagonistes ayant chacun sa propre manière d'interagir avec les autres.
- L'idée de ce sujet est de promouvoir
la programmation fonctionnelle
(pureté et première
classe). L'écriture de classes ou l'utilisation du
mot-clé
thisdans le code n'y sont pas nécessaires et sont donc proscrits. Toute forme de programmation pure est encouragée. - Bien que le sujet encourage à produire une visualisation à travers une page HTML, il est fortement recommandé de commencer par produire une visualisation en mode texte sur la console (que ce soit pour démarrer, pour tester, ou autre ...). La programmation d'interaction avec l'utilisateur au cours de la partie n'est pas formellement interdite, mais sera considérée comme hors-sujet4.
- L'auteur du sujet offrira une bonification (sous une forme non spécifiée) à toute modélisation non-violente de ce genre de jeu.
Acteurs et phases de jeu
Le monde de jeu est une grille 2D de
dimensions libres. Un acteur est une
entité disposant d'un ensemble de caractéristiques, dont une
position dans le monde. Le jeu se déroule en une série
de tours pendant lesquels chaque acteur
est appelé pour proposer des modifications de ses
caractéristiques, ou de celles des acteurs voisins. Un acteur
est supposé être un objet constant. Les propositions de
modifications sont gérées et validées par une entité centrale
appelée par la suite le moteur de jeu, qui
s'occupe de vérifier que les modifications sont cohérentes.
Un tour se décompose en un ensemble fini
de phases de jeu, réalisée par l'ensemble
des acteurs. Un exemple est la phase de déplacement
(move) pendant laquelle chaque acteur peut choisir ou pas
de modifier sa propre position. Il n'est pas requis pour un
acteur de participer à une phase de jeu particulière, auquel cas
il aura un comportement par défaut (par ex., pour la phase de
déplacement, il ne se déplacera pas). Les modifications peuvent
être contradictoires (par ex. si deux acteurs veulent se
déplacer au même endroit) et devront donc être gérées par le
moteur. Une phase se termine lorsque toutes les modifications
ont été réalisées, et les conflits résolus. La boucle de jeu
globale se présente de la manière suivante :
Les acteurs sont censés être
relativement autonomes (ils contiennent le
code pour prendre leurs propres décisions) et interagir de
manière locale (ils n'interagissent qu'à
une distance finie avec le monde). De plus, ils peuvent avoir
des comportements très variés. Pour cela,
on propose de représenter les actions des acteurs pendant les
différentes phases de jeu comme des fonctions aux paramètres
bien choisis. Dans l'exemple suivant, pour se déplacer, l'acteur
dispose d'une fonction
Pour une phase de jeu donnée, toutes les fonctions sont censées
avoir le même prototype (en particulier
concernant la valeur renvoyée). Cela permettra au moteur de jeu
de les appeler uniformément. Dans l'exemple ci-dessus, la
fonction
|
move le faisant se déplacer
systématiquement d'un pas vers la droite :
|
move prend deux paramètres : l'acteur à
déplacer et le monde dans lequel celui-ci vit. Il est ainsi
envisageable d'avoir des fonctions de déplacement très
raffinées, par exemple en utilisant un
algorithme A*.
Noter que selon cette façon de faire, l'acteur n'est jamais
censé modifier lui-même ses caractéristiques propres (il est
constant). Chaque fonction ne fait que calculer une
intention. Le moteur de jeu récupère l'ensemble des intentions,
et les résout en appliquant ses propres règles.
La représentation précédente permet d'envisager de nombreuses
techniques fonctionnelles pour engendrer des
interactions. Ainsi, il est possible d'utiliser
un décorateur fonctionnel5 pour créer une
fonction de mouvement qui ne serait appelée qu'une fois tous les
deux tours, induisant ainsi un ralentissement de l'acteur
concerné. Il est aussi envisageable de fusionner les actions des
acteurs (pour par ex. construire un acteur se déplaçant soit
comme un liève, soit comme une tortue). Enfin, les décorateurs
peuvent avoir une durée d'application finie, et réinstaurer le
comportement précédent après cette durée.
Description du projet
Le projet se propose de réaliser à la fois une bibliothèque
permettant de créer des mondes et des acteurs et d'exécuter un
ensemble fini de tours de jeu les faisant interagir. Une
décomposition des tâches possibles est discutée ici.
- Concevoir des mondes de
jeu.
Il s'agira d'un environnement capable de contenir des acteurs, mais aussi des cases aux caractéristiques variées (chemin, paysage, rivière …). Il devra être possible de déplacer les acteurs et de calculer la liste des acteurs autour d'un point donné. Les éléments de décor peuvent être considérés comme des acteurs sans interaction. Dans un second temps, il devra être possible de calculer des chemins pour se déplacer entre les points du monde. Enfin, il devra exister un algorithme de génération procédurale permettant de construire un chemin partant d'une source et se dirigeant vers l'objectif. - Concevoir des
acteurs.
Chaque acteur doit être vu comme une entité capable de stocker ses caractéristiques et ses comportements sur chacune des phases de jeu. Le premier exemple de caractéristique est la position de l'acteur dans le monde. Le premier exemple de comportement est une fonction calculant un déplacement. - Proposer de nouvelles
phases de jeu.
Il est demandé à ce qu'il existe au moins une phase de jeu appeléemove. Le reste des phases de jeu est laissé à l'imagination des programmeurs :block,target,fight,spawn,heal,trade… Il est conseillé de se mettre d'accord sur l'ordre des phases de jeu (par ex., il est envisageable qu'unblockempêche unmove, auquel cas il doit être calculé avant). - Écrire le moteur de
jeu.
Le moteur de jeu doit orchestrer le monde et les acteurs, accumuler les intentions des acteurs à chaque phase et les résoudre. Il peut se permettre de faire disparaître des acteurs ou d'en créer. Il doit être conçu de manière modulaire, de faon à faciliter l'ajout et le retrait de nouvelles phases. - Engendrer des acteurs aux
comportements variés.
Il s'agira de fournir une famille de fonctions permettant de construire des acteurs ayant des comportements aussi variés que possible pour chacune des phases de jeu. Lesdits acteurs seront construits en composant ces fonctions. De plus, les comportements des acteurs pourront évoluer au fur et à mesure de la partie.
Détails techniques
Dans ce projet, le code doit être écrit entièrement
en TypeScript. Pour rappel, un fichier
Javascript standard est acceptable comme fichier TypeScript. Les
types sont complètement dispensables, néanmoins le code doit
pouvoir être compilé sans erreurs avec
Le fichier
Ces fichiers sont utilisés en particulier sur la forge pour
compiler, vérifier la syntaxe et tester le code.
Les paquetages Node.js nécessaires au fonctionnement du code
doivent se restreindre à la liste suivante :
tsc.
Les fichiers devront être organisés de la manière suivante dans
le dépôt :
/ -- Base directory Makefile -- Global Makefile package.json -- npm configuration file /src -- Source files /tst -- Test files /html -- Web files (html, css) /dist -- Install directory (should be empty in the repository but for a .keep empty file) /node_modules -- npm directory (should be empty in the repository but for a .keep empty file)
package.json est présent pour permettre
d'installer les dépendances et toute autre opération
utilisant npm. Néanmoins, comme ce dernier traite
les dépendances de manière sous-optimale, le projet requiert la
présence d'un Makefile avec les règles
suivantes :
make builddoit compiler les fichiers les fichiers du répertoiresrcdans le répertoiredist;make rundoit exécuter une partie avec un affichage sur la console;make testdoit exécuter les tests;- (optionnel, recommandé)
make eslintdoit exécuter la commandeeslintsur les fichiers de code (cf. partie sur ESLint) pour en vérifier la syntaxe; - (optionnel)
make parceldoit lancer la commandeparcel(cf. partie sur Parcel) de manière à pouvoir lancer un serveur HTTP servant un exemple du code.
- un
fichier tsconfig.json
servant de configuration pour
tsc; - un
fichier .eslintrc.cjs
servant de configuration
pour
ESLint(cf. partie sur ESLint); - un fichier
jest.config.ts
servant de configuration pour
jest(cf. partie sur Jest).
commander,
jest,
ts-jest,
@types/node,
@types/jest,
typescript,
eslint,
parcel,
@typescript-eslint/parser, et
@typescript-eslint/eslint-plugin.
Le dépôt ne devra en aucun cas contenir
les modules
Le dépôt ne devra en aucun cas contenir de fichier de données gigantesques. Toute présence d'un fichier (ou d'un ensemble de fichiers) d'une taille déraisonnable dans le dépôt à un instant du développement verra attribuer un malus de
La page
Node.js utilisés dans le code. Toute
présence d'un quelconque répertoire node_modules
d'une taille strictement positive dans le dépôt à un instant
du développement verra attribuer un malus
de -2 à la note finale du projet, ce malus
étant cumulatif.
Le dépôt ne devra en aucun cas contenir de fichier de données gigantesques. Toute présence d'un fichier (ou d'un ensemble de fichiers) d'une taille déraisonnable dans le dépôt à un instant du développement verra attribuer un malus de
-2
à la note finale du projet, ce malus
étant cumulatif. Pour fixer les idées,
les tailles raisonnables sont de l'ordre de 100ko.
La page
dist/index.html ne
devra en aucun cas faire appel à une
quelconque ressource sur le réseau, et devra donc pouvoir
s'exécuter sans accès à Internet.
Utilisation de ESLint
ESLint est un analyseur statique de code, qui
permet de vérifier un certain nombre de règles syntaxiques. Il
peut être configuré pour vérifier du code TypeScript.
- Page principale
d'
eslint; - Tutoriel
pour l'utilisation de
ESLint - Liste des
règles disponibles dans
ESLint.
ESLint est la suivante :
npx eslint src tst
Utilisation de Jest
Jest est un framework de test en Javascript qui
peut lui aussi être configuré pour être utilisé avec TypeScript.
- Page principale
de
Jest; - Tutoriel
pour l'utilisation de
Jest; - Documentation des matchers;
Principalement, la commande à retenir pour
utiliser Jest est la suivante :
|
L'exemple simple de test en Jest est le
suivant :
|
npx jest tst/*.ts |
|
Utilisation de Parcel
Une partie du sujet propose de produire une
page :
dist/index.html présentant les capacités du
projet. Cette page peut faire appel à un ensemble d'autres
fichiers présents dans le répertoire public (styles
CSS, fichiers JS). La pratique courante consiste à utiliser un
logiciel pour préparer le code aussi
appelé bundler. Le bundler autorisé pour
ce projet se nomme Parcel-
Page principale
de
Parcel. - Tutoriel
pour l'utilisation de
Parcel(privilégiernpmàyarn). -
Options de
la CLI de
Parcel.
Parcel est la suivante :
npx parcel dist/index.html
Le choix des modules ESM
Les projets font le choix d'utiliser les modules ESM plutôt que
les modules CommonJS, parce qu'ils correspondent au
standard. Néanmoins, le support par node des modules ESM est
toujours marqué comme expérimental, et il existe beaucoup de
confusion sur les façons de faire cohabiter tous les outils
(
eslint, tsc&hellip) avec le bon
système de modules.
Le sujet impose d'écrire le code en Typescript, qui
sert de compilateur capable de produire à la fois du code
compatible ESM ou CommonJS. Il suffit pour cela de changer la
configuration target du
fichier tsconfig.json.
Recommandations
Pour l'ensemble du projet, il est recommandé de
systématiquement :
- Définir formellement les éléments nécessaires pour représenter le jeu, et les relier à leur implémentation.
- Définir formellement les algorithmes proposés, et étudier leur complexité (temps/mémoire).
- Caractériser dans les algorithmes et structures de données ce qui ressort de la programmation fonctionnelle et ce qui n'en est pas.
- Suivre les standards de codage développés dans le cours de programmation fonctionnelle et disponibles à l'adresse suivante.
Contact
Pour toute information complémentaire, contacter : David RENAULT.
| 1. | Certainement pour partir en vacances de neige. |
| 2. | Certainement leur expliquant que, les araignées étant poïkilothermes, cela n'a pas de sens pour elles de partir à la neige, et qu'elles feraient mieux de rentrer chez elles. Les barres vertes et rouges au dessus des arachnides indiquent à quel point elles ont été convaincues par cette argumentation. |
| 3. | Poïkilotherme, un adjectif à la sonorité amusante, signifiant simplement "à sang froid". Poil à l'homéotherme. |
| 4. | Sauf justification sérieuse de l'intérêt vis-à-vis de la programmation fonctionnelle. |
| 5. | Mais dans quel genre de document pourrait-on trouver de l'information à ce sujet ? ;) |