Available nodes

 Une histoire de sable et de magiciennes1...

Noita est le nom d'un jeu vidéo construit autour d'un concept2 simple : le monde en deux dimensions est constitué d'un ensemble de pixels/cellules évoluant plus ou moins indépendamment selon des règles physiques simples. Le sable tombe et s'accumule en tas pyramidaux, l'eau s'écoule, tombe et s'accumule en tas horizontaux, la vapeur d'eau monte et est bloquée par les plafonds, le pétrole s'écoule comme un liquide, mais s'enflamme puis se transforme en gaz lorsqu'il est mis en contact avec du feu … L'image suivante (un peu confuse il est vrai, mais tellement riche en couleurs) permet de se faire une petite idée de la façon dont se traduit ce concept :
Image du jeu Noita (image Wikimedia)
L'objectif de ce sujet consiste à développer un ensemble d'outils et de programmes décrivant un système dans lequel des pixels/cellules évoluent au cours du temps. Ledit système s'inspire des automates cellulaires qui ont été largement popularisés par le jeu de la vie de John Conway. Ces modèles de calcul sont capables de reproduire des comportements extrêmement riches3, ainsi que des techniques algorithmiques assez fascinantes, comme cet algorithme d'accélération permettant de calculer des nombres délirants d'itérations desdits automates. Le système s'inspire aussi des modèles de tas de sable largement explorés en combinatoire, et ainsi que des problèmes algorithmiques classiques comme les problèmes de transport (abordés dans ce sujet d'un point de vue seulement algorithmique).

Le sujet ne porte pas sur l'écriture d'un jeu, puisque le code devra s'exécuter sans aucune interaction avec l'utilisateur. Il ne porte pas non plus sur la partie graphique, qui sera évoquée dans la partie Rendu graphique. Il consiste principalement à concevoir les algorithmes permettant de simuler des comportements ressemblant en priorité à ceux produits par des automates cellulaires, et par extension à ceux apparaissant dans un jeu comme Noita. Les programmes devront produire sur la sortie standard des matrices de points de couleur (i.e des images) qui, affichées les unes à la suite des autres, décriront l'évolution de l'automate cellulaire de manière dynamique. Les idées développées dans la vidéo suivante ont largement inspiré l'écriture de ce sujet.

À propos des achievements : ce sujet de projet est construit sur la notion d'achievement. Un achievement est un ensemble de fonctionnalités à développer pour le projet. Les achievements doivent être réalisés dans l'ordre, et de manière cumulative. Ils seront débloqués à chaque fois qu'au moins une équipe de projet aura rempli les conditions de l'achievement précédent et aura fait valider la chose par son encadrant. La version de base correspond à l'achievement initial. L'évaluation du projet est basée en partie sur le nombre d'achievements réalisés, et la version de base n'est pas forcément représentative du travail nécessaire pour atteindre la moyenne.

 Des automates cellulaires

Un automate cellulaire est une construction4 constituée d'un ensemble de cellules évoluant au cours du temps. Cette partie fixe un ensemble de définitions qui seront utilisées pour réaliser le projet.

Un monde est un ensemble de cellules pouvant chacune prendre un état. Dans ce projet, nous nous limiterons à des mondes qui sont des grilles 2D de largeur WIDTH et de hauteur HEIGHT. Une cellule est alors identifiable à une paire de coordonnées (x,y) dans ladite grille. Chaque cellule peut prendre un ensemble fini d'états. Dans ce projet, les états en question seront des entiers non signés (représentant en même temps des couleurs). L'état (global) de l'automate cellulaire est l'ensemble des états de ses cellules, et forme ici une matrice d'entiers (représentant en même temps une image).

Un automate cellulaire évolue d'état en état au cours du temps. Concrètement, à chaque seconde, il prend un état global particulier. Vu qu'un état correspond à une image, l'évolution de l'automate constitue une sorte d'animation. La règle de passage d'un état à un autre est définie de la manière suivante pour chaque cellule de l'automate. L'automate autorise un ensemble de règles d'évolution locales constituées d'un motif et de sa transformation (aussi appelée 'change' dans le code). Il est possible de représenter graphiquement une règle de la manière suivante :

Motif :  Transformation : 
Une règle définit un voisinage d'une cellule et les états des différentes cellules dans ce voisinage. Elle permet alors le changement d'état uniquement de la cellule centrale. Dans l'exemple ci-dessus, toute cellule de couleur noire ayant 3 voisins de couleur blanche disposés comme indiqué change d'état pour devenir jaune5. Pour les besoins de ce projet, on considérera les voisins dans un espace torique (i.e le voisin de droite d'une cellule sur le bord droit est la cellule sur la même ligne sur le bord gauche). Le nombre de transformations pour une règle donnée est fixé à 1, mais on peut imaginer des automates autorisant plusieurs transformations possibles pour une même règle.

Toutes les cellules évoluent en même temps et indépendamment, au cours d'une opération appelée une itération. Cela a pour conséquence importante qu'il ne faut pas changer l'état d'une cellule si celle-ci peut encore influer sur ses voisines. Il est donc nécessaire de commencer par enregistrer l'ensemble des changements d'états, et ensuite de les appliquer. Nous demandons dans ce projet d'enregistrer lesdits changements d'état dans une structure de file, ce qui permettra par la suite de les inspecter et de rejeter des changements incohérents. Le dessin suivant représente une itération utilisant la règle précédente :

État 1 :  État 2 : 

L'exemple le plus connu d'automate cellulaire est le jeu de la vie, pour lequel les règles sont les suivantes : une cellule noire avec trois voisins blancs devient blanche, tandis qu'une cellule blanche avec soit 0, soit 1, soit 4 ou plus voisins blancs devient noire. La vidéo suivante permet de se rendre compte de la complexité des comportements représentables par ces règles d'évolution d'une simplicité très élégante. L'image suivante, tirée d'une thèse de Paulo Rosa publiée en 2015, explicite ces règles d'une manière graphique.

Pour les besoins du sujet, les règles d'évolution de l'automate cellulaire devront être implémentées à travers un fichier world.h et un fichier rule.c incluant le fichier  rule.h. En particulier, les deux fichiers .h précédents devront être inclus dans le dépôt sans modification (sauf indication ultérieure du sujet). Au final, il devra être possible de fournir différents ensembles de règles permettant de simuler différents comportements d'automates.

Remarque sur world.h : les largeurs et hauteurs des struct world sont fixées de manière statique. Il s'agit d'une précaution pour permettre de réaliser le sujet sans aucune forme d'allocation dynamique. Par conséquent, toute forme d'allocation dynamique (à base de malloc ou apparenté) est interdite pour ces structures. Plus généralement, le sujet peut être traité sans aucune forme d'allocation dynamique.
Remarque sur rule.h : une caractéristique importante de ce ficher est que le struct rule est un type incomplet. Cela a pour conséquence que tout code utilisant rule.h ne peut connaître ce qu'il y a à l'intérieur de la structure. En particulier, cela permet de remplacer le code de rule.c par un autre code. Un des tests automatiques du projet fait exactement cela. Mais aussi, il devient possible de proposer des ensembles de règles différents en compilant le code avec des fichiers rule.c différents. Vous le remarquerez certainement au moment où vous voudrez accéder aux membres de votre structure sans passer par les fonctions de l'interface.
Ci-dessous, un exemple simple d'automate cellulaire produisant des triangles de Sierpinski.

 Données de sortie

Les données produites par le programme devront être écrites sur la sortie standard et avoir le format suivant :
  • Une ligne contenant deux entiers strictement positifs séparés par un seul espace, représentation la largeur L et la hauteur H des images utilisées.
  • Pour chaque image produite, une ligne contenant uniquement le caractère #, puis ensuite une série de H lignes contenant exactement L entiers suivis chacun par des espaces.
Les images sont ainsi écrites sous forme de matrices d'entiers, chaque entier N représentant un triplet (R,G,B) de la manière suivante :
  • R = N % 256
  • G = (N/256) % 256
  • B = (N/65536) % 256
Par exemple, la couleur blanc correspond à l'entier 16777215 (code RGB (255,255,255)), la couleur noire correspond à l'entier 0 (code RGB (0,0,0)), et la couleur rouge correspond à l'entier 255 (code RGB (255,0,0)). Pour les besoins du sujet, on fixe par convention le fait que l'entier maximal sur 32 bits (i.e 4294967295) représente n'importe quelle couleur.

Il n'est pas demandé de fournir le nombre d'images produites. Les données écrites sur la sortie d'erreur ne sont pas contraintes par cette spécification, le programme peut y écrire ce que bon lui semble.
Le  code suivant représente une sortie standard valide pour des images de taille 4x3.

Un code ne produisant pas une sortie correcte (i.e suivant ces spécifications) sur des entrées correctes ne valide pas les projets.

 Écriture du code

Le code écrit est censé respecter les standards de codage suivant :
  • Le code devra être organisé en répertoires de la manière suivante :
        Makefile
        src/
        src/world.h
        src/rule.h
        tst/
    
    Sans surprise, le répertoire src correspond au code source, tandis que le répertoire tst doit contenir le code nécessaire aux tests. Les différents achievements devront être marqués dans le dépôt à l'aide d'étiquettes (ou tags) git. Ajouter une étiquette se fait avec les commandes suivantes :
    git tag achiev0    # Create tag 'achiev0'
    git push --tags    # Push tags on server
    git tag            # List available tags
    
    La version de base est considérée comme l'achievement 0, les autres achievements sont numérotés à partir de 1.
    Les tags marquent les achievements réalisés, et suivent une syntaxe bien particulière, à savoir achiev[0-9\.]+. Noter qu'une fois un tag mis sur le dépôt, il n'est plus possible de le modifier. Seul le code avec le dernier tag sera considéré pour le rendu final. S'il n'existe pas de tel tag, il sera considéré qu'il n'y a pas de code rendu. Un projet sans code rendu ne valide pas les projets. Afin de simplifier la vie, la syntaxe des tags autorise les tags suivants correspondant tous à l'achievement 0 : achiev0, achiev0.1 ou encode achiev0.1.2.3.4.
  • Le dépôt doit contenir un fichier Makefile permettant de le compiler et comportant au moins les règles ci-après.
    • Une règle principale permettant de compiler un exécutable appelé project, qui exécutera une partie entière de jeu comme spécifié ci-après, en prenant comme paramètres optionnels :
      • un paramètre optionnel -m pour spécifier le nombre d'images produites par le programme.
      • un paramètre optionnel -s pour initialiser le générateur aléatoire.
      L'analyse de la ligne de commande se fera au moyen de la bibliothèque getopt (voir getopt(3) et getopt_log(3)). La page de manuel de getopt donne un exemple de code d'utilisation. Les exemples suivants donnent des idées sur les possibilités d'utilisation :
      ./project               # No parameters, 10 pictures, board WIDTH*HEIGHT, random initialization of the RNG
      ./project -m 5 -s 156   # One optional parameter for the number of pictures (here 5)
                              # and an optional parameter to initialize the RNG (here 156)
      
      La règle doit permettre de paramétrer les tailles des images produites en passant deux variables d'environnement WIDTH et HEIGHT. Ainsi, la ligne suivante doit produire un exécutable générant des images de taille 40 par 30 :
      make WIDTH=40 HEIGHT=30
      Le fichier Makefile fourni en exemple permet déjà de réaliser ce paramétrage. Il conviendra à chacun de comprendre comment il fonctionne ou de poser la question à un de ses encadrants.
    • Une règle test lançant l'ensemble des tests pour le dernier achievement réalisé. Il est tout à fait envisageable d'avoir plusieurs exécutables de tests différents, mais ils devront tous être lancés par la commande make test.
Un code qui ne compile pas est un code sans intérêt, et un code qui n'intéresse pas le responsable des projets est un code qui ne valide pas les projets.

 Base version

Pour valider la version de base du projet, il est demandé de produire un exécutable avec les caractéristiques décrites dans ce paragraphe.

Le programme doit mettre en place une boucle produisant des images utilisant le format décrit à la section Données de sortie. Ces images décrivent l'évolution d'un automate cellulaire sur un monde en deux dimensions de taille WIDTH*HEIGHT torique. Le nombre d'images produites par l'exécutable est par défaut de 10. Le pseudo-algorithme de la boucle principale est le suivant :

w = world_init();
rule_init();
printf("%d %d\n", WIDTH, HEIGHT);
For as many steps as necessary
    q = queue_init();
    For all available rules r, and all cells (x,y)
        If rule_match(w, r, (x,y))
            queue_append(q, r, (x,y))
    For all elements (r, (x,y)) in the queue q
        world_apply_rule(w, r, (x,y));
    world_disp(w);
A chaque fois qu'un choix à faire est nécessaire dans l'exécution de l'algorithme ci-dessus (par exemple pour initialiser le monde), il est demandé d'utiliser la fonction rand. Celle-ci devra être initialisée à l'aide d'une graine passée à la fonction srand. Pour permettre de reproduire les comportements, il est demandé au code de pouvoir prendre la graine en question en paramètre (avec l'option -s), et d'afficher la graine utilisée à chaque exécution sur la sortie d'erreur.
Le projet suggère la décomposition des tâches suivante :
  • Créer des mondes, des cellules et des états

    Implémenter le code nécessaire à la manipulation de la structure de données struct world (sans modifier world.h). En particulier, coder les fonctions permettant de créer un monde (vide ou rempli de couleurs aléatoires), et afficher le monde en question en respectant les spécifications de la section Données de sortie.
  • Créer des règles pour un automate cellulaire

    Définir une structure de données struct rule, ainsi que le code nécessaire à la manipulation de ces structures (sans modifier rule.h). Noter que l'écriture d'un tel code implique de se poser la question non seulement des types de données pour les règles, mais aussi des règles que l'on veut implémenter. Par exemple, il est possible de se limiter à coder la règle donnée ci-dessus pour commencer, voire une règle plus simple. Ensuite, coder les 6 fonctions dont les prototypes sont donnés dans le .h en question.
  • Construire une structure de file

    Cette structure est censée pouvoir stocker les modifications qu'il faut apporter aux états des cellules à chaque itération. L'interface utilisée pour manipuler la file en question est laissée libre, mais il est nécessaire de pouvoir créer une file vide, lui ajouter des élements, itérer sur tous les éléments à l'intérieur de la file, et enfin les retirer un à un. Il est fortement suggéré de proposer de quoi tester cette fonction dans un exécutable indépendant.
  • Mettre en place l'algorithme de calcul d'itération

    Écrire le code nécessaire pour pouvoir faire évoluer un automate cellulaire à partir d'un état de départ aléatoire et produire les images correspondantes sur la sortie standard.
  • Implémenter les règles du jeu de la vie

    Implémenter les règles du jeu de la vie de Conway pour démontrer à la fois que votre code est valide, mais aussi qu'il est possible de changer (relativement) facilement l'ensemble des règles utilisées dans le code. Noter que, vu comment est fournie l'interface rule.h, une modification des règles doit se faire par une recompilation avec des fichiers différents.

 Achievement 1 : Multicoloritude

Les automates décrits précédemment sont déterministes, au sens où chaque règle n'autorise qu'une unique transformation. Vu que cela donne un résultat assez triste et déterministe, on propose de laisser les règles autoriser plusieurs transformations possibles (le sujet n'étant pas très subtil à ce sujet6). En reprenant l'exemple initial, on peut imaginer une règle ayant deux transformations possibles :
Motif :  Transformations : 
Assez naturellement, il est possible d'utiliser la fonction rule_num_changes pour indiquer le nombre de transformations associées à une règle donnée, et la fonction rule_change_to pour obtenir les couleurs différentes couleurs possibles, comme dans le pseudo-code suivant :
let r be a rule
n = rule_num_changes(r)
for idx in [0 .. n-1]
    c = rule_change_to(r, idx)
    // do something with the color c ...
Évidemment, si une règle autorise plusieurs transformations possibles, il faut choisir laquelle appliquer. Le choix se fait en tirant aléatoirement une transformation parmi toutes les transformations possibles d'une règle donnée. Dans la mesure où cet achievement introduit l'usage de plusieurs couleurs dans le code, il est opportun de se souvenir que le sujet prévoit à la section Données de sortie une couleur spéciale permettant de représenter n'importe quelle couleur.

 Achievement 2 : Mouvements multiples

Quitte à proposer des automates cellulaires avec plusieurs transformations possibles, une idée consiste à considérer la cellule centrale comme une particule qui change de couleur (ce que l'on a fait jusqu'à présent), mais qui peut aussi se déplacer. On associe donc à une transformation un vecteur de translation fixe (dx, dy) (sous la forme d'un couple d'entiers signés). Appliquer une transformation consiste alors à enlever la particule de la case centrale de coordonnées (x,y) (qui devient noire) et à la déplacer sur la case (x+dx, y+dy) (qui prend la couleur de la particule).

Plusieurs problèmes vont découler de cette modification :

  • D'une part, la cellule d'arrivée pourrait être déjà occupée;
  • D'autre part, plusieurs particules pourraient décider de se déplacer au même endroit.
Dans tous les cas, on parle de conflit. Noter que jusqu'à présent, les particules ne se déplaçant pas, on n'avait pas de conflit à gérer. Dans cet achievement, on propose de gérer les conflits de la manière suivante :
  • A partir d'un état du monde donné, la liste des changements à réaliser est calculée et placée dans une file, sans appliquer aucun changement. Les particules sont traitées ligne par ligne de haut en bas, colonne par colonne de gauche à droite.
  • Les changements sont appliqués dans l'ordre de la file. Si plusieurs particules veulent aller au même endroit, c'est la dernière à le faire dans l'ordre de la file qui gagne.
Enfin, pour pouvoir accéder aux différents déplacements dans le reste du code, il est nécessaire d'ajouter de nouvelles fonctions permettant de manipuler les règles. Ainsi, on ajoute les deux fonctions suivantes au fichier rule.h :
/** Return the displacement of index `idx` of the rule `r`, namely the
 * change in x (resp.y). `idx` must be strictly less than
 * `rule_num_changes(r)`. */
int rule_change_dx(const struct rule* r, unsigned int idx);
int rule_change_dy(const struct rule* r, unsigned int idx);
A partir de cet achievement, il est autorisé d'utiliser la version étendue du fichier rule.h qui ajoute simplement ces deux prototypes.

 Achievement 3 : Incompressibilité

L'achievement précédent laisse à désirer dans la mesure où certaines particules disparaissent pour des raisons arbitraires (i.e l'ordre dans lequel elles sont gérées). Cet achievement propose de gérer le problème de manière plus fine en apliquant un principe dit d'incompressibilité que ne renierait pas Lavoisier : aucune particule ne se perd lors des itérations des automates. Du fait de ce principe, si jamais il existe un conflit entre plusieurs particules, on cherche à le résoudre en en choisissant une parmi celles visant une place donnée, la déplaçant et laissant les autres sur place.

L'ensemble des déplacements de particules ainsi engendrés dans les mondes peut être vu comme une endofonction. L'usage de ce terme particulièrement distingué masque le fait qu'il s'agisse en réalité d'un simple graphe où chaque sommet n'a qu'un seul successeur7. La compréhension de la structure d'un tel graphe permet d'envisager des algorithmes dédiés ayant des complexités variées. Dans un premier temps, on propose l'algorithme de résolution de conflit suivant :

  • Pour chaque cellule d'arrivée vide possible, calculer la liste de toutes les particules désirant se déplacer sur cette cellule.
  • Lorsqu'une de ces listes est de longueur > 1, la case est en conflit, en ce cas choisir aléatoirement parmi les candidats de la liste celui qui va se déplacer sur la cellule en question.
Mettre en place un tel algorithme de gestion des conflits et proposer un test permettant de le voir en action.

 Achievement 4 : Généricité des règles

La façon dont sont implémentées des règles comme les règles du jeu de la vie peut, selon la façon dont on s'y prend, être sous-optimale. Par exemple, si on énumère toutes les règles possibles pour le jeu de la vie, même en ne considérant que des cases bicolores, il existe 2^9 = 512 règles différentes8.

Dans cette partie, on propose d'implémenter les règles comme des pointeurs de fonctions. Une implémentation de la struct rule peut ainsi prendre la forme suivante :

struct rule {
    int (*match)(const struct world*, unsigned int, unsigned int);
    // other attributes more or less significant
};
Le pointeur de fonctions ainsi défini représente une fonction permettant de calculer si une règle s'applique à un emplacement d'un monde donné9. Les plus sagaces des lecteurs se rendront compte qu'à ce moment du sujet, on a largement étendu les possibilités des règles : initialement une règle avait une entrée et une sortie, et maintenant elles peuvent avoir plusieurs entrées (achievement 4) et plusieurs sorties (achievement 1).

Mettre en place les modifications nécessaires pour pouvoir représenter le jeu de la vie à l'aide de tels pointeurs de fonctions (en toute logique, il devrait suffire de 2 règles au lieu des potentielles 512 précédentes).

 Achievement 5 : Incompressibilité fine

Le principe d'incompressibilité présenté à l'achievement 3 est fâcheux, au sens où même s'il préserve les particules existantes, il a tendance à fortement ralentir le flot de ces particules lorsque celles-ci entrent en conflit. On propose ici une autre version de l'algorithme de résolution des conflits un peu plus fine.

Rappelons que la structure des mouvements de nos particules est censé être une endofonction, et que celle-ci peut se représenter sous la forme d'un graphe dirigé dans lequel chaque sommet ne possède qu'un unique successeur. La page suivante (tirée de la page Wikipedia suivante) fournit un exemple d'un tel graphe :

Graphe d'une endofonction (image Wikimedia)
Dans l'image précédente, on se rend compte que les cellules en conflit (vers lesquelles plusieurs particules cherchent à se déplacer) sont les cellules 0, 3, 4, et 6. L'algorithme décrit à l'achievement 3 ne permet de déplacer des particules que vers des cellules vides. On propose ici de calculer les chemins et les cycles de l'endofonction, et d'appliquer l'algorithme suivant :
  • Si des particules apparaissent dans un cycle, on les déplace par permutation circulaire. Dans l'exemple ci-dessus, cela signifierait que les particules dans le cycle (1, 6, 3) se déplacent toutes d'une case dans la direction du cycle.
  • Si des particules apparaissent dans un chemin ne se terminant pas par un cycle, on propose de toutes les faire avancer en même temps d'une case sur leur chemin. Il faut évidemment que la dernière particule se propose d'avancer sur une case vide.
En particulier, un tel algorithme devrait permettre à des particules d'échanger leur place (comme un gaz et un solide par exemple), et à des tas de sable de tomber en parallèle plutôt que goutte à goutte.

Il existe de nombreux algorithmes de détection de cycles dans une endofonction, en particulier celui dit du lièvre et de la tortue dû à à R. W. Floyd. Une mise en place efficace de cet algorithme demande d'avoir une représentation efficace de l'endofonction permettant de calculer facilement l'image de la fonction f comme dans l'exemple ci-dessus.

Mettre en place un tel algorithme optimisé de résolution des conflits. A ce stade, il est aisé de se rendre compte que de nombreuses optimisations de l'algorithme précédent peuvent exister si le cycle contient des cellules vides. Le bonus consiste alors à maximiser à chaque étape le nombre de particules déplacées.

 Achievement 6 : Multicoloritude is back

Le système des couleurs pour représenter les particules est actuellement mal fichu. En effet, il considère qu'un état (par exemple, du sable) correspond à une couleur (par exemple, du jaune). Cela a plusieurs conséquences : d'une part, cela impose que le sable est forcément d'une seule et unique couleur, et d'autre part, cela empêche de réutiliser des couleurs plusieurs fois. Ainsi, si l'on désire représenter des effets de flammes, il est envisageable de considérer que les flammes possèdent plusieurs couleurs (par exemple, du rouge, du orange et du jaune).

Modifier la représentation des couleurs dans le jeu de manière à ce que :

  • les états entiers des cellules ne soient plus des couleurs (tout en restant des valeurs entières);
  • chaque état entier est associé à un ensemble de couleurs possibles;
  • au moment du rendu d'une case dans un état donné, une couleur aléatoire parmi les couleurs possibles est choisie.
Noter que cette réalisation est différente du premier achievement qui autorisait plusieurs couleurs pour une règle, les couleurs correspondant à des états différents. Ici, on considère que du sable reste du sable (l'état ne change pas) mais qu'on peut l'afficher avec des couleurs différentes.

 Achievement 7

 Rendu graphique

Un utilitaire est fourni pour effectuer le rendu graphique des matrices produites dans ce projet. Cet utilitaire est un binaire compilé à partir d'un code C écrit utilisant la bibliothèque SDL2. L'utilitaire en question est disponible sur les machines de l'ENSEIRB-Matmeca en utilisant le chemin /net/ens/renault/local/bin/sdl. Il s'utilise de la manière suivante :
./project | /path/to/sdl
L'exécutable project produit des données sur sa sortie standard conformes à la spécification fournie à la section Données de sortie, et la commande ci-dessus redirige ces données vers l'entrée standard de l'utilitaire sdl, qui se charge de les afficher dans une fenêtre graphique. Ainsi, il est possible de produire des animations de la forme suivante  :
Au début des projets, l'utilitaire n'est fourni qu'à travers le binaire précédent, pour limiter les recopies de code intempestives. Ce binaire est compilé pour des machines Linux 64 bits, mais moyennant suffisamment de motivation, l'auteur peut proposer de compiler des binaires pour d'autres architectures. Il n'est pas inenvisageable que le code de l'utilitaire soit rendu disponible à un moment dépassant au minimum la moitié des projets.

L'utilitaire permet d'afficher les données produites de manière graphique (et en couleur !), mais dispose aussi d'un mode manuel permettant de se déplacer entre les images et donc de vérifier si du code est exécuté correctement. Les options disponibles actuellement sont :

Usage: ./sdl  [-f delay] [-w width] [-hmM]

	-f delay	 Specify delay between frames (e.g '-f 10')
	-h		 Display this help message
	-m		 Enables the keyboard to control frames at the end of the run
	-M		 Enables the keyboard to control frames at the start of the run
	-w width	 Specify the width of the SDL window (e.g '-w 100')

Les personnes désireuses d'utiliser cet utilitaire peuvent le télécharger en fonction de l'architecture de leur machine :

  • Linux x86-64 : sdl
  • MacOS (Mach-O) arm64 : sdl
  • MacOS (Mach-O) x86-64 : sdl
N'oubliez pas dans tous les cas que ces exécutables ne peuvent fonctionner qu'avec la bibliothèque SDL2 installée sur la machine. Le code est disponible dans le dépôt https://thor.enseirb-matmeca.fr/git/projetss5-sdl-all.

 Contact

Pour toute information complémentaire, contacter : David RENAULT disponible aux séances d'encadrement le mardi et le vendredi.

1.Le terme anglais 'witch' admet une traduction en français comme 'sorcière', selon les dictionnaires anglais comme le Cambridge Dictionary, mais le sujet prend de manière unilatérale des libertés avec les traductions de termes provenant de toutes façons du finnois. Toute remarque sur le caractère un peu faisandé du ou des jeux de mots constituant la base de ce sujet recevra un blâme à coups de tromblon.
2.Plusieurs concepts, en réalité, le jeu étant original à plus d'un titre, mais le sujet se concentre sur l'un d'entre eux en particulier.
3.L'auteur ne refuse absolument pas de discuter de machines de Turing et autres aspects abordés dans l'article Interstices donné dans le lien, ne le tentez pas trop non plus.
4.Les gens chics parlent de modèle de calcul ou de système dynamique et ce sont des sujets passionnants, et on a dit qu'il ne fallait pas trop le tenter.
5.La couleur jaune est choisie ici pour mieux visualiser le changement, mais elle pourrait aussi bien être blanche.
6.L'auteur s'entraîne à l'antanaclase de chantier, toujours de bon goût dans les soirées de l'ambassadeur.
7.La page Wikipedia utilise le terme encore plus pompeux de pseudo-forêt dirigée. En en anglais en plus.
8.Si, à la lecture de ceci, vous vous rendez compte que vous avez codé quelque chose de répétitif 512 fois dans votre code, il est peut-être temps de faire le point et de réfléchir sur votre amour pour le travail à la chaîne.
9.Noter qu'il est difficile à cet instant du sujet de mettre d'autres pointeurs de fonctions dans la structure, le plus intéressant étant une fonction apply qui applique la règle en question. Mais les achievements précédents rendent les algorithmes d'application des règles trop complexes pour que cela se fasse de manière raisonnable.