Available nodes

 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 :
Une ode au pixel-art.
  • 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)
{	
	initscr();			/* Start curses mode 		  */
	mvprintw(LINES/2,COLS/2,
		 "Hello World !!!");	/* Print Hello World		  */
	refresh();			/* Print it on to the real screen */
	getch();			/* Wait for user input */
	endwin();			/* End curses mode		  */

	return(EXIT_SUCCESS);
}

 Contact

Pour toute information complémentaire, contacter : David Renault présent aux séances d'encadrement le vendredi après-midi.