Bourgades et patelins
De tous temps, les hommes ont voulu construire des villes1. Des petites villes2, des grandes
villes, et encore des petites villes… Des villes en bord de
mer et des villes en montagne, des villes où il fait chaud et des
villes où il fait froid… bref, des villes dans lesquelles on
vit.
Mais, dans ce contexte un peu farfelu, posons nous la
question : qui s'est vraiment posé la question de l'optimisation du
placement du tissu socio-économique, dans un contexte de concurrence
entrepreunariale libérale mais équitable, tout en gardant à l'esprit
une juste rémunération de sa masse salariale, le tout dans un
contexte temporel discret uniformément réparti ? Un jeu combinatoire
dans lequel des bâtisseurs tirent parti des ressources de la terre
pour faire surgir une économie florissante et lucrative, pour
décerner la palme à l'investisseur le plus efficace… comme on
peut majestueusement le constater sur l'illustration suivante :
L'objectif de ce projet consiste à badiner autour du jeu de
société Little
Town, en s'en servant comme inspiration sans
complètement suivre ses règles existantes (disponibles pour
référence ici). Il
s'agira de réaliser un ensemble de structures de données et
d'algorithmes permettant de jouer des parties d'un jeu ressemblant
de loin à son modèle, tout en se permettant des variations plus ou
moins loufoques. Principalement, le but consistera à jouer des
parties correctes de manière automatique. La réalisation de
stratégies de jeu ne fait pas partie des objectifs de ce
projet. Aucune connaissance du jeu de société n'est nécessaire à la
réalisation du projet.
Une (toute) petite agglomération en devenir (Source chez iello) |
À 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.
Ressources et Employés
Dans notre jeu, plusieurs joueurs s'affrontent, chacun étant
identifié par une couleur tirée dans un
ensemble fini de cardinal
Dans le jeu, il existe au
maximum
NUM_COLORS
. Par exemple, on
peut choisir de jouer avec quatre joueurs, de couleurs
blanc WHITE
, orange ORANGE
,
rose PINK
et violet VIOLET
. Mais il est
aussi envisageble de jouer avec moins de joueurs. Le nombre maximal
de joueurs ne peut dépasser MAX_PLAYERS
, fixé ici à
4. Le nombre maximal de couleurs utilisable sur toutes les parties
vaut MAX_COLORS
, fixé ici à 11. L'interface pour
manipuler les couleurs est définie dans le fichier color.h.
Le déroulement de la partie se déroule sur un plateau de jeu
constitué d'un ensemble
de positions. L'interface pour manipuler ces
positions est définie dans le fichier position.h. Une position
est caractérisée par deux coordonnées entières
positives (x,y)
. A position donnée, il est possible de
produire la liste de ses voisins dans l'espace, sachant que leur
nombre ne peut pas dépasser MAX_NEIGHBORS
, fixé
à 8. La relation de voisinage est une relation symétrique. Pour
les besoins du projet, les positions sont bornées
maximalement : x
ne peut
dépasser MAX_X
, y
ne peut pas
dépasser MAX_Y
. Certaines positions sont donc
considérées comme invalides, ce qui signifie
qu'il n'est pas possible de jouer dessus3. A cet effet, le
nombre total de positions valides ne peut pas
dépasser MAX_POSITIONS
. Le type utilisé pour
représenter les positions est un type abstrait
et ne peut être défini que dans un fichier position.c
.
Le fait que le type soit abstrait oblige à
ne manipuler les positions qu'à travers des pointeurs dans les
fichiers autres que
Les joueurs manipulent des ressources4, qui sont spécifiées dans le fichier resource.h. Le nombre de
ressources différentes utilisées dans une partie est fixé
par position.c
. Le bénéfice apporté
par cette complication est la possibilité de proposer d'autres
implémentations que l'on pourra (un
jour) substituer en fonction des besoins de
jeu.
NUM_RESOURCES
. Le fichier contient quelques
fonctions utilitaires pour manipuler les ensembles de ressources.
Les joueurs ont chacun à leur disposition un certain nombre
d'employés. Chaque employé a un nom, et un
coût d'entretien5 sous la forme d'un ensemble de
ressources qui lui est dû régulièrement. Ces employés ont vocation à
prendre position sur le plateau de jeu et à ramener des ressources à
leur employeur, soit en les ramassant sur la carte, soit en activant
des bâtiments. Dans le jeu, il existe au
maximum MAX_WORKERS_PER_PLAYER
employés par joueur
(fixé à 6 par défaut), mais le nombre dans une partie réelle dépend
du nombre de positions valides.
Il est possible pour un joueur qui dispose de suffisamment de
ressources de construire un bâtiment sur une
des positions valides de la carte. Un tel bâtiment est caractérisé
par un nom, une valeur d'achat value
, un gain immédiat
à l'achat earns
un coût
d'activation costs
, ainsi qu'une
production supplies
. Tous ces coûts sont fournis sous
la forme d'un ensemble de ressources. Un bâtiment a lui aussi
vocation a être placé sur un emplacement valide du plateau de jeu,
et à être utilisé par les employés des joueurs pour produire des
ressources. Par exemple (le code ci-après n'est pas un code C
valide) :
{ "Farm", .value=WOOD(1), .earns=GOLD(3), .costs=GOLD(1), .supplies=CORN(1) } { "Gazebo" , .value=WOOD(3),STONE(3), .earns=GOLD(1),CORN(1), .costs=WOOD(1),GOLD(1), .supplies=CORN(1),FISH(1),WOOD(2),STONE(2) }
MAX_BUILDINGS_PER_PLAYER
bâtiments par joueur
(fixé à 7 par défaut).
Il n'est pas fourni d'interface pour les employés et les
bâtiments. Si l'on se réfère au jeu de base pour trouver des idées
de bâtiments, noter que la notion de 'points de victoires' a été
éliminée pour la remplacer par des ressources supplémentaires.
Déroulement de la partie
Soit
N
le nombre de positions valides du plateau de
jeu. Pour les besoins du jeu, on demande à ce que N >=
16
.
Le plateau de jeu est intialement rempli en plaçant aléatoirement
sur ses positions valides des mines de
ressources : champ pour le blé, lac pour le poisson, forêt
pour le bois et carrière pour la pierre6. Pour qu'un plateau de jeu soit valide, il
faut que N/4
positions valides contiennent une mine
(arrondi à l'entier inférieur), qu'au moins une mine de chaque type
soit présente en jeu, et que chaque mine possède au moins un
emplacement valide libre parmi ses voisins.
Les bâtiments disponibles pour la partie sont sélectionnés
aléatoirement parmi l'ensemble des bâtiments disponibles. Le nombre
de bâtiments disponibles est égal à N/3
(arrondi à
l'entier inférieur). Pour que la liste des bâtiments soit valide,
elle doit comporter au moins 1 ferme.
Chaque joueur dispose d'un nombre d'employés égal au minimum
entre (N/3)/num_players
et
MAX_WORKERS_PER_PLAYER
, arrondi à l'entier
inférieur. Le nombre de bâtiments qu'il peut construire est
simplement borné par MAX_BUILDINGS_PER_PLAYER
7. Il dispose également
d'un entrepôt de ressources initialement vide représentant
ses réserves.
Une partie se déroule sous la forme d'une suite
de NUM_ROUNDS
manches. Le
premier joueur d'une manche est choisi de manière
aléatoire. Pendant chaque manche, les joueurs, à tour de rôle,
choisissent une des positions valides et libre (i.e sans autre
employé, ni bâtiment, ni ressource préexistante) du plateau de
jeu. Si une telle position n'existe pas, la manche se
termine. Sinon, ils posent un de leurs employés sur cette position,
et ils doivent choisir de réaliser une action parmi deux actions
possibles :
-
Récupération de ressources : le
joueur récupère une ressource pour chaque mine de ressources
dans les voisins adjacents à la
position de son employé. Optionnellement, il peut
choisir d'activer les bâtiments adjacents. Pour commencer, s'il
n'est pas propriétaire du bâtiment en question, il paie le coût
d'activation au propriétaire. Ensuite, il récupère la
production.
-
Activation de bâtiment : pour
activer un bâtiment, le joueur doit disposer dans ses
réserves des ressources nécessaires à son activation (le
champ
costs
). Si il désire activer le bâtiment, il paiecosts
et récupèresupplies
dans ses réserves. Les coûts payéscosts
sont ajoutés aux ressources du propriétaire du bâtiment8.
-
Activation de bâtiment : pour
activer un bâtiment, le joueur doit disposer dans ses
réserves des ressources nécessaires à son activation (le
champ
- Construction de bâtiment : le joueur qui en a les moyens peut construire un bâtiment sur la case où se situe son employé. Il soustrait de ses ressources la valeur d'achat, puis il ajoute à ses ressources le gain immédiat à l'achat8. Ensuite, le bâtiment est posé sur la position correspondant du plateau de jeu, à la couleur de son propriétaire.
NUM_ROUNDS
manches,
initialement fixé à 4, ou s'il ne reste moins de deux joueurs en
jeu. Les joueurs sont classés en fonction de la quantité d'or dont
ils disposent à la fin de la partie. Il peut y avoir égalité entre
les joueurs.
Bâtiments par défaut
Le sujet ne fixe aucune contrainte sur les bâtiments utilisables
durant une partie. Il est tout à fait possible d'implémenter ses
propres bâtiments. Néanmoins, dans l'intérêt de la simplicité,
voici des ensembles de bâtiments par défaut raisonnables (le code
suivant n'est pas un code C valide9) :
Il est possible de répéter ces bâtiments de manière cyclique pour
remplir les contraintes du plateau de jeu.
[ { "Farm", .value=WOOD(1), .earns=GOLD(3), .costs=GOLD(1), .supplies=CORN(1) } { "Sawmill", .value=WOOD(2), .earns=GOLD(4), .costs=GOLD(1), .supplies=WOOD(3) } { "Pontoon", .value=WOOD(3), .earns=GOLD(5), .costs=GOLD(1), .supplies=FISH(2) } { "Quarry" , .value=WOOD(3), .earns=GOLD(5), .costs=GOLD(2), .supplies=STONE(2) } ]
Base version
Pour valider la version de base du projet, il est demandé de
produire un programme avec les caractéristiques décrites dans ce
paragraphe.
Dans la version de base, les positions disponibles sont celles
d'un rectangle classique de taille
Le projet suggère la décomposition des tâches suivante :
MAX_X *
MAX_Y
. Les valeurs de MAX_X
et MAX_Y
sont fixées pour toutes les parties, mais
doivent être supérieurs à 4x4
. La liste des voisins
d'une position donnée est celle obtenue par 8-connexité. Toutes
les positions du rectangle sont considérées comme valides, les
autres étant invalides.
Le programme doit mettre en place une boucle permettant de jouer
une partie entre plusieurs joueurs en suivant les règles
précédemment énoncées. Toute décision impliquant plusieurs choix
possibles sera prise de manière aléatoire. Le pseudo-algorithme de
la boucle principale est le suivant :
-
init_positions(0); // Use parameter equal to 0 by default board = init_board(num_players) for NUM_ROUNDS rounds: current_player = get_random_player() while there exists a player with free workers and an empty position: if current_player.has_free_workers() a_pos = board.find_empty_position() current_player.place_worker(board, a_pos) affordable_buildings = board.list_buildings_costing_less_than(current_player.resources) if affordable_buildings.length > 0 and current_player.wishes_to_build(): // Construct a building a_building = current_player.select_building(affordable_buildings) current_player.place_building(board, a_building, a_pos) else: // Earn resources neighbors = a_pos.list_neighbors() for a_neighbor in neighbors: if board.is_resource_mine(a_neighbor) current_player.earn_resource(board.get_resource(a_neighbor)) else if board.is_building(a_neighbor) if current_player.wishes_to_activate(board, a_neighbor) current_player.activate_building(board, a_neighbor) current_player = next_player(current_player) board.reset_workers_still_on_board()
-
Exemple de début de partie :
available_buildings = { Farm, Pontoon, Sawmill, Quarry }; board = { Wood at (0,0), (1,0), Corn at (2,0), (3,0), (0,1), Fish at (1,1), (2,1), Stone at (3,1), (0,2), (1,2), (2,2), (3,2), (0,3), (1,3), (2,3), (3,3), }; players = { david, sophy }; //// David plays and earns resources //// david.place_worker(board, (1,0)); david.earn_resource(...); // Takes W, F, C //// Sophy plays and earns resources //// sophy.place_worker(board, (2,1)); sophy.earn_resource(...); // Takes F, C, S //// David plays and builds a farm //// david.place_worker(board, (2,2)); david.place_building(board, farm, (2,2));
Le projet suggère la décomposition des tâches suivante :
-
Écrire des méthodes pour
transformer les couleurs en chaînes de caractères
Pour cela, il suffit de créer un fichier
color.c
qui implémente les trois fonctionscolor_*
dont les prototypes sont définis danscolor.h
. Les fonctions en question peuvent renvoyer des chaînes de caractères vides, ou alors utiliser les codes couleurs ANSI pour les plus aventureux. -
Créer des positions et des
ressources
Lesdites positions et ressources doivent respecter (sans les
modifier) les interfaces
position.h
etresource.h
spécifiées dans la section Ressources et Employés. Il est conseillé de construire chaque objet séparément et d'écrire pour chacun un exécutable différent testant son fonctionnement. -
Créer des employés et des bâtiments
Le sujet ne fournit pas d'interface prédéfinie pour ces types de données, il est donc suggéré de se poser la question des valeurs stockées à l'intérieur de ces types et des fonctions utilisées pour y accéder. Ces deux types de données ne disposent (a priori) pas de fonctions remarquables, hormis pour ce qui est des accès à leurs valeurs internes (noms, coûts …). -
Créer les structures nécessaires pour manipuler le plateau de jeu et les joueurs
Il s'agira de pouvoir placer des bâtiments et des employés à des positions du plateau, et ensuite permettre de récupérer les bâtiments et les employés à des positions données. Il s'agira aussi de gérer le stock de ressources, d'employés et de bâtiments de chacun des joueurs. -
Écrire un algorithme pour trouver le placement optimal de ses employés
Il s'agira simplement de trouver un ensemble de positions pour les employés qui maximise les ressources disponibles sans activer les bâtiments (et sans tenir compte des placements à venir des adversaires). Pour cela, il faudra discuter d'un ordre sur les ensembles de ressources. On pourra par exemple considérer le fait de maximiser simplement le nombre total de ressources, ou de maximiser le minimum des ressources 10. -
Mettre en place la boucle de jeu.
Écrire le code nécessaire pour pouvoir réaliser une partie complète, et afficher le(s) vainqueur(s) éventuel(s) sur la sortie standard. La boucle de jeu doit vérifier que les actions des joueurs sont correctes. Toute action invalide d'un joueur se termine par son exclusion immédiate. Le nombre de joueurs d'une partie doit être paramétrable sans recompiler le code.
Achievement 1 : Orée rouge emerveillant
L'idée derrière cet achievement consiste à proposer des ensembles
de positions jouables différents, pour varier les parties. Pour
cela, on propose dans un premier temps de modifier les listes des
voisins accessibles, et dans un second temps de modifier le graphe
de jeu lui-même.
- Écrire un plateau de jeu dans lequel les voisins d'une position donnée sont les positions valides accessibles à distance 2, en utilisant uniquement les directions cardinales, ou uniquement les directions diagonales.
- Écrire un plateau de jeu dans lequel le plateau de jeu a une géométrie torique (un sommet sur un bord gauche / droit / haut / bas a pour voisin le sommet sur le bord opposé droit / gauche / bas / haut).
- Écrire un plateau de jeu infernal dans lequel une position sur quatre est invalide (le choix des positions exactes est laissé libre, on pourra par exemple choisir de rendre invalides les positions d'abscisse et d'ordonnées impaires).
init_positions
, en lui passant
un paramètre adéquat. Le paramètre en question est censé être passé
à l'exécutable project
en utilisant l'option de ligne
de commande -c
.
Achievement 2 : Messires roses incrédules
Actuellement, la répartition initiale des mines de ressources sur
le plateau de jeu laisse à désirer. Si cette répartition se fait de
manière aléatoire, le résultat final peut produire un plateau de
jeu dans lequel les ressources forment des amas mal disposés. Pire,
il est même envisageable qu'une mine de ressource ne soit
accessible à aucun employé
Pour évaluer la répartition initiale des mines de ressources, on
propose de calculer la mesure suivante. On considère que deux mines
de ressources sont dans la
même composante
connexe si elles sont jointes par un chemin de mines de
ressources voisines. Les composantes connexes forment ainsi des
amas sur le plateau de jeu, dont la taille est le nombre de sommets
de la composante. Le coût d'une répartition
est la somme des carrés des tailles des amas.
Écrire un algorithme permettant de calculer la coût du placement
initial des ressources.
Proposer un algorithme recherchant une répartition initiale des
mines de ressources de coût faible. L'algorithme doit à la fois
être simple (i.e sa complexité doit rester
facilement calculable) et aléatoire (i.e il
doit pouvoir produire des répartitions différentes à chaque
partie)11
Achievement 3 : Bel matador hermétique
L'objectif de cet achievement est de proposer des tactiques plus
fines pour les placements des employés. Pour cela, on propose de se
placer dans un contexte où le joueur désire déterminer l'ensemble
des bâtiments qu'il peut construire sur un plateau de jeu donné.
Pour cela, deux approches sont envisageables :
Dans l'article The Ideal Approach
to Computing Closed Subsets in Well-Quasi-orderings est décrit
section 2.1.1 un algorithme simple pour représenter ces ensembles,
qui utilise un nombre raisonnablement faible d'objets formels
compliqués.
Mettre en place une procédure pour appliquer cet algorithme au
problème du calcul des bâtiments achetables en un tour. Discuter de
sa complexité, par rapport à la version précédente évoquée ci-dessus
travaillant bâtiment par bâtiment.
- pour chaque bâtiment dans la liste des bâtiments disponibles, chercher si on peut le construire en cherchant un placement d'ouvriers adapté;
- calculer l'ensemble des coûts des bâtiments que le joueur peut construire, et vérifier, pour un bâtiment donné, si son coût est dans cet ensemble.
![]() |
Image tirée de l'article The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings (lien sur HAL)
|
Achievement 4 : Biceps, défi sous-jacent
Pour pimenter le jeu, on propose d'ajouter un certain nombre
d'objectifs à réaliser pour les
joueurs. Chacun de ces objectifs prend la forme d'un prédicat sur
les possessions du joueur à la fin de la partie, et d'une quantité
d'or rapportée. Par exemple :
- "avoir plus de bâtiments que d'employés", qui rapporte 3 Gold;
- "avoir construit 2 bâtiments qui produisent du Corn", qui rapporte 2 Gold;
- "avoir 3 bâtiments qui forment une composante connexe", qui rapporte 2 Gold.
Achievement 5
Achievement 6
Écriture du code
Le code écrit est censé respecter les standards de codage suivant :
-
Le code devra être organisé en répertoires comme suit :
Sans surprise, le répertoire
Makefile src/ src/color.h src/position.h src/resource.h test/
src
correspond au code source, tandis que le répertoiretest
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 :
La version de base est considérée comme l'achievement 0, les autres achievements sont numérotés à partir de 1.git tag achiev0 # Create tag 'achiev0' git push --tags # Push tags on server git tag # List available tags
Les tags marquent les achievements réalisés, et suivent une syntaxe bien particulière, à savoirachiev[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 encoreachiev0.1.2.3.4
. -
L'exécutable du projet doit se nommer
project
, doit pouvoir exécuter une partie du jeu décrit dans ce projet. En plus de cela, il doit pouvoir prendre comme paramètres optionnels :- un paramètre optionnel
-s
pour initialiser le générateur aléatoire. - un paramètre optionnel
-c
pour initialiser lespositions
et qui sera transmise àinit_positions
. - un paramètre optionnel
-p
pour fixer le nombre de joueurs (par défaut égal à 4).
getopt
(voirgetopt(3)
etgetopt_long(3)
). La page de manuel degetopt
donne un exemple de code d'utilisation. Les exemples suivants donnent des idées sur les possibilités d'utilisation :
Il est tout à fait envisageable d'ajouter d'autres types de paramètres à cet exécutable../project # No parameters, world MAX_X*MAX_Y, NUM_ROUNDS equal to 4, 2 players # random initialization of the RNG, init_positions is called with parameter equal to 0 ./project -s 156 -p 4 -c 2 # One optional parameter for the number of players (here 4), # an optional parameter to pass to init_positions (here 2) # and an optional parameter to initialize the RNG (here 156)
- un paramètre optionnel
-
Le dépôt doit contenir un fichier Makefile permettant d'exécuter les tests. Pour cela, il devra comporter
au moins les
règles ci-après :
-
Une règle
principale permettant de compiler l'ensemble du code et des
tests, dont en particulier un exécutable
appelé
project
décrit dans le paragraphe précédent. La règle de compilation doit permettre de paramétrer les tailles des plateaux de jeu en passant deux variables d'environnementMAX_X
etMAX_Y
. Ainsi, la ligne suivante doit produire un exécutable jouant sur un plateau restreint au rectangle 5x6 :
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.make MAX_X=5 MAX_Y=6
-
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 commandemake test
.
-
Une règle
principale permettant de compiler l'ensemble du code et des
tests, dont en particulier un exécutable
appelé
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.
Contact
Pour toute information complémentaire, contacter : David RENAULT
disponible aux séances d'encadrement le mardi et le vendredi.
1. | Débuter une introduction sur une captation benevolentiae de mauvaise qualité mais avec un léger effet comique est une tactique éprouvée pour pousser les gens à lire les notes de bas de page. |
2. | Sur l'air du Poinçonneur des Lilas évidemment. |
3. | Il est
d'ailleurs envisageable que le nombre de positions valides soit bien
inférieur à MAX_X*MAX_Y |
4. | Noter le côté facétieux de la langue anglaise qui s'arroge le droit de parler de ces ressources avec un 's' en moins. |
5. | Dans un monde moins ludique, on parlerait de salaire. |
6. | Il s'agit d'une simplification que de ne pas autoriser des mines de ressources pour toutes les ressources. Ce n'est pas expressément interdit, mais cela pose problème avec les tailles de carte réduites. |
7. | Noter que pour construire un bâtiment, il faut aussi lui trouver un emplacement disponible. |
8. | Il n'est pas possible de profiter des gains à l'activation pour payer les coûts d'activation, ni des gains à l'achat pour acheter le bâtiment. Non mais. |
9. | Stricto sensu, c'est faux, il est tout à fait possible d'écrire des macros qui rendent ce code valide. Par contre, pour l'exemple venant avant, c'est bien plus difficile. |
10. | Il s'agit de la version de base, d'autres algorithmes de placement seront discutés plus tard dans le projet. |
11. | Il est demandé de garder un algorithme aléatoire, d'une part pour permettre des plateaux de jeu variés, et d'autre part parce que, au moins pour la version de base, il existe une manière simple et non aléatoire de produire une répartition de coût minimal. Toute proposition pour améliorer cette fonction de coût pourra être discutée. |