Robotic
Simulateur de robots
_Le site Robozzle propose un jeu
dans lequel il s'agit de programmer un automate de façon à le faire se
déplacer sur un terrain en deux dimensions, ceci afin de ramasser un
ensemble d'étoiles éparpillées sur le
terrain. La version en
Javascript du site offre un certain nombre de terrains possibles.
Le sujet consiste à remplir successivement les 4 phases suivantes :
Le sujet consiste à remplir successivement les 4 phases suivantes :
- Afficher les niveaux de jeu dans un terminal
A cet effet, il sera nécessaire de définir un format texte de représentation des niveaux, et de les afficher en utilisant la bibliothèque ncurses décrite ci-après. Pour simplifier le déboguage, il est fortement recommandé d'avoir deux types de sorties dans le terminal : en mode texte et en mode ncurses. L'image ci-contre est un simple encouragement à faire mieux que l'auteur du sujet.
- Charger un programme de robot et simuler son exécution dans un niveau
Là encore, il faudra définir un format de représentation des programmes, simuler l'exécution de ce programme (potentiellement récursif) et les mouvements du robot associé, et en fournir un rendu sous forme d'une animation graphique dans le terminal utilisant la bibliothèque ncurses. - Charger un niveau et calculer un programme permettant d'attraper toutes les étoiles du niveau
Pour un niveau donné, le site Robozzle fixe des bornes sur le programme utilisé pour le résoudre. Donc, pour chaque niveau, il s'agit de tester l'ensemble des programmes possibles jusqu'à trouver une solution. Pour prévenir l'explosion combinatoire inévitable de ce type d'algorithmes, il est conseillé de s'intéresser initialement à des niveaux dont la solution est de taille faible. - Générer aléatoirement des niveaux réalisables, en leur attribuant une note de difficulté
Toute latitude est laissée aux programmeurs pour fournir des niveaux aléatoires. Les niveaux que l'on devra obtenir seront censés être suffisamment aléatoires pour que l'on ne retrouve pas les mêmes en exécutant le générateur plusieurs fois de suite. Il pourra être plus facile d'engendrer des programmes aléatoires, puis de construire un niveau valide correspondant.
_Il n'est pas demandé dans le sujet de réaliser
une interface pour résoudre à la main les niveaux. En cas de
difficulté, il est conseillé de réduire la taille des objets
utilisés (taille des niveaux, taille des programmes, nombre
d'instructions possibles ...) pour simplifier le problème. Le projet
peut être considéré comme réussi lorsque la 3ème phase est
au moins partiellement fonctionnelle.
_Le code devra être fourni avec une batterie de tests montrant le bon fonctionnement des différentes parties du
programme, par exemple sous la forme d'un script à exécuter ou d'une
règle d'un fichier Makefile.
Bibliothèque nCurses
Afin d'afficher des informations dans un terminal avec un peu de style, il est demandé de passer à travers la bibliothèque ncurses. La plupart des questions quant à cette bibliothèque peut être répondue dans le howto accessible en ligne, ainsi que sur sa version PDF. Les exemples de programme donnés dans le howto sont disponibles à l'adresse suivante sous la forme d'une archive .tar.gz. A titre d'exemple et pour simple référence, voici le code du "Hello World" donné dans le HOWTO, très légèrement modifié :
#include <ncurses.h> #include <stdlib.h> int main(void) { /* Start curses mode */ initscr(); /* Print Hello World */ mvprintw(LINES/2,COLS/2, "Hello World !!!"); /* Print it on to the real screen */ refresh(); /* Wait for user input */ getch(); /* End curses mode */ endwin(); return(EXIT_SUCCESS); }