Skip to content

Exemples de structures de données dans les jeux de sociétés

Les mécaniques des jeux de sociétés reposent parfois sur des structures de données classiques en informatique. En voici quelques exemples :

Pile

À l’image d’une pile de livres sur laquelle il est possible d’empiler et de dépiler des éléments, une pile permet d’accéder au dernier élément ajouté. C’est dernier arrivé, premier sorti.
Dans Keltis, un joueur défaussant une carte d’une couleur, la met sur la pile de cette couleur. Les joueurs auront alors, comme action de jeu, la possibilité de la prendre. La carte empilée empêche de prendre celle qu’elle vient de recouvrir.

Pile de cartes à Keltis

Sur la photo précédente, les joueurs ont défaussé successivement plusieurs cartes jaunes, en finissant par le 9, puis le 6 puis le 7.
Lorsqu’un joueur choisit de prendre le 7 jaune, le suivant pourra choisir de prendre le 6. Si ces deux cartes ont été choisies, le 9 devient disponible, etc.

Dans Skull and Roses, un jeu principalement basé sur le bluff et un mécanisme de stop-ou-encore, un joueur va finir par retourner des cartes. Tout d’abord en retournant ses cartes, puis celle des autres joueurs en commençant par les dernières posées. Il peut s’arrêter de dépiler la pile d’un des joueurs pour choisir de dépiler celle d’un autre joueur. L’objectif étant de ne jamais retourner un crâne. Sur la photo suivante, la première carte a été retournée, permettant de voir des roses. Les trois dernières cartes peuvent, si le joueur le décide, être retournées :
Pile de cartes Skull and roses

File

À l’image d’une file d’attente de supermarché où les derniers clients se mettent à la fin de la file, dans une file, c’est le premier arrivé qui est aussi le premier sorti.
Dans Smallworld, les joueurs jouent un peuple puis en choisissent régulièrement un nouveau. Lorsque un joueur choisit un peuple, un nouveau peuple arrive en dernière position. L’intérêt est de permettre aux joueurs d’anticiper les peuples qui vont devenir disponibles. C’est équivalent à une pile, dont la règle du jeu fixe la longueur à 5.

Dans la photo ci-dessous, si un joueur décide de prendre le premier peuple de la file (les zombies des collines), alors le second peuple (les hommes-rats diplomates) deviendront le premier peuple et un nouveau peuple sera ajouté après les mi-portions scouts.
smallword

Contrairement au comportement normal d’une file, il est possible dans Smallworld de choisir un peuple qui n’est pas le premier à condition de payer plus cher. L’intérêt ludique étant d’obliger le joueur à choisir entre économiser ou choisir un peuple qu’il préfère avant qu’un autre joueur le choisisse (mais payer plus).

Arbre

Un arbre est un ensemble de nœuds reliés par des arrêtes dont un seul chemin permet de relier deux nœuds. Bref, c’est un graphe sans cycle.
Dans 7 Wonders, chaque joueur développe une civilisation en posant des cartes représentant des ressources, des bâtiments, etc. Normalement, il faut payer à chaque fois le coût pour poser la carte mais certaines cartes permettent de chaîner les développements de sa civilisation : si une carte permettant un chaînage a déjà été posée par un joueur, celui-ci pourra jouée la carte suivante gratuitement.

Plusieurs arbres de développement distincts sont présents dans le jeu. La photo suivante montre un des arbres possibles du jeu.

Un arbre dans 7 wonders

Tous les arbres disponibles ne sont pas de jolis arbres binaires. Dans l’exemple ci-dessous, trois arbres parmi ceux possibles dans le jeu de base sont présentés (dont celui de la photo) :
Quelques arbres de développement dans 7 wonders
Les couleurs représentent le type de développements (jaune pour le commerce, vert pour la science et rouge pour le militaire). Il existe des cartes avec d’autres couleurs mais ce n’est pas le sujet donc ce n’est pas la peine de s’étendre dessus et cette phrase devrait s’arrêter au plus vite pour qu’on puisse passer à autre chose. Merci.

Hors du jeu de société, les compétitions avec quart de finale, demi et finale sont les arbres binaires dont toutes les branches ont la même hauteur.

Graphe

Un graphe est un ensemble de nœuds reliés par des arêtes.

Les plateaux des Aventuriers du rail sont des graphes : chaque nœud est une ville et les arêtes sont les chemins qui relient les villes entre elles. Le but du jeu est de faire des liaisons entre des villes pour marquer des points. Faire le chemin le plus court entre chaque ville n’a pas d’intérêt. En réutilisant les mêmes routes pour plusieurs objectifs, le joueur optimisera son nombre de coups nécessaires. Chaque joueur aura tendance à faire un arbre couvrant chacune des villes de ses objectifs pour minimiser le coût de pose des chemins.

