Available nodes

 Robot Programming

Le jeu Robozzle fait partie d'une grande famille de jeux de programmation de robots1. Dans ce jeu, des robots se déplacent dans un espace avec un ensemble d'objectifs à réaliser. Le but du jeu consiste à produire un programme (usuellement dans un langage simplifié) permettant au robot d'accomplir l'ensemble de ces objectifs. Dans Robozzle, l'objectif consiste à ramasser l'ensemble des étoiles sur le plateau sans tomber hors des limites. Ainsi, dans l'exemple suivant, le programme doit conduire le robot, le faire tourner à gauche sur les cases vertes et à droites sur les cases rouges, tout cela pour atteindre l'étoile:

const puzzle = {
   id:644,
   title:"Right on red",
   about:"",
   robotCol:7,
   robotRow:6,
   robotDir:0,
   subs:[5,4,0,0,0],
   allowedCommands:0,
   board:[ '                ',
           '                ',
           '                ',
           '     gbbbbbbg   ',
           '     b      b   ',
           '     b      b   ',
           '     b bbbbbg   ',
           '     b          ',
           '   B grg        ',
           '   b  b         ',
           '   gbbg         ',
           '                ' ]
};
Image tirée du site Robozzle pour le puzzle "Right on Red" Code Javascript spécifiant ledit puzzle

Un petit langage de programmation comme celui utilisé dans ce jeu permet quand même de créer des dizaines de puzzles plus ou moins complexes. La page des techniques est accessible et permet d'aborder les puzzles à travers diverses techniques de programmation accessibles : le color turning, le stacking ou counting (techniques d'utilisation de la pile pour implémenter des compteurs), le wall hugging / crawling et le dizzying.
L'objectif de ce projet consiste à produire un ensemble d'outils permettant de construire des puzzles du style précédent, exécuter des programmes sur ces puzzles, vérifier s'ils sont capables d'atteindre correctement un ensemble d'objectifs, et enfin concevoir des algorithmes capables, étant donné un puzzle, de trouver un ou plusieurs programmes capables de le résoudre.
Pour les besoins de ce sujet, les formats des données utilisées dans le jeu Robozzle sont purement indicatifs (comme par exemple les champs subs ou allowedCommands). Rien dans le sujet n'oblige à suivre les formats de données proposés par le site, il est au contraire encouragé d'adapter ces formats aux extensions présentes dans ce sujet.

 Robots, programmes, et mondes

Les mondes sont des grilles 2D de taille 12x16. Chaque case de la grille est colorée d'une couleur dans l'ensemble { BLEU, ROUGE, VERT, NOIR }. La couleur NOIR est considérée comme inaccessible. Les cases en dehors du monde sont aussi considérées comme inaccessibles. Chaque case accessible peut comporter une étoile ou un autre élément de décor.
Les programmes sont en fait des tableaux de N fonctions, chaque fonction représentée par un indice de ce tableau (allant de 1 à N). Une fonction est une suite finie d'instructions représentée par les dessins suivants:

