Available nodes

 Acteurs

Le modèle basé sur les acteurs (actor model en anglais) est un modèle de programmation concurrent construit sur l'idée d'un monde rempli d'acteurs échangeant des messages. Dans le cadre de ce projet, un message est une structure de données constitué d'une étiquette ainsi que d'un ensemble quelconque de paramètres (par ex. { key: "move", params: [1, 0] })). Un acteur est simplement une structure de données possédant un état propre, et capable de recevoir et d'émettre des messages. En fonction des messages qu'elle reçoit, elle peut choisir de mettre à jour son état, d'émettre de nouveaux messages, voire même de créer de nouveaux acteurs ou encore de mourir de sa belle mort. Exemple d'application très concret de ce style de programmation, le jeu Terminal Phase, codé en Racket par C. L. Webber, est basé sur un modèle d'acteurs et écrit avec un style fonctionnel :
(image tirée du jeu Terminal Phase de C. L. Webber, le lien contient un GIF animé)

L'objectif de ce projet consiste à mettre en place une bibliothèque d'acteurs en Typescript afin de permettre de construire un jeu ressemblant à un shoot'em up1. Pour simplifier par rapport au modèle de programmation cité ci-dessus, nous allons considérer que les acteurs se mettent à jour de manière synchronisée. Une horloge globale découpe le temps en intervalles (tick en anglais). Au début d'un intervalle de temps, les acteurs n'ont aucun message en attente. Ils reçoivent un ensemble de messages pendant cet intervalle (move, collide ...) sans autre modification. A la fin de l'intervalle de temps, ils vident leur boîte de message et se mettent à jour en fonction de ce qu'ils ont reçu. La mécanique de cette horloge globale peut être réalisée à l'aide d'une structure de données globale servant de runtime organisant la mise à jour simultanée de tous les acteurs. Les messages sont alors considérés comme reçus séquentiellement pendant cette mise à jour.

 Description du projet

L'idée générale du sujet est de créer des acteurs, qui sont des structures de données ayant un type proche du type suivant en Typescript:
type actor = {
   location: position;                                  // Returns the actor location (x,y)
   send: (message) => void;                             // Send a message to an actor
   actions: {
     [key: string]: (a: actor, ...rest: any) => actor;  // The actions that the actor will respond to
   };
   update: (actor) => actor;                            // Handles the actor list of messages
                                                        // and returns a new updated actor with an empty mailbox
}
Dans le cadre de ce projet, tous les acteurs ont une position dans l'espace (x,y)2. Ils ont aussi une boîte aux lettres propre qui accumule des messages. A chaque intervalle de temps, les acteurs sont mis à jour, en traitant la liste des messages dans leur boîte aux lettres. Par exemple
  • l'acteur peut recevoir le message { key: "move", params: [1, 0] } qui le fait se déplacer d'une unité vers la droite;
  • l'acteur peut recevoir le message { key: "collide", params: [] } qui lui fait perdre un certain nombre de points de vie;
  • l'acteur peut recevoir le message { key: "tick", params: [] } qui lui fait réaliser des opérations automatiques à la fin d'un intervalle de temps, comme par exemple se déplacer automatiquement s'il dispose d'une vitesse propre, mettre à jour son état interne s'il a perdu tous ses points de vie, ou envoyer des messages aux autres acteurs.
