Cartouche

Prélude

Conditions de travail

Ce sujet est à faire seul. La communication n’est pas permise.

Sauf autorisation explicite pour un site web ou une URL, l’accès à internet n’est pas autorisé. Sont autorisés :

• https://cppreference.com ;
• https://git.ecole-89.com pour créer votre rendu seulement ;
• https://publish.obsidian.md/elise pour les sujets de ce rattrapage.

Critères et grille

Ce rendu permettra l’évaluation des critères du tableau qui suit. Certains critères sont spécifiques à ce sujet, d’autres en commun avec le premier sujet, d’autres encore seront exclusif au premier sujet.

Pour qu’un critère soit considéré comme obtenu, vous devez en avoir fait la preuve tout au long de la journée de rattrapage.

Rattrapage • Grille d'évaluation

Conditions de rendu

Fichiers à rendre :

• automata/Makefile
• automata/src/**/*.{cpp,hpp}

Le projet Automata doit être rendu dans un dossier automata à l’intérieur du dépôt. Le binaire produit par son Makefile doit s’appeler automata. Votre Makefile doit comporter les règles all, clean, fclean, re. Vous pouvez prendre pour référence ce Makefile.

Il est interdit de rendre des fichiers déjà compilé tels que des exécutables et des objets. Assurez-vous à chaque commit de ne rendre que des fichiers sources ou de configuration.

Dépôt de référence

Vous pouvez utiliser le dépôt de référence pour faciliter le formatage automatique de votre éditeur de code et argumenter son auto-complétion. https://git.ecole-89.com/eriizu/cpp_reference.

Déplacez le contenu du dépôt de référence dans le dossier automata/ de votre dépôt de rendu.

Fonctions autorisées

Toute la bibliothèque standard C++ est autorisée. L’utilisation de fonctions spécifiques au C (comme strlen, printf, etc.) est permise mais fait perdre les points d’utilisation de la bibliothèque standard.

Introduction

Un automate cellulaire (cellular automaton pl. automata), c’est un modèle de calcul, une façon de décrire un algorithme, où l’on génère un état à partir d’un jeu de règles immuables et d’un état précédent.

Le plus connu des automates cellulaires c’est le Jeu de la vie de Conway. Mais on va commencer par plus simple, avec une petite simulation de la physique d’un grain de sable, et vous allez vite comprendre le principe de ces automates.

Prenons un tableau de $10*10$ (avec $x$ allant vers la droite et $y$ allant vers le bas). Dans ce tableau on marque le point $(4, 4)$ comme étant un grain de sable, le reste est vide.

Prenons maintenant le jeu de règles suivant :

• si une case contient un grain de sable, on regarde si la case en dessous est libre ;
• si elle l’est on déplace le grain de sable d’une case vers le bas ;
• si elle ne l’est pas on le déplace dans la case en dessous à gauche ;
• si elle ne l’est pas non plus, idem avec la case en dessous à droite ;
• si aucune des trois cases en dessous n’est libre, le grain de sable reste immobile.

Lorsqu’on fait cycler notre programme, le grain de sable passe de $(4, 4)$ à $(4, 5)$, car la case en dessous est libre.

Si un grain de sable est tout en bas, en $(4, 9)$ (en comptant bien les cases à partir de 0) et qu’on en a un en $(4, 8)$ :

• celui tout en bas ne bougera pas au moment de cycler ;
• celui juste au dessus en $(4,8)$ tombera à gauche en $(3, 9)$.

Si un crée un grain de sable au dessus en $(4, 8)$ à nouveau :

• les deux qui sont tout en bas ne bougent pas ;
• le nouveau va tomber en $(5, 9)$ au moment du cycle.

Pour que le tout soit plus visuel, voici un extrait d’une vidéo YouTube à ce sujet :

Étape 1 : Board

Écrivez une classe Board qui sert à contenir votre plateau. Elle doit permettre :

• l’initialisation avec une taille en hauteur et en largeur ;
• l’affichage sur le terminal du plateau ;
• le placement d’une valeur à une position $(x, y)$ sur le plateau ;
• la consultation d’une valeur à une position $(x, y)$ sur le plateau.

Vous pouvez choisir le type de la valeur de chaque case du plateau. Vous pouvez choisir la stratégie que vous souhaitez pour stocker un plateau à deux dimensions.

Vous avez le droit de créer davantage de fonctions au fur et a mesure du sujet, si vous pensez en avoir besoin.

Étape 2 : le sable qui tombe

Écrivez une classe SandAutomaton qui prend à la construction une référence vers votre Board.

Elle doit avoir une fonction membre cycle_once qui fait avancer le temps d’une unité, faisant ainsi tomber le sable d’une case (si c’est possible vers le bas, sinon en dessous à gauche, sinon en dessous à droite, sinon pas du tout).

Étape 3 : boucle principale

Écrivez un main qui :

• initialise une board et un automate
• boucle
  • tous les 5 tours de boucle, crée un nouveau grain de sable en $(4,0)$, tout en haut de la board si la position est libre
    • si elle ne l’est pas : arrêtez la boucle
  • fait faire un cycle à l’automate
  • affiche la board
  • attends 500 millisecondes

Étape 4 : conway : calculer une case

L’univers du Jeu de la vie est un plateau orthogonal infini à 2 dimensions de cellules carrées, mais nous nous contenterons de notre board à taille fixe. Chaque cellule peut avoir un de deux états : vivante ou morte (respectivement peuplée ou non). Chaque cellule interagit avec ses 8 voisines, les cellules qui lui sont verticalement, horizontalement et diagonalement adjacentes. À chaque tour, chaque fois que le temps avance d’une unité, les transitions suivantes se produisent.

1. Si une cellule vivante a moins de 2 voisines : elle meurt (dépeuplement).
2. Si une cellule vivante a 2 ou 3 voisines : elle reste en vie (équilibre).
3. Si une cellule vivante a plus de 3 voisines : elle meurt (surpopulation).
4. Si une cellule vide est entourée d’exactement 3 voisines : elle prend vie (reproduction).

Et voilà c’est tout. Il n’y a aucune autre règle. C’est pourtant suffisant pour créer des choses très complexes. Vous pouvez en lire davantage depuis la page wikipedia du Jeu de la vie si vous êtes curieux·se ou avez besoin de précisions pour mieux comprendre.

Écrivez une fonction non-membre conway_compute_cell qui prend en paramètre une référence constante sur une board et un jeu de coordonnées. La fonction renvoie un booléen.

Renvoyez true lorsque que la cellule aux coordonnées qu’on vous a donné doit prendre vie ou rester en vie, renvoyez false lorsqu’elle doit rester vide ou le devenir.

Étape 5 : conway : classe

Écrivez la classe ConwayAutomaton, elle doit, comme SandAutomaton, être construite avec une Board et implémenter la fonction membre cycle_once.

Dans cycle_once avant de modifier la board, il faut que vous en fassiez une copie, car conway_compute_cell à besoin de connaitre l’état du cycle précédent tel qu’il était avant toute modification pour fonctionner correctement.

Étape 6 : conway : main

Pour tester votre automate, choisissez un motif d’exemple depuis la page wikipedia.

Modifiez votre précédent main de sorte qu’il soit possible d’exécuter votre simulation précédente en faisant ./automata sand et votre Jeu de la vie avec ./automata conway. Faites en sorte de ne pas avoir a répéter votre boucle principale : utilisez des interfaces. Pour le Jeu de la vie remplissez la board avec le motif d’exemple que vous avz choisis. Placez le au milieu. Créez une board assez grande pour qu’il puisse bouger s’il a une période non-nulle.