Une instruction définit soit une action de la part du robot, soit un appel à une fonction du programme (dans la liste des fonctions disponibles). Parmi les instructions du langage, il est demandé de pouvoir faire un MOVE (avancer le robot d'une case dans la direction qu'il vise), un LEFT et un RIGHT (tourner le robot d'un quart de tour), et un CALL_I (appeler la fonction d'indice I). Chaque instruction peut être colorée en { BLEU, ROUGE, VERT }, auquel cas elle ne s'applique que si le robot est situé sur une case de la même couleur, sinon elle n'a aucun effet. Les instructions sont par défaut colorées en NOIR, ce qui signifie qu'elles s'appliquent sur toutes les cases. Comme le montre le dessin ci-dessus, les instructions n'ont pas de raisons d'être limitées à celles présentes sur le site de Robozzle.
L'exécution d'un programme consiste à appeler la première fonction du programme. L'appel d'une fonction exécute chacune de ses instructions en séquence, s'arrêtant à la fin de cette liste. Si l'une de ses instructions consiste à appeler une fonction, alors celle-ci est exécutée récursivement, en utilisant la même méthode. En cela, l'exécution d'un programme va faire que des appels de fonctions s'empilent et se dépilent, amenant au choix soit à la terminaison de l'exécution, soit à des boucles infinies d'exécution, soit à une explosion de la pile d'appel. A titre d'information, le puzzle suivant permet de comprendre comment utiliser la pile d'appel dans un problème.
Un puzzle consiste en la donnée:
  • d'un monde, contenant au minimum une case accessible et une position pour le robot sur une case accessible,
  • d'une spécification des objectifs devant être réalisés sur ce monde (par exemple : ramasser toutes les étoiles),
  • et d'une spécification des programmes autorisés (à savoir la taille des programmes possibles et des fonctions à l'intérieur des programmes, et la liste des instructions autorisées pour résoudre le puzzle).
Un programme est considéré résoudre un puzzle s'il suit ses spécifications et atteint ses objectifs. Un puzzle est considéré comme bien pensé si il existe au moins un programme le résolvant.
Pour simplifier le problème, le sujet fixe un certain nombre de limites à l'exécution des fonctions. Ainsi, les programmes ne peuvent pas comporter plus de 5 fonctions en tout. L'exécution d'un programme ne peut demander d'appliquer plus de 1000 instructions (l'appel d'une fonction comptant comme une instruction), sous peine d'être déclarée comme "Infinite loop error". La même exécution ne peut pas dépasser plus de 50 appels de fonctions imbriqués sous peine d'être déclarée comme "Stack overflow error". Toute exécution amenant le robot à se retrouver dans une position inaccessible est déclarée comme "Out of ground error". Le chargement d'une carte incorrecte produit un "Incorrect world error", tandis que l'application d'une instruction inconnue ou incorrecte produit un "Unknown instruction error".

 Description du projet

Le projet se propose de réaliser à la fois une bibliothèque permettant de créer des mondes et des programmes, d'exécuter lesdits programmes sur lesdits mondes, et de concevoir et résoudre des puzzles bien pensés. Une décomposition des tâches possibles est discutée ici.
  • Concevoir un langage de programmation simplifié.
    Proposer une manière de décrire des programmes et des instructions permettant de déplacer un robot dans un monde donné. Les instructions utilisées dans Robozzle doivent être présentes. D'autres instructions peuvent être ajoutées, à discuter avec vos encadrants.
  • Écrire un évaluateur pour ce langage.
    Programmer un ensemble de fonctions Ecmascript qui, étant donné un programme, et un monde, réalisent l'exécution de ce programme sur le monde, et produisent un compte-rendu de cette exécution, ainsi que son résultat (soit une terminaison normale, soit l'erreur d'exécution).
  • Proposer un afficheur pour les exécutions.
    Écrire un code générant une page HTML permettant de visualiser les exécutions de vos programmes. L'afficheur devra permettre de visualiser la pile d'appel. Pour les besoins de ce projet, cette partie est considérée comme mineure. Un fichier d'exemple vous est fourni comme base de départ à modifier.
  • Concevoir une manière de représenter les objectifs pour une exécution.
    Par exemple, dans le cas de Robozzle, un objectif consiste à vérifier qu'à la fin d'une exécution, le robot est passé par toutes les cases contenant une étoile au moins une fois. Selon le puzzle, on peut imaginer que l'objectif accepte qu'à la fin de l'exécution, le robot s'arrête de lui-même, ou bien termine sur une "Out of ground error" après avoir ramassé toutes les étoiles.
  • Proposer des façons d'étendre le monde pour en complexifier les mécanismes.
    Très simplement, il suffit, en plus des étoiles, d'ajouter des clés, des portes, des murs, des bombes, des canards tirant des lasers et des lapins sautillants …
  • Proposer des méthodes pour engendrer des problèmes.
    Dans cet objectif, il est demandé d'engendrer des programmes simples non triviaux, dans l'idée de concevoir des puzzles à partir de ces programmes. L'exemple du puzzle "recursed" montre qu'il est possible de faire des puzzles complexes avec très peu d'instructions. Évidemment, il faut engendrer le monde en même temps que le programme. Pour cela, on peut envisager différentes tactiques raffinant la simple génération aléatoire.
  • Proposer des méthodes pour trouver des solutions auxdits problèmes.
    Trouver un programme résolvant un puzzle se résume à explorer l'espace des programmes possibles. Dans certains cas, cet espace est d'une taille suffisamment restreinte pour explorer toutes les possibilités. D'un autre côté, les programmes ainsi construits sont généralement facilement encodables dans de simples chaînes de caractères. Des algorithmes génétiques peuvent être envisagés pour obtenir des solutions aux puzzles. Le sujet laisse la porte ouverte à d'autres types d'algorithmes.
  • (Optionnel) Offrir la possibilité de pouvoir revenir en arrière dans les exécutions. . L'idée serait de pouvoir aider au débuggage des fonctions pour mieux comprendre comment l'évaluateur a pu prendre ses décisions au cours de l'exécution.

 Détails techniques

