Available nodes

 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 :
(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'objectif de ce projet consiste à produire un ensemble d'outils permettant de construire un jeu de type Tower Defense appartenant au genre susnommé, de programmer des types d'interactions variés entre les éléments du jeu, et de visualiser l'évolution d'une partie.
  • 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é this dans 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 :

world  = initializeWorld()
actors = initializeActors(world)
phases = computePhases(world, actors)
while the game is not over
      [world, actors] = phases.reduce(([aWorld, actors], aPhase) => {
            funcName  = aPhase.funcName
            proposals = actors.map((anActor) =>
                              anActor.funcName(anActor, aWorld));
            [aNewWorld, newActors] = resolveProposals(aWorld, actors, proposals);
            return [aNewWorld, newActors];
        },
        [world, actors]);

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 move le faisant se déplacer systématiquement d'un pas vers la droite :

const anActor = {
    pos:     { x: 5, y: 7 },
    actions: {
         move: (anActor, aWorld) => { dx: 1, dy: 0 },
    },
};
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 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ée move. 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'un block empêche un move, 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 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)
Le fichier 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 build doit compiler les fichiers les fichiers du répertoire src dans le répertoire dist;
  • make run doit exécuter une partie avec un affichage sur la console;
  • make test doit exécuter les tests;
  • (optionnel, recommandé) make eslint doit exécuter la commande eslint sur les fichiers de code (cf. partie sur ESLint) pour en vérifier la syntaxe;
  • (optionnel) make parcel doit lancer la commande parcel (cf. partie sur Parcel) de manière à pouvoir lancer un serveur HTTP servant un exemple du code.
Des fichiers de configuration sont fournis pour les différents outils, et il est demandé de ne pas les modifier :
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 : 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 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. Principalement, la commande à retenir pour utiliser 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.
Principalement, la commande à retenir pour utiliser Jest est la suivante : L'exemple simple de test en Jest est le suivant :
npx jest tst/*.ts
const sum = require('../src/sum');

test('adds 1 + 2 to equal 3', () => {
  expect(sum(1, 2)).toBe(3);
});

 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 ? ;)