Détail de la carte États-Unis publiée pour le dixième anniversaire du jeu

Détail de la carte États-Unis publiée pour le dixième anniversaire du jeu

Représentation schématique du détail de la carte États-Unis

Représentation schématique du détail de la carte États-Unis

Il existe probablement plus de variantes de graphes que de cartes des Aventuriers du rails. Pourtant, le nombre de cartes est loin d’être ridicule : États-Unis, Europe, Allemagne, Suisse, Asie etc.

Un graphe est dit pondéré lorsque chaque arête est dotée d’un poids spécifique. La longueur de chaque route et le besoin (ou non) de locomotive peut être apparenté à son poids. Dans une des cartes du jeu représentant la Hollande, les routes ont un autre coût qui est un montant que le premier joueur posant la route doit payer à la banque et que le second joueur la construisant doit payer au premier joueur. D’un point de vue ludique, l’intérêt de donner un avantage au joueur posant rapidement des wagons et d’imposer d’une ressource secondaire à gérer pour les joueurs.

Détails de la carte Pays-Bas dans le jeu Les aventuriers du rail

Pour relier Eindhoven à Maastricht, les joueurs devront payer soit quatre cartes jaunes, soit quatre cartes mauves (ce sont les règles de base) mais aussi payer deux pièces.

Sources et propriétaires des jeux

Les schémas ont été réalisés avec graphviz :

#graphe 7 wonders
#dot -Tpng 7wonders.gv -o 7wonders.png

digraph G {
    "comptoir est" [color=goldenrod1, style=filled];
    "comptoir ouest" [color=goldenrod1, style=filled];
    forum [color=goldenrod1, style=filled];
    port [color=goldenrod1, style=filled];
    officine [color=forestgreen, style=filled];
    écuries [color=red2, style=filled];
    dispensaire [color=forestgreen, style=filled];
    arène [color=goldenrod1, style=filled];
    loge [color=forestgreen, style=filled];
    dispensaire [color=forestgreen, style=filled];
    muraille [color=red2, style=filled];
    fortifications [color=red2, style=filled];

    "comptoir est" -> forum [dir=none];
    "comptoir ouest" -> forum [dir=none];
    forum -> port [dir=none];
    officine -> écuries [dir=none];
    officine -> dispensaire [dir=none];
    dispensaire -> arène [dir=none];
    dispensaire -> loge [dir=none];
    muraille -> fortifications [dir=none];
}
#graphe aventuriers du rail
#dot -Tpng aventuriers_etats-unis.gv -o aventuriers_etats-unis.png

digraph G {
    "sault-ste-marie" -> montreal [dir=none];
    "sault-ste-marie" -> toronto [dir=none];
    montreal -> toronto [dir=none];
    montreal -> "new york" [dir=none];
    montreal -> boston [dir=none];
    boston -> "new york" [dir=none];
    toronto -> pittsburgh [dir=none];
    "new york" -> pittsburgh [dir=none];
}

Merci aux propriétaires !🙂

  • l’association Ludoludik pour Keltis et Skull and Roses
  • Nantenai pour Smallworld
  • Stéphanie pour 7 Wonders
  • Pierre pour les Aventuriers du rail

Redimensionner des images avec python-resize-image

python-resize-image est une bibliothèque python disponible sur pypi.python.org. C’est une surcouche à PIL qui simplifie son usage pour des redimensionnements courants d’image. Bien pratique, elle ne remplacera pas PIL pour toutes les autres possibilités comme les empilements d’image par exemple.

La bibliothèque est utilisable avec python2 et python3 mais le fichier wheel n’a été fait que pour la version 2.
Pour l’installer sur python2, pip install python-resize-image suffit.
Pour l’installer sur python3, il faut d’abord cloner le projet, créer l’archive avant de l’installer dans son virtualenv.

Cet article montre un rendu d’exemple pour chaque fonction.

L’image de départ fait 1000 × 413 pixels :

Le fichier d'origine avant modification

Crop : resize_crop()

Dimension d’arrivée : 800 x 700 pixels

L’image d’arrivée possède une zone transparente au-dessus et au-dessous de la photo.

Avec la fonction resize_crop()

Cover : resize_cover()

Dimension d’arrivée : 800 x 700 pixels