Pour les besoins du projet, les fichiers devront être organisés de la manière suivante dans le dépôt :
    /               -- Base directory
      Makefile      -- Global Makefile
    /src            -- Source files
    /public         -- Web files (should be empty in the repository)
Le Makefile doit contenir une règle test permettant d'exécuter les tests propres au projet, ainsi que d'une règle gen pour générer un ensemble de fichiers dans le répertoire public. Le fichier principal doit pouvoir être démarré en utilisant la commande suivante :
node src/main.js
Les paramètres passés à cet exécutable sont laissés à la liberté des programmeurs, néanmoins ils doivent être décrits précisément dans la documentation. A part les répertoires src et public, d'autres fichiers peuvent se trouver dans le dépôt s'ils sont indispensables au projet. La commande make gen doit générer une page public/index.html valide, ainsi qu'un ensemble de fichiers js dans le même répertoire.
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 public/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.

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.


Si vous faites le projet en Javascript pur
  • Pour eslint et jest : ajoutez la ligne
    "type": "module"
    à votre fichier package.json
  • Pour jest : exécutez jest avec la variable d'environnement
    NODE_OPTIONS=--experimental-vm-modules
    . Par exemple :
    NODE_OPTIONS=--experimental-vm-modules npx jest --coverage
Si vous faites le projet en Typescript pur
  • Pour tsc : le fichier de configuration tsconfig.json vous indique comment sont compilés vos codes sur la forge (le sous-répertoire projetss6-robot est utilisé pour les tests automatiques)
  • Pour eslint : installez les paquetages @typescript-eslint/parser et @typescript-eslint/eslint-plugin, puis utilisez le fichier de configuration adapté .eslintrc
  • Pour jest : installez le paquetage ts-jest, puis utilisze le fichier de configuration adapté jest.config.js

 Utilisation de Parcel

Une partie du sujet propose de produire une page public/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: Parcel a les avantages suivants :
  • Il ne demande quasiment aucune configuration. Une commande npx parcel html/index.html se débrouillera pour rechercher toutes les dépendances à l'intérieur du fichier.
  • Il est possible de placer ses fichiers dans des répertoires de développement, et de ne produire les fichiers dans le répertoire public qu'au dernier moment en utilisant l'option --dist-dir.
  • Il est possible d'utiliser Parcel avec un serveur HTTP pour le développement. Par défaut, il vous envoie un message du style Server running at http://localhost:1234. Si vous faites pointer un onglet de votre navigateur à l'adresse http://localhost:1234, Parcel s'occupera de recharger la page à chaque modification du code dans les dépendances de vos fichiers.

 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.Qui existent en version numérique comme au format jeu de plateau, comme le fort connu RoboRally.