Travail pratique de programmation concurrente
Le but de ce travail pratique est de réaliser une simulation du jeu agar.io. Dans ce jeu 2D dans le navigateur, en réseau, chaque joueur contrôle, à la souris, le déplacement d’une cellule, représentée par un disque de couleur. En début de partie, la cellule apparaît sur le domaine de jeu à une position aléatoire. Ce domaine a des dimensions finies, de sorte qu’une cellule ne peut en “sortir”. La “loi de la nature” s’applique aux cellules : une cellule plus grosse peut “gober” une plus petite. En contrepartie, une cellule plus petite se déplace plus rapidement qu’une grosse. Pour gagner en masse, une cellule doit soit manger des cellules plus petites qu’elle-même, soit manger de la nourriture disséminée sur le domaine de jeu de manière aléatoire. Le but étant bien entendu de manger les autres, rester en vie et d’être la plus grosse cellule au classement. L’objectif du TP est de réaliser une simulation simplifiée du jeu original, comme vu en fig. 1. Les cellules seront contrôlées par ordinateur et il faudra gérer l’affichage, la gestion du clavier et la logique du jeu de manière concurrente.
Pour ne pas faire “grossir” vos cellules trop rapidement, nous vous recommandons de déduire le rayon d’une cellule en fonction de sa masse par la fonction suivante :
\[r = 4 + 6 \sqrt{m}\] où \(r\) est le rayon et \(m\) la masse.
De manière analogue, pour obtenir une vitesse inversement proportionnelle, mais lissée, en fonction de la masse, votre professeur de maths favori vous recommande d’utiliser la fonction sigmoïde suivante :
\[s = \alpha + \frac{\beta}{1 + e^{\gamma (m - \delta)}}\] où \(s\) est la vitesse et \(m\) la masse.
La fig. 2 illustre cette fonction et ses paramètres.
Les trois types de collisions sont les suivants :
Le programme à développer est basé sur une architecture multi-threadée organisée de la manière suivante :
main) s’occupe seulement de gérer les arguments de la ligne de commande, initialiser les structures de données, et créer les threads.Concernant les collisions, deux variantes sont possibles :
agario et sa syntaxe est la suivante :agario <width> <height> <seed> <food> <dir> <res> <nf> <freq> <workers> <cells>
Exemple : agario 960 600 0 0.001 0.01 0.05 0.1 30 4 10width et height spécifiés sur la ligne de commande, entiers plus grands ou égaux à 100.seed et food spécifiés sur la ligne de commande :
seed (entier) est la graine à utiliser par le générateur de nombres aléatoires.food (valeur décimale dans le range [0..1[) représente la proportion de cases du domaine occupées par des particules de nourriture. Par exemple, 0.1 représente une surface occupée de 10% par de la nourriture.dir, res et nf (valeurs décimales dans le range [0..1[) représentent les probabilités de :
dir: changement de direction d’une cellule (vivante).res: pour une cellule morte, réapparaître (testé à chaque frame).nf (pour “new food”): faire apparaître une nouvelle particule de nourriture sur une position qui ne comprend pas déjà de nourriture.freq est un entier (> 0), représentant la fréquence d’affichage en Hz.workers est un entier (>= 1) donnant le nombre de threads travailleurs.cells est un entier (>= 1 et >= workers) représentant le nombre de cellules.makefile devra être présent à la racine et ayant comme première règle la compilation de votre programme produisant l’exécutable.gfx_create) et d’afficher le jeu à la fréquence spécifiée (fonction gfx_present) par l’argument freq sur la ligne de commande. Attention à ce que l’affichage du domaine ne soit réalisé qu’une fois celui-ci entièrement mis à jour !gfx_create, gfx_present, etc.); cf. section suivante.rand_r() à la place de rand() (voir explications plus détaillées plus loin).#define ou le mot-clé const).sleep de 1 seconde est incorrect car il est nécessaire de tenir compte du temps d’exécution de la routine R.Nous vous conseillons de compiler votre code avec gcc et les options de compilation suivantes :
De plus, si vous utilisez des barrières dans votre code, vous devez inclure cette directive :
Pour réaliser le rendu graphique de votre programme, vous devez utiliser la librairie gfx incluse dans le repository du TP. L’entête de la fonction gfx_drawcircle vous est fournie dans gfx, à vous de l’implémenter.
Pour obtenir un déroulement identique du simulateur entre différentes exécutions, vous devrez vous servir du seed donné en argument. Dans un contexte multi threads, le combo srand() et rand() n’est pas suffisant, car rand() n’est pas réentrante. Vous devrez donc utiliser à la place rand_r(unsigned int* seed) en lui passant un dérivé par thread de ce seed initial (man rand_r pour plus d’infos). Veillez à ce que chaque thread dispose d’un seed unique et différent.
Les mesures du temps d’exécution peuvent être effectuées avec la fonction clock_gettime de la librairie <time.h> comme montré ci-dessous :
struct timespec start, finish;
clock_gettime(CLOCK_MONOTONIC, &start);
... // code à mesurer
clock_gettime(CLOCK_MONOTONIC, &finish);
double elapsed = (finish.tv_sec - start.tv_sec) * 1e6;
elapsed += (finish.tv_nsec - start.tv_nsec) / 1e3;À noter que selon les versions de gcc, le code ci-dessus requiert la librairie rt. Pour ce faire, passez -lrt à gcc au moment de l’édition des liens.
Pour appuyer vos explications à l’oral, vous devrez produire un schéma du fil d’exécution du code et de la synchronisation entre threads, à rendre avec votre code. La fig. 5 illustre un exemple d’un tel schéma. La syntaxe à utiliser est libre, mais les mécanismes de synchronisation doivent clairement apparaître.
N’oubliez pas de lire attentivement le document “Consignes Travaux Pratiques.pdf” disponible sur la page CyberLearn du cours. Les consignes supplémentaires et spécifiques pour ce travail sont les suivantes :