Contrairement au crop, l’image d’arrivée est complètement remplie par la photo d’origine

Avec la fonction resize_cover()

Contain : resize_contain()

Dimension d’arrivée : 800 x 700 pixels

Comme le crop, l’image d’arrivée possède une zone transparente au-dessus et au-dessous de la photo.

Avec la fonction resize_contain()

Largeur fixée : resize_width()

Dimension d’arrivée : 400 x 165 pixels

Pas de transparence. L’image d’arrivée est un redimensionnement de l’image de départ, sous la contrainte de la largeur donnée en paramètre de resize_with().

Avec la fonction resize_width()

Hauteur fixée : resize_height()

Dimension d’arrivée : 969 x 400 pixels

Le comportement est équivalent à resize_width(), mais pour la hauteur.

Avec la fonction resize_height()

Vignette : resize_thumbnail()

Dimension d’arrivée : 800 x 330 pixels

La transformation respecte le ratio de départ et redimensionne au mieux pour respecter les dimensions passées en paramètre. Dans l’exemple, les 800 pixels pour la largeur sont bien là mais les 700 pixels demandés pour la hauteur ont été réduits à 330.

Avec la fonction resize_thumbnail()

Sources

J’ai pris la photo au Cap (en Afrique du Sud, pas en France) la semaine précédent la DebConf 16.

L’ensemble des images sont disponibles à http://stephane.yaal.fr/python-resize-image/ au cas où l’envoi sur WordPress ait modifié les données.

Le code source qui a permis de produire les images :

from PIL import Image
from resizeimage import resizeimage

with open('origine_1000.png', 'r') as f:
    TAILLE = [800, 700]
    FIXE = 400
    img = Image.open(f)
    img = resizeimage.resize_crop(img, TAILLE)
    img.save('crop.png', img.format)
    
    img = Image.open(f)
    img = resizeimage.resize_cover(img, TAILLE)
    img.save('cover.png', img.format)
    
    img = Image.open(f)
    img = resizeimage.resize_contain(img, TAILLE)
    img.save('contain.png', img.format)
    
    img = Image.open(f)
    img = resizeimage.resize_width(img, FIXE)
    img.save('width.png', img.format)
    
    img = Image.open(f)
    img = resizeimage.resize_height(img, FIXE)
    img.save('height.png', img.format)
    
    img = Image.open(f)
    img = resizeimage.resize_thumbnail(img, TAILLE)
    img.save('thumbnail.png', img.format)

Des graphiques à la Xkcd

Ou comment faire des graphiques dans le légendaire style de XKCD (une finesse du trait plus tranchante que Michel-Ange, des couleurs plus contrastées que Léonard de Vinci).

graphique à la xkcd

Les développeurs de Matplotlib l’ont fait et intégré à la bibliothèque. Globalement, il suffit d’initialiser le script python avec la fonction xkcd(). Cette fonction initialise des paramètres pour le rendu des graphiques.

with plt.xkcd():
    #le code pour produire le graphique

Installation

Dans Debian, le paquet de base de Matplotlib est python-matplotlib pour python2 et python3-matplotlib pour python3.

Pour que le graphique ait une police similaire à ceux de xkcd, la police Humor Sans doit être installée. Dans Debian, elle se trouve dans le paquet fonts-humor-sans.

Il est possible d’avoir encore une erreur signalant que la police n’est pas trouvée :

/usr/lib/python2.7/dist-packages/matplotlib/font_manager.py:1288: UserWarning: findfont: Font family [u'Humor-Sans'] not found. Falling back to Bitstream Vera Sans

En réalité, elle est bien accessible par matplotlib mais la bibliothèque a construit un cache des polices disponibles lors de la création d’un autre graphique par le passé. Ce cache n’est pas vidé après l’installation de la police. L’erreur survient car matplotlib regarde dans son cache et non les polices actuellement installées sur le système. Il suffit donc de supprimer ce cache (fontList.cache pour python2 ou fontList.py3k.cache pour python3) et d’exécuter à nouveau le script.


stephane@foehn:~$ ls .cache/matplotlib/
fontList.cache fontList.py3k.cache tex.cache
stephane@foehn:~$ rm .cache/matplotlib/fontList.cache #si script lancé avec python2

Et là, ça marche !🙂

Évitez tout de même de mettre des accents, la police ne dispose pas de ces caractères et un « ? » est affiché à la place.

Versions des logiciels utilisés, code source

paquet python-matplotlib : 1.5.1-1
paquet fonts-humor-sans : 1.0-1

Le code source qui a permis de produire le magnifique graphique inséré au début de l’article :

