Tilings
Ce sujet est construit sur l'idée de réaliser des pavages du plan, à
l'aide d'objets simples nommés
des tuiles de
Wang. Il s'agit de tuiles carrées divisées en quatre
triangles. Chaque triangle est associé à un côté du carré, et coloré
d'une couleur particulière. Le dessin suivant
permet de rapidement se faire une idée de la forme d'une tuile, ainsi
que du fait que les couleurs des triangles ne sont pas forcément
toutes distinctes1 :
La réalisation de ces pavages va se faire sous la forme d'un jeu à
plusieurs joueurs, se jouant sur un plateau carré, dans lequel chaque
joueur place à son tour une tuile de manière à 1) que l'ensemble des
tuiles reste connexe et 2) que les bords de deux tuiles attenantes
soient de même couleur. Les couleurs autorisées sont spécifiées dans
le fichier
color.h
suivant :
Les tuiles sont arrangées dans des jeux de
tuiles ou decks, qui sont simplement la
donnée d'un ensemble de paires (tuile × quantité), chaque paire
signifiant la présence d'une tuile répétée un certain nombre de fois
dans le jeu. La description des tuiles est fixée dans le
fichier tile.h
:
La fonction
{
{, 4},
{, 2},
{, 2},
{, 2},
{, 2}
}
Les règles du jeu sont particulièrement simples. Le jeu de tuiles est
mélangé aléatoirement, et distribué équitablement aux joueurs. Chaque
joueur fait une pile de l'ensemble de ses tuiles, et les joue une par
une. Le premier joueur pose sa tuile aléatoirement sur le plateau, et
ensuite, à chaque tour de jeu, chaque joueur dans l'ordre pose une
tuile sur le plateau respectant les conditions de contiguïté et de
connexité. Si un joueur ne peut pas poser de tuile à son tour, il
remet sa tuile en dessous de sa pile et passe son tour. Si aucun
joueur ne peut jouer, ou si un des joueurs a joué sa dernière tuile,
la partie se termine. Par défaut, le joueur ayant posé le plus de
tuiles gagne la partie.
Pour simplifier l'écriture de code, il est décidé que chaque fois
qu'un joueur est placé devant un choix, il prend une
décision aléatoire uniforme parmi l'ensemble des
choix possibles. Le projet ne s'intéresse pas à l'écriture de
stratégies pour les joueurs.
![]() |
![]() |
Tuiles de Wang (image Wikimedia) |
Pavages de Truchet (image math.cnrs.fr) |
#ifndef _COLOR_H_
#define _COLOR_H_
struct color; // Anonymous struct for colors
// A string giving the color name
const char* color_name(const struct color* t);
// An ANSI-colored string describing the color
const char* color_cstring(const struct color* t);
// Return a color from its name, or NULL
// The relation between `name` and `struct color*` is bijective.
struct color* color_from_name(const char* name);
#endif // _COLOR_H_
#ifndef _TILE_H_
#define _TILE_H_
#include "color.h"
enum direction { NORTH, SOUTH, EAST, WEST,
MAX_DIRECTION, ERROR_DIRECTION = -1 };
struct tile; // Anonymous struct for tiles
#define MAX_DECK_SIZE 100
struct deck_pair {
const struct tile* t; // a pointer to a tile
unsigned int n; // a number of occurrences of this tile
};
struct deck {
struct deck_pair cards[MAX_DECK_SIZE]; // an array of struct deck_pair
unsigned int size; // the number of struct deck_pair in `cards`
};
// A tile that is empty
const struct tile* empty_tile();
// A predicate telling if the tile is empty
int tile_is_empty(const struct tile* t);
// A comparator between tiles
int tile_equals(const struct tile* t1, const struct tile* t2);
// Accessors to the color of the edges
struct color* tile_edge(const struct tile* t, enum direction d);
// A function that fills a deck with tiles
// The contents of the deck `d` after the call must always be the same.
void deck_init(struct deck* d);
#endif // _TILE_H_
deck_init
prend en paramètre un deck
initialement vide, et le remplit avec un ensemble de tuiles
particulier. Le projet est prévu pour pouvoir fournir différentes
implémentations des fichiers color.[ch]
et tile.[ch]
afin de varier les parties possibles avec
des couleurs différentes, des tuiles différentes, et des decks
différents. Pour fixer les idées, voici un exemple de deck
possible contenant 12 tuiles :
À 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. 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. La version de base
n'est pas forcément représentative du travail nécessaire pour
atteindre la moyenne.
É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 :
Le répertoire
latest/ Makefile src/ tst/ achiev0/ Makefile src/ tst/ achiev1/ ...
latest
correspond au dernier achievement réalisé. Les autres répertoiresachiev?
sont des copies du code validant l'achievement en question. La version de base est considérée comme l'achievement 0. -
Le code devra contenir (entre autres) 4 fichiers
src/color.[ch]
etsrc/tile.[ch]
. Les deux.h
sont fournis dans la première partie du sujet et ne doivent pas être modifiés. Les deux.c
restent à écrire et devront respecter ces interfaces. Les tests devront passer avec des versions différentes de ces fichiers.c
(et donc des typesstruct color
etstruct tile
). En particulier, les tests automatiques fourniront une implémentation particulière avec lesquels le code devra continuer à compiler et s'exécuter correctement. -
Chaque répertoire du projet (
latest
etachiev?
) 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
-n
pour indiquer le nombre de joueurs, - un paramètre optionnel
-b
pour indiquer la taille du plateau, - un paramètre optionnel
-s
pour initialiser le générateur aléatoire.
./project # No parameters, 2 players, board 10x10, random initialization of the RNG ./project -n 5 -s 156 # One optional parameter for the number of players (here 5) # and an optional parameter to initialize the RNG (here 156) ./project -b 25 # One optional parameter for the size of the board (here 25x25)
- un paramètre optionnel
-
Une règle
test
lançant l'ensemble des tests pour le dernier achievement réalisé. Chaque achievement est censé posséder ses propres tests dans un exécutable différent.
-
Une règle principale permettant de compiler un exécutable appelé
-
Chaque répertoire doit contenir un fichier source s'inspirant
de ce fichier
, qui (dans cet exemple, il reste à
compléter) prend en paramètre une graine aléatoire à l'aide de
l'option '
-s
'.
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 projet suggère la décomposition des tâches suivante :
Il n'y a aucun lien entre le fait de "valider
la version de base" et celui de "valider le projet". Le fait de
"valider la version de base" est simplement le premier pas vers la
réalisation des achievements.
Le programme doit mettre en place un système de jeu, pendant
lesquels des joueurs vont pouvoir placer des tuiles les uns à la
suite des autres. Le programme se termine lorsque toutes les tuiles
ont été jouées, ou que tous les joueurs ont passé leur tour. Le
pseudo-algorithme de la boucle principale est le suivant :
d = deck_init(); b = board_init(); players = players_init(); n = players.length(); split_deck(d, players); While the n last turns have not all been skipped active_player = get_next_player(players); t = active_player.cards.top(); p = list_authorized_places(b, t); if (!p.is_empty()) place_tile(b, select_position(p)); active_player.cards.pop() display_results()
-
Créer des tuiles et des jeux de tuiles
Implémenter les structures de données et les fonctions permettant de manipuler des valeurs de typecolor
,tile
etdeck
. A terme, il est demandé de pouvoir fournir au moins deux versions différentes des couleurs, tuiles et jeu de tuiles disponibles en jeu. Les couleurs et tuiles utilisées peuvent évidemment différer des exemples fournis ci-dessus. -
Créer une structure de file pour gérer les jeux des joueurs
Une telle file devrait pouvoir accepter d'insérer des éléments à l'intérieur (push
), de récupérer un pointeur vers l'élément en tête de pile (top
) ainsi que de retirer des éléments si la file n'est pas vide (pop
), tout cela en respectant l'ordre d'insertion. Aussi, il faudra pouvoir mélanger, et distribuer un jeu de tuiles à un ensemble de joueurs. Même si c'est envisageable, le sujet n'impose pas de gérer la liste des joueurs avec une file2. -
Mettre en place la boucle de jeu
Écrire le code nécessaire pour pouvoir faire jouer une partie à un ensemble de joueurs, et afficher le joueur gagnant à la fin de la partie. Les joueurs font des choix aléatoires, en sélectionnant un emplacement autorisé aléatoirement parmi la liste des positions jouables. Le premier joueur peut jouer sur n'importe quelle case libre. -
Assurer le respect des règles
Mettre en place les vérifications nécessaires par la boucle de jeu pour 1) assurer que l'ensemble des tuiles en jeu reste connexe au cours de la partie et 2) vérifier que deux tuiles adjacentes partagent la même couleur sur leur jonction. Tout joueur sortant hors des clous est évincé de l'ensemble des joueurs actifs, ses tuiles restent en jeu, mais son score en fin de partie est nul.
20
. Le nombre de
couleurs différentes est compris entre 2
et 20
. Le nombre de tuiles possibles dans un deck, et
aussi dans la main d'un joueur, est de 200
. La taille
maximale du plateau est de 50x50
.
Achievement 1 : Patterns
Dans cette extension, les tuiles ont désormais un propriétaire, qui
correspond au joueur ayant posé la tuile. Les règles du jeu
définissent aussi un ensemble de motifs,
rapportant chacun un certain nombre de points. Par exemple, le motif
suivant représente une tuile rouge avec 4 tuiles voisines accolées,
représentant un score de 34 points :
Chaque motif possède une tuile centrale, qui est utilisée pour
déterminer le propriétaire du motif. Le nombre maximal de motifs
pour une partie est de
Motif : | |
Score : | 34 |
20
. La taille d'un motif est
définie comme la distance maximale
(de Chebyshev)
d'une tuile du motif à la tuile centrale. La taille maximale d'un
motif est de 2
.
Le calcul du score final est modifié par rapport à la version de
base, et correspond pour chaque joueur à la somme des scores des
motifs dont il est propriétaire. Plusieurs motifs peuvent se
recouvrir, tant qu'ils ont des tuiles centrales différentes.
Achievement 2 : Connections
Dans cette extension, on propose une façon supplémentaire de marquer
des points. Les couleurs des tuiles définissent des zones connexes
du plan recouvrant un certain nombre de tuiles. Deux triangles de
même couleur sont considérés comme connexes s'ils partagent une
arête commune, ou un sommet commun qui est centre d'une tuile.
Dans l'exemple suivant, considérant que les zones noires
représentent des couleurs autres que la couleur rouge, la zone rouge
recouvre 9 tuiles différentes :
Le score associé à une zone connexe est défini comme
le carré du nombre de tuiles couvertes. Le
propriétaire d'une zone connexe est défini comme le joueur étant le
propriétaire d'un maximum de tuiles de cette zone. S'il y a
plusieurs joueurs se partageant ce maximum, ils se partagent le
score de la zone équitablement, en arrondissant à l'entier
inférieur.
Achievement 3 : Influence
Dans cette extension, on propose de modifier la façon dont les
joueurs deviennent propriétaires des tuiles.
Chaque tuile possède un niveau (entier) de propriété par joueur. Le
joueur qui joue une nouvelle tuile dispose d'un niveau de propriété
de
100
sur cette tuile, tandis que celui des autres
joueurs est nul. Mais un joueur qui pose une tuile adjacente à cette
même tuile (dans les huit directions) après
qu'elle ait été placée peut remonter son niveau de propriété. Le
premier joueur à poser une tuile adjacente remonte son niveau
de 90
, le suivant de 80
, et ainsi de suite
pour les 8 voisins possibles. A chaque tour, les niveaux de
propriété de tous les joueurs baissent de 1
, sans
jamais passer en dessous de 0
. Le (ou les)
propriétaires d'une tuile sont ceux dont le niveau de propriété sur
cette tuile est maximal.
Un joueur supplémentaire nommé "The King" apparaît dans la liste des
joueurs. Il ne dispose pas de jeu de tuiles, et ne pose jamais de
tuiles. A son tour de jeu, il sélectionne aléatoirement un
emplacement sur le plateau de jeu, saute dessus, et s'il tombe sur
une tuile, réduit le niveau d'influence des propriétaires de toutes
les tuiles atteignables de manière connexe sur la même ligne et la
même colonne. Pour une tuile atteinte, le niveau d'influence du ou
des propriétaires (et uniquement eux) est réduit de 50
,
les niveaux d'influence des autres joueurs ne sont pas modifiés.
Il peut donc toujours y avoir plusieurs propriétaires pour une tuile
donnée. Si tous les joueurs ont un niveau de propriété nul sur la
tuile, ils sont tous propriétaires. Les propriétaires d'une zone
connexe sont ceux pour lesquels la somme de leurs niveaux de
propriété sur les tuiles de la zone est maximal.
Achievement 4 : Symmetries and Loops and Adjacencies
Dans cette extension, on propose que les tuiles puissent être
utilisées à symétrie près. Il est alors possible d'appliquer aux
tuiles des rotations à 90°, 180° ou 270°. Les compatibilités de
couleurs entre tuiles ne sont pas modifiées, simplement, on permet
d'utiliser une tuile donnée dans 4 configurations possibles3.
En parallèle, la notion d'adjacence entre emplacements du plateau
est modifiée. Certains emplacements du plateau ne permettent pas de
placer de tuiles, mais acceptent n'importe quelle tuile à
côté. Certains emplacements du plateau voient leurs bords être
associés à un autre emplacement du plateau. Cas d'application
pratique : rendre le plateau torique et créer (en théorie, si la
fin de partie recouvre l'ensemble du plateau) des pavages
périodiques.
Enfin, les tuiles définissent maintenant elles-même leurs relations
d'adjacence. Ainsi, sur une tuile donnée, deux triangles d'une même
couleur partageant une arête peuvent ne pas être considérés comme
adjacents. Réciproquement, deux triangles d'une même couleur se
touchant uniquement sur un sommet peuvent être considérés comme
adjacents. Par exemple, on pourrait considérer une tuile de la forme
suivante :
dans laquelle les sommets nord et sud ne sont pas connectés, tandis
que les sommets est et ouest le sont.

Ces trois extensions peuvent être gérées en parallèle ou en série,
mais elles partagent toutes les trois une forme d'évolution du
code. Laquelle ?
Achievement 5 : Blocs
A chaque tour de jeu, le joueur peut désormais tirer une suite de
tuiles accolées, et placées sur le terrain. Pour faire simple, il
joue seul sur son plateau, prépare une "méta-tuile" composée de
plusieurs tuiles accolées, et ensuite place cette "méta-tuile" sur
le plateau. Il s'arrête de tirer des tuiles dès qu'aucun accolement
n'est possible ou que la "méta-tuile" n'est plus plaçable sur le
plan de jeu, ou que l'on a atteint un nombre maximum de 3 tuiles
pour la "méta-tuile". Les accolements sont calculés de manière
aléatoire, et les symétries s'appliquent au bloc entier.
Contact
Pour toute information complémentaire, contacter : David RENAULT
disponible aux séances d'encadrement le mardi et le vendredi.
1. | Pour les personnes intéressées, par le sujet, le chapitre 1 de l'EJCIM 2017 (École de Jeunes Chercheurs en Informatique et Mathématique) donne un panorama des problèmes actuels, et la vidéo de Veritasium suivante sur Youtube fait de même avec un point de vue plus général. |
2. | Quoique la réalisation d'une implémentation d'une structure de données file qui évite de dupliquer le code entre les joueurs et les tuiles sera considérée comme un bonus. |
3. | Les plus aventureux des codeurs peuvent considérer à la fois les rotations et les symétries des tuiles, ce qui autorise 8 transformations possibles par tuile. Les plus combinatoristes peuvent argumenter sur le fait qu'on pourrait autoriser des symétries non continues. Ils peuvent le faire (je veux dire, argumenter). |