L'idée de la mise à jour est qu'elle soit faite de manière transactionnelle: si l'acteur est transformé pendant l'intervalle de temps, la mise à jour crée un nouvel acteur indépendant du premier, qui le remplace. Cette technique assure que l'on ne fasse pas d'effets de bords sur les acteurs que l'on met à jour, et permet en particulier de garder des instantanés ou snapshots des acteurs à un moment donné. A son tour, cela permet par exemple des techniques comme le retour dans le temps.
Supposons vouloir écrire une fonction make_actor qui construise un nouvel acteur capable de se déplacer quand il reçoit le message "move". Une telle fonction pourrait prendre une forme comme suit:
function make_actor(p: position): actor {
      let actor = {
            position: p,
            actions: {},
      };
      let move = (a:actor, dx: position): actor => make_actor(position_add(a.position, dx));
      actor.actions.move = move;
      return actor;
}
Il s'agit ici d'une fonction récursive, au sens où la création de nouveaux acteurs utilise le même principe de construction que l'acteur que l'on est en train de construire.
Pour gérer cet ensemble d'acteurs, il faut un chef d'orchestre, appelé ici runtime, à savoir une structure de données qui s'occupe de rassembler l'ensemble des acteurs actifs à l'intervalle de temps donné, et en plus permet d'envoyer des messages à tous les acteurs3, puis de mettre à jour les acteurs dans un second temps. Il doit être capable d'ajouter de nouveaux acteurs, et de filtrer les acteurs en fin de vie (par exemple ceux qui ont disparu de l'écran, ou qui ont un nombre négatif de points de vie). Sur le long terme, il devrait aussi permettre de récupérer les éventuels messages envoyés par les acteurs pour les retransmettre, mais aussi de gérer des contraintes globales inconnues des seuls acteurs comme par exemple les collisions de positions des acteurs.
Ce projet est un projet de programmation fonctionnelle. Pour autant qu'il soit tentant d'ajouter des fonctonnalités du monde objet, elles sont considérées comme hors-sujet. Cela concerne entre autres (mais la liste n'est pas exhaustive) la présence de l'utilisation de this, de class, et de constructor. Les appels à new sont autorisés pour créer des objets de la bibliothèque standard (comme Error) ou d'autres bibliothèques externes.

 Découpage du projet

Le découpage des tâches suivant est proposé :
  • Concevoir des acteurs et des messages.
    Écrire le code nécessaire pour définir des positions, des acteurs et des messages. Chaque acteur doit pouvoir répondre à au moins un message du type { key: "move", params: [x, y] }, et sa mise à jour doit renvoyer un nouvel acteur dont la position est décalée de (x,y) par rapport à l'acteur initial.
  • Concevoir un runtime pour coordonner les acteurs.
    Écrire le code nécessaire pour définir un runtime pour manipuler un ensemble d'acteurs évoluant sur un tick d'horloge. Pour commencer, il est conseillé de construire une structure world rassemblant l'ensemble des acteurs en jeu. À chaque tick d'horloge, cette structure pourra envoyer un message "tick" à chaque acteur en jeu.
  • Offrir une visualisation en ASCII.
    Écrire le code nécessaire pour visualiser la position des acteurs en jeu à chaque instant. La visualisation pourra se faire de différentes manières, mais devra être visualisable depuis un terminal. Pour ce faire, l'utilisation de la bibliothèque terminal-kit est autorisée (cf. la section dédiée pour plus d'informations)
  • Permettre aux acteurs de créer de nouveaux acteurs.
    Adapter le runtime de manière à pouvoir lui ajouter dynamiquement des acteurs, et faire que cette opération soit accessible aux acteurs qui le désirent. Cette fonctionnalité pourra être utilisée pour faire lancer des projectiles (eux-même des acteurs) par certaines acteurs.
    L'écriture de cette fonctionnalité demande un peu de subtilité, au sens où il faut différencier les acteurs du tick courant (sur lesquels le runtime est éventuellement en train d'itérer) des acteurs créés et qui n'arriveront en jeu que pour le tick suivant.
  • Gérer les collisions entre acteurs.
    Chaque acteur n'est censé connaître que sa propre position. Il s'agit donc d'une opération qui doit être réalisée par le runtime, qui pourra à son tour envoyer des messages "collide" aux acteurs concernés.
    Vu le modèle choisi, les acteurs se déplacent de manière discrète à chaque intervalle de temps. Si l'on programme la chose de manière naïve, il est assez facile de faire que deux agents se dirigeant l'un vers l'autre passent au travers l'un de l'autre.
  • Permettre aux acteurs d'envoyer eux-même des messages.
    Adapter le code de manière à permettre aux acteurs d'envoyer des messages aux autres acteurs. Un cas d'application possible consisterait à créer des bonus ayant un effet sur tous les acteurs ennemis, ou, plus raffiné, de faire que les acteurs se coordonnent entre eux pour mieux gêner l'adversaire.
  • Mettre en place des générateurs de niveaux.
    Concevoir une manière de générer des acteurs (qu'il s'agisse de simples murs ou d'adversaires plus intelligents) pour produire des niveaux entiers. L'important dans ce besoin est la façon de composer des éléments différents (générateur de murs, générateur d'ennemis, générateur de bonus …) pour produire le niveau entier.
  • Permettre de remonter le temps.
    Adapter le code de manière à permettre de remonter le temps. Pour cela, on pourra s'inspirer du message du développeur de Terminal Phase. L'idée est de pouvoir profiter du caractère transactionnel des mises à jour pour garder en mémoire des instantanés des acteurs à certains moments du jeu.

 Détails techniques

Dans ce projet, le code doit être écrit entièrement en TypeScript4. 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
jest.config.ts    -- jest configuration file
package.json      -- npm configuration file
tsconfig.json     -- tsc configuration file
eslint.config.js  -- eslint 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;
  • make eslint doit exécuter la commande eslint sur les fichiers de code (cf. partie sur ESLint) pour en vérifier la syntaxe;
Des fichiers de configuration sont fournis pour les différents outils, et ce sont ceux utilisés sur la forge pour les tests:
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 : @types/jest, @types/node, @types/underscore, @types/terminal-kit, @typescript-eslint/eslint-plugin, @typescript-eslint/eslint-plugin/parser, commander, eslint, fp-ts, immutable, jest, parcel, pure-rand,ramda, ts-jest, ts-node, typescript, typescript-eslint et underscore.

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 et de Typescript

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…) 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. Néanmoins, ce projet est censé être écrit avec des modules ESM.

 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.Le sujet n'impose pas le style de jeu de tir utilisé pour démontrer la bibliothèque, il demande simplement à ce qu'il soit possible d'illustrer le fonctionnement de la bibliothèque d'acteurs. Si vous voulez créer un jeu d'aventure à la Zelda, c'est cohérent avec ce principe.
2.L'espace dans lequel se déplace les acteurs est censé être celui du terminal dans lequel le code est exécuté.
3.Les messages sont envoyés à tous les acteurs dans un premier temps seulement. Il est possible de considérer ensuite que les messages ne sont adressés qu'à des acteurs particuliers.
4.Pour rappel, un fichier Javascript standard est acceptable comme fichier TypeScript