from matplotlib import pyplot as plt
import numpy as np

with plt.xkcd():
    fig = plt.figure()
    ax = fig.add_subplot(1, 1, 1)
    ax.spines['right'].set_color('none')
    ax.spines['top'].set_color('none')
    plt.xticks([])
    plt.yticks([])
    ax.set_ylim([-1, 2])

    x = np.linspace(0, 10)
    plt.plot(x, np.sin(x) + 0.3, '--')

    plt.xlabel('abscisses')
    plt.ylabel('ordonnees')
    plt.title("c'est le plus beau graphique du monde !")

    plt.savefig("/tmp/graph_xkcd.png")

Réflexions à propos de l’Open Gaming Licence

Wizard of the Coast est une entreprise éditrice de jeux. Les jeux les plus connus sont Magic: the gathering et Dongeons & Dragons, le premier jeu de rôle publié. La cinquième édition de Dongeons & Dragons vient d’être publiée. Une partie des règles, le System Reference Document 5.0 (SRD5), est publiée à part, sous une licence qu’ils ont créée en 2000 : « Open Gaming License » (OGL).

Le SRD5 contient les caractéristiques des classes de personnages et de monstres. Elle ne contient donc que des mécaniques de jeu, pas l’univers ou les personnages créés pour Dongeons & Dragons 5. Cela ressemble un peu à ce que font des éditeurs de jeu propriétaires qui libèrent le moteur mais pas les modèles et les textures inclus dans le jeu. Par exemple idSoftware le fait depuis longtemps avec les moteurs successifs de Doom, Quake, etc.

Comparaison avec le logiciel libre

Si on compare les libertés garanties par les licences considérées comme libres en informatique, il est nécessaire d’adapter les 4 libertés du logiciel libre à l’équivalent pour l’OGL :

  • la liberté d’exécuter le programme, quelque soit l’usage. Dans le cas de l’OGL, cela reviendrait à considérer que le contenu est utilisable pour n’importe quel jeu, univers, etc., quelque soit le support.
  • la liberté d’étudier le fonctionnement du programme, et de le modifier pour qu’il effectue n’importe quelle tâche informatique ; dans le cas de l’OGL, cela serait la liberté de modifier n’importe quelle règle.
  • la liberté de redistribuer des copies ; cette liberté ne nécessite pas d’aptatation pour s’appliquer à l’OGL.
  • la liberté de distribuer à n’importe qui des copies de versions modifiées ; cette liberté ne nécessite pas d’aptatation pour s’appliquer à l’OGL.

Pour les deux dernières libertés, l’accès au code source est une condition nécessaire. Dans le cas de SRD5, le texte est fourni au format pdf. L’origine du .pdf semble être un fichier .docx qu’il faudrait fournir (on peut l’assimiler au code source car c’est le fichier qui a permis de produire le fichier pdf). Je n’ai pas cherché s’il est disponible.

La licence commence par

Permission to copy, modify and distribute the files collectively known as the System Reference Document 5.0 (“SRD5”)

Ce qui sont les libertés requises de copie et de modification et de redistribution. Cependant, il faut lire la licence dans les détails pour savoir si qui est réellement permis et ce qui est interdit. Un epu plus loin, la définition g indique :

« Use », « Used » or « Using » means to use, Distribute, copy, edit, format, modify, translate and otherwise create Derivative Material of Open Game Content.

Le terme « use » recouvre l’équivalent des 3 premières libertés, la quatrième y est implicite.

Quelques détails

– Il est obligatoire de fournir la licence (clause 2 et 10) :

You must affix such a notice to any Open Game Content that you Use. (clause 2)

You MUST include a copy of this License with every copy of the Open Game Content You Distribute. (clause 10)

C’est une obligation classique que l’on retrouve dans les licences libres.

– Il est interdit de modifier la licence (clause 2) :

No terms may be added to or subtracted from this License except as described by the License itself. No other terms or conditions may be applied to any Open Game Content distributed using this License.

C’est une obligation classique que l’on retrouve dans les licences libres. En cas de modification, il faut donner un autre nom à la licence créée. Cela évite les confusions et il est possible de connaître les droits et obligations de la licence simplement en connaissant son nom.

– Si une nouvelle version de la licence est publiée, n’importe laquelle reste valide pour les utilisateurs.

You may use any authorized version of this License to copy, modify and distribute any Open Game Content originally distributed under any version of this License.

