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 :
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.
![]() |
|
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 {
Les programmes sont en fait des tableaux de :
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
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 :
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".
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).
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 :
Le
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 / -- Base directory Makefile -- Global Makefile /src -- Source files /public -- Web files (should be empty in the repository)
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
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
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
Les paquetages 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.
Node.js
nécessaires au
fonctionnement du code doivent se restreindre à la liste
suivantecommander
, 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
etjest
: ajoutez la ligne"type": "module"
à votre fichierpackage.json
- Pour
jest
: exécutezjest
avec la variable d'environnementNODE_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épertoireprojetss6-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 paquetagets-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-
Page principale
de
Parcel
. - Tutoriel
pour l'utilisation de
Parcel
(privilégiernpm
àyarn
). -
Options de
la CLI de
Parcel
.
-
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 styleServer running at http://localhost:1234
. Si vous faites pointer un onglet de votre navigateur à l'adressehttp://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.