Cela provoque une incertitude quand aux choix futurs de Wizards of the Coast : l’évolution future des termes de la licence est inconnue et étant donné que n’importe quelle version de la licence peut être valide, les utilisateurs de l’OGL sont dans le flou. La General Public Licence propose de mettre la version pour laquelle le détenteur du droit d’auteur accepte (par exemple, version 2, version 2 et plus, version 3, version 3 et plus, etc.) que l’utilisateur utilise pour son usage, modification, etc. L’équivalent pour l’OGL ne serait pas « 1.0a et plus », car elle n’empêche pas non plus de prendre une plus ancienne.

– Le respect de l’ensemble des obligations de la licence est obligatoire (clause 3). C’est une obligation classique que l’on retrouve dans les licences libres. En cas de non respect, les droits octroyés par la licence s’arrêtent (clause 13).

– Il est possible de commercialiser une version modifiée ou non. L’interdiction de commercialisation rendrait la licence non-libre selon les critères du secteur informatique. Aucune clause de l’OGL n’interdit un usage commercial. La clause 11 interdit l’usage du nom des autres contributeurs pour la commercialisation, sauf autorisation expresse :

You may not market…using the name of any Contributor[…]

Cependant, on peut lire sur toutes les pages dans le pied de page du document :

Not for resale. Permission granted to print or photocopy this document for personal use only.

Cette mention ne me semble pas correcte avec la licence.

– L’OGL porte une attention particulière à la protection des éléments qui ne sont pas sous OGL. Les parties sous OGL doivent être clairement définis (clause 8). Il est interdit d’utiliser le nom des contributeurs sans leur autorisation expresse (clause 11). Il est interdit de faire référence aux noms protégés (clause 7), sauf autorisation expresse du détenteur des droits sur les noms. Il semble évident que Wizard of the Coast a voulu empêcher des concurrents potentiels de réutiliser les termes connus et l’univers de D&D pour éviter toute concurrence sur ce terrain.

Versions et exclusion de garantie

La version utilisée pour SRD5 vers la 1.0a.

Si jamais le SRD5 disparaît du site officiel, il reste téléchargeable à http://stephane.yaal.fr/licence_ogl_dd/SRD-OGL_V1.1.pdf. Le licence est placée sur les deux premières pages du document.

Je ne suis pas juriste, donc si vous voulez être plus rassuré, payez-en un pour qu’il lise le texte mieux que moi.

Bonnes fêtes en équation

J’ai pu voir récemment une image d’une équation se transformant en « merry x-mas ».

Trouvant l’idée amusante, je me suis essayé à l’exercice :
Équation bonnes fêtes

Bien que ce ne soit pas très difficile, le raisonnement est inverse à celui auquel on est habitué : il ne faut pas simplifier/factoriser/transformer une équation pour trouver la (les) solution(s) mais partir du résultat (le message que l’on veut obtenir) pour le rendre moins lisible au premier abord.

Techniques utilisées ou envisagées

– utiliser des produits plutôt que des sommes. En effet, l’insertion de signes + ou – sont problématiques pour la lecture.
– utiliser les puissances pour écrire un peu différemment et profiter des règles de calcul des puissances.
– utiliser un produit remarquable. J’ai essayé avec (n² + es²) mais je n’ai rien trouvé de probant avec la suite des transformations.
– utiliser des logarithmes ou exponentielles pour modifier l’équation. Pratique pour cacher le résultat final. Je n’ai pas utilisé cette astuce.
– utiliser une intégrale pour faire le « f ». L’inconvénient est qu’il faut indiquer les bornes de l’intégrale pour que l’expression soit correcte, ce qui va gêner la lecture.

Crédits

Merci à Gilles BM pour la relecture attentive de la résolution de l’équation.🙂
L’image au debut de l’article est une capture d’écran des équations écrites avec LaTex. Le code source LaTex et le fichier pdf sont téléchargeables dans les liens situés au début de cette phrase.

La version de pdflatex pour produire le pdf :
$ pdflatex --version
pdfTeX 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian)
kpathsea version 6.2.1
Copyright 2015 Peter Breitenlohner (eTeX)/Han The Thanh (pdfTeX).
There is NO warranty. Redistribution of this software is
covered by the terms of both the pdfTeX copyright and
the Lesser GNU General Public License.
For more information about these matters, see the file
named COPYING and the pdfTeX source.
Primary author of pdfTeX: Peter Breitenlohner (eTeX)/Han The Thanh (pdfTeX).
Compiled with libpng 1.6.17; using libpng 1.6.17
Compiled with zlib 1.2.8; using zlib 1.2.8
Compiled with poppler version 0.38.0