Générer un jeu de Dobble

Lorsque j’ai découvert le jeu de Dobble, je me suis tout de suite demandé comment on pouvait générer un tel ensemble de cartes.

Après y avoir vainement réfléchi, j’ai trouvé quelques références ici et qui font appel à la géométrie projective.

L’idée m’est alors venue de générer un jeu personnalisé avec des images ayant un thème commun (des visages familiers, des lieux de vacances, etc.)

Le projet :

  1. Trouver une façon de générer les combinaisons de cartes et symboles
  2. Générer les combinaisons et les stocker dans fichier texte
  3. Faire un script qui génère les images de chacune des cartes avec ImageMagick
  4. Faire imprimer les images sur un support se rapprochant d’une carte à jouer

Les points 1 à 3 étant techniquement réglés, j’en partage ici les différentes étapes. Le dernier point est encore en projet…

1. Trouver l’algorithme

Après avoir parcouru liens mentionnés plus haut, il me restait à en faire l’implémentation. Après quelques tâtonnements, je suis tombé sur ce post de stackoverflow qui propose quelques implémentations.

2. Générer les cartes

J’en ai choisi une qui est sous-optimale (elle génère 58 symboles plutôt que 57). Le jeu reste cependant tout à fait valide et le bout de code implémentait aussi une fonction de vérification du jeu généré. J’ai légèrement modifié la sortie pour avoir un fichier texte facile à lire pour la suite.

Le fichier source est ici : mainDobble.cpp

Le résultat du programme est un fichier texte de la forme suivante où chaque ligne représente une carte composée de 8 symboles, eux-même représentés par un entier.

 

wilhelm@beluga:~/code/dobble$ head -5 dobble.txt
0   1   2   3   4   5   6   50
7   8   9   10  11  12  13  50
14  15  16  17  18  19  20  50
21  22  23  24  25  26  27  50
28  29  30  31  32  33  34  50
wilhelm@beluga:~/code/dobble$
Le format du fichier texte contenant les cartes de Dobble

Fichier des cartes résultant : dobble.txt

On peut aussi générer des jeux avec 4, 6 ou même 12 symboles par carte. Par exemple:

3. Le script de rendu

Pour créer le rendu des cartes, un petit script bash: card.sh.

Syntaxe

Premier argument: le fichier texte en entrée. Second argument: le chemin du répertoire où sont les images. Les cartes sont générées dans un répertoire output

wilhelm@beluga:~/code/dobble$ ./card.sh dobble.txt ~/picture/dobble
Commande pour lancer le rendu des cartes.

On notera la double utilisation de shuf. L’algorithme de génération des cartes est assez ordonné. Un double brassage s’impose. Le premier, c’est pour réarranger l’ordre des cartes (le shuf de la boucle for). Le second (encapsulé dans une fonction Shuffle pour ventiler les éléments d’une ligne plutôt que des lignes), est plus important. Il s’agit de ventiler la position des symboles sur les cartes. Sinon, les mêmes symboles ont tendance à se retrouver aux mêmes positions et ça enlève un peu du piment au jeu.

La boucle principale appelle ImageMagick pour créer un montage à partir d’images stockée dans le répertoire passé en argument et du fichier texte mentionné plus haut.

#!/bin/bash

Shuffle()
{
	 echo $* | tr " " "\n" | shuf | tr -d " " 
}

##############################################
# Main
##############################################
INPUT=$1
DIR=$2
OUTDIR=ouput

BAK_IFS=${IFS}
IFS=$'\r\n' 
Image=($(ls $DIR))
IFS=${BAK_IFS}

mkdir -p ${OUTDIR}
export i=0
export SMSIZE=500
export BIGSIZE=600
export FULLSIZE=1600
shuf ${INPUT} | while read a b c d e f g h; do
	sa=( $( Shuffle ${a} ${b} ${c} ${d} ${e} ${f} ${g} ${h} ) )
	im=( \
		"${DIR}/${Image[ ${sa[0]} ]}"\
		"${DIR}/${Image[ ${sa[1]} ]}"\
		"${DIR}/${Image[ ${sa[2]} ]}"\
		"${DIR}/${Image[ ${sa[3]} ]}"\
		"${DIR}/${Image[ ${sa[4]} ]}"\
		"${DIR}/${Image[ ${sa[5]} ]}"\
		"${DIR}/${Image[ ${sa[6]} ]}"\
		"${DIR}/${Image[ ${sa[7]} ]}" ) 

	OUTPUT=${OUTDIR}/card_${i}.jpeg
	echo ${OUTPUT}
	((i++))

	 convert  -size "${FULLSIZE}x${FULLSIZE}" xc:white  \
-gravity Center \
\( "${im[0]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate -45 	-repage +0+0 		\)		\
		\( "${im[1]}" 	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 45 		-repage +1000+0 	\)		\
		\( "${im[2]}" 	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 0		-repage +0+600	 	\)		\
		\( "${im[3]}" 	-resize "${BIGSIZE}x${BIGSIZE}"	-gravity Center -rotate 60		-repage +400+400  	\)		\
		\( "${im[4]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate 180		-repage +1200+500 	\)		\
		\( "${im[5]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate -135	-repage +0+1100 	\)		\
		\( "${im[6]}" 	-resize "${SMSIZE}x${SMSIZE}"	-gravity Center -rotate 180		-repage +800+1100 	\)		\
		\( "${im[7]}"	-resize "${SMSIZE}x${SMSIZE}" 	-gravity Center -rotate 135		-repage +1100+1100	 \)		\
		-compose Multiply -layers flatten  tiff:- | convert - 	-mattecolor DarkOrange4 -frame 20x20+0+0 \
${OUTPUT}
done
Script pour le rendu des images de carte

Ci-dessous, un exemple du rendu de quelques cartes générées. Il ne reste plus qu’à ajuster un peu les dimensions en fonction des proportions des cartes à imprimer. Mais pour ça, il faut trouver un fournisseur/site web, qui propose d’imprimer 57 cartes différentes pour un prix raisonnable. C’est la fameuse étape 4, qui est encore en suspend…

Reception des colis

Ça y est, le facteur est arrivé ! Les deux paquets la même journée.  C’est la fête du grand déballage.

Première étape: installer un système d’exploitation. Comme premier OS, j’ai sans hésité commencé par Raspbian. Comme son nom le laisse deviner, cette distribution est basée sur Debian. Comme  je suis plutôt familier avec cette famille de distributions et que la gestion des paquets est juste parfaite avec les commandes apt, ça me semble être un bon point de départ.

Le site officiel de Raspberry Pi propose même des torrent, ce qui peut accélérer le téléchargement.

Pour copier l’image de l’OS sur une carte SD, j’ai utilisé Win32DiskImage tel que recommandé sur cette page. Il suffit alors de sélectionner le fichier image (une fois décompressé, on a un fichier de la forme date-bla-bla-raspbian.img, en l’occurrence 2014-01-07-wheezy-raspbian.img, qui doit faire autour de 2 GO).

On sélectionne la lettre du disque où se cache la carte SD. Attention, on dit qu’il ne faut pas se tromper de lettre… Win32DiskImage ne se pose pas trop de questions existentielles, c’est un peu un dd sous Windows. Si vous lui demandez d’écrire sur un disque, il va tenter de le faire, comme ça, directement, sans trop y réfléchir. Si vous vous trompez de disque, il peut vous arriver des choses que je n’ai pas moi-même expérimentées…

Capture écran de l'installation de Raspbian sur la carte SD.
Installation de Raspbian sur la carte SD via Win32DiskImager.

Une fois terminé, on branche la carte SD dans l’engin, on branche sur un moniteur via le HDMI, on accroche un clavier via un des ports USB/host et puis on alimente via la prise micro USB/device. Et puis magie! Ça marche. La séquence de boot de linux s’affiche à l’écran.

Le menu de base

Le boot terminé, vient ensuite un outil de configuration, raspi-config avec des menus genre ncurses. Cela permet de dégrossir un peu la configuration (nom d’hôte, accès ssh, etc). Un tutoriel plus détaillé est disponible ici.

Photo d menu raspi-config
Le premier menu de raspi-config

Le menu de configuration permet d’agrandir la taille de la partition sur la carte SD. Lors de la copie de l’image, elle a été créé à la taille de cette dernière (~2 GO). C’est d’ailleurs la première option et c’est conseillé de le faire tout de suite.

Après avoir changé son password, on peut passer directement  menu avancé (Advanced Options) ou raffiner encore certains paramètres.

Pour l’internalisation (changement de configuration du clavier par exemple), il y a une entrée dans le menu de base.On peut aussi choisir le mode par défaut : desktop avec serveur X, mode console ou mode Scratch, un logiciel d’apprentissage de la programmation destiné aux enfants. Pour mes besoins, je reste en mode console, mais pour une box multimédia, on peut imaginer un mode desktop, avec xforwarding ou directement branché sur une télé/un moniteur via HDMI.

Les options avancées

Le menu avancé permet notamment de changer le  hostname, d’activer le daemon sshd et de charger les modules SPI.

Photo des options avancées du menu raspi-config
Le menu avancé permet notamment de changer le hostname, d’activer le daemon sshd et de charger les modules SPI.

Par défaut, le hostname est raspberrypi. Comme la bête est destinée à capter les signaux émis par mes capteurs météo, je lui ai donné un nom d’hôte approprié

Photo du menu pour changer le hostnam
Par défaut, le hostname est raspberrypi. J’en ai choisi un dans l’esprit de la tâche à effecteur : écouter des ondes radios…

Une fois la configuration terminée, on peut sortir de  raspi-config et profiter de sa toute nouvelle Debian.

20140130_231753

Mais puisque le sshd est lancé, on peut rapidement libérer l’écran 23″ et récupérer son clavier pour passer en mode distant…

sshpinsa
La connexion distance est tout de même plus pratique…

La connexion réseau se fait par le connecteur RJ-45, le temps de configurer le WI-FI. Le dongle Edimax est immédiatement reconnu et fonctionnel.

Résultat de ifconfig
Résultat de ifconfig « out of the box » avec le dongle Edimax EW-7811Un.

Pour configurer le WI-FI, ce lien peut être utile.

En résumé, il faut:

sudo iwlist wlan0 scan | grep ESSID

pour récupérer les noms de réseaux (SSID) disponibles et ajouter les lignes suivantes au fichier /etc/wpa_supplicant/wpa_supplicant.conf.

network={
        ssid="YourSSID"
        psk="password"
        key_mgmt=WPA-PSK
}

Puis relancez votre interface

pi@nsa ~ $ sudo ifdown wlan0
pi@nsa ~ $ sudo ifup wlan0
pi@nsa ~ $ ifconfig

Vous devriez maintenant avoir une adresse ip sur wlan0

Output de ifconfig après la configuration du WI-FI
Nous avons maintenant une adresse IP sur wlan0 (donc du WI-FI)

Ne pas oublier de faire un petit détour par son serveur DHCP pour attribuer un adresse statique (ça simplifie les connexions distantes via ssh) et de créer sa clef privée puis d’échanger sa clef publique avec ses autres points d’accès ssh.

On peut maintenant débrancher le câble sur le connecteur RJ-45 et puis passer à la suite. Mais ce sera pour une autre fois.

Raspberry Pi dans son boîtier, avec plusieurs connecteurs utilisés.
Le Raspberry Pi en action. On y voit: le câble HDMI, un câble RJ-45, un câble USB pour le clavier, le dongle WI-FI juste au dessus. L’OS est sur la carte SD à droite, à côté de l’alimentation via microUSB.

Chronomètre basique

On a souvent besoin d’un chronomètre multiplateforme. Celle-ci est 100% inline et ne dépend que de ctime (aka time.h). Un simple #include suffit à l’utiliser un peu partout. La classe étant basée sur clock(), la précision n’est pas garantie. Mais c’est souvent amplement suffisant.

Le fichier est disponible ici: chrono.h

#ifndef __CHRONO_H__
#define __CHRONO_H__

#include <ctime>

/**
 * \namespace	Chrono 
 *
 * \brief	A small set of utilities encapsulating timing functions 
**/
namespace Chrono 
{

/**
* \class	Stopwatch
*
* \brief	A stopwatch
*
* \details	Allows to create a stopwatch, start, stop and getting time in various formats.
**/
class Stopwatch
{
public:
 /**
 * \fn	Stopwatch::Stopwatch();
 *
 * \brief	Default constructor. 
 *
**/
inline
Stopwatch();

 /**
 * \fn	void Stopwatch::Start();
 *
 * \brief	Starts the time counter. 
 *
**/
inline
void Start();

  /**
 * \fn	void Stopwatch::Stop();
 *
 * \brief	Stops the time counter. 
 *
**/
inline
void Stop();

  /**
 * \fn	void Stopwatch::Reset();
 *
 * \brief	Resets the time counter to 0 sec.
 *
**/
inline
void Reset();

  /**
 * \fn	double  Stopwatch::GetTimeInMilliseconds();
 *
 * \brief	Gets the time in milliseconds. 
 *
 * \return	The time in milliseconds. 
 *
**/
inline
double  GetTimeInMilliseconds();

 /**
 * \fn	double Stopwatch::GetTimeInSeconds();
 *
 * \brief	Gets the time in seconds. 
 *
 * \return	The time in seconds. 
 *
**/
inline
double  GetTimeInSeconds();

  /**
 * \fn	double Stopwatch::GetTimeInMinutes();
 *
 * \brief	Gets the time in minutes. 
 *
 * \return	The time in minutes. 
 *
**/
inline
double  GetTimeInMinutes();

  /**
 * \fn	double Stopwatch::GetTimeInHours();
 *
 * \brief	Gets the time in hours. 
 *
 * \return	The time in hours. 
 *
**/
inline
double  GetTimeInHours();

  /**
 * \fn	void Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);
 *
 * \brief	Gets a time in a formated way
 *
 * \param [in,out]	aHours			a in hours. 
 * \param [in,out]	aMinutes		a in minutes. 
 * \param [in,out]	aSeconds		a in seconds. 
 * \param [in,out]	aMilliseconds	a in milliseconds. 
 *
**/

inline
void    GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);

private :
  unsigned int mStart;
  unsigned int mAccumulator;
  bool mStopped;
  };
}

inline
Chrono::Stopwatch::Stopwatch() : mAccumulator(0), mStopped(true)
{
}

inline
void Chrono::Stopwatch::Start()
{
  if(!mStopped)
   return;

  mStart = clock() - mAccumulator;
 mStopped = false;
}

inline
void Chrono::Stopwatch::Stop()
{
  if(mStopped)
   return;

  mAccumulator = clock() - mStart;
  mStopped = true;
}

inline
void Chrono::Stopwatch::Reset()
{
  Stop();
  mAccumulator = 0;
}

inline
double Chrono::Stopwatch::GetTimeInMilliseconds()
{
  return GetTimeInSeconds() * 1000.0;
}

inline
double Chrono::Stopwatch::GetTimeInSeconds()
{
  unsigned int lTime;
  if(mStopped)
   lTime = mAccumulator;
  else
   lTime = clock() - mStart;

  return lTime / (double)CLOCKS_PER_SEC;
}

inline
double Chrono::Stopwatch::GetTimeInMinutes()
{
  return GetTimeInSeconds() / 60.0;
}

inline
double Chrono::Stopwatch::GetTimeInHours()
{
  return GetTimeInSeconds() / 3600.0;
}

inline
void Chrono::Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds)
{
  double lRemainder = GetTimeInSeconds();

  aHours = (int)(lRemainder / 3600.0);
  lRemainder -= aHours;

  aMinutes = (int)(lRemainder / 60.0);
  lRemainder -= aMinutes;

  aSeconds = (int)lRemainder;
  lRemainder -= aSeconds;

  aMilliseconds = (int)lRemainder;
}

#endif // __CHRONO_H__
Contenu du fichier chrono.cpp

Écart type en une passe

On a souvent besoin de calculer quelques statistiques sur un ensemble de données. Si calculer la moyenne en une passe est trivial, le calcul de l’écart type demande un peu d’attention. Ci-dessous, une solution que je poste comme pense-bête.

Le snippet calcule aussi les valeurs min et max.

Code snippet :

std::vector<int> vec;   // Container with values
uint64_t count  = 0 ;     
uint64_t accu   = 0 ;     
uint64_t accu2  = 0 ;
uint64_t min    = -1;
uint64_t max    = 0 ;

for_each(begin(vec), end(vec) [&](int x)
{
    accu += x;
    accu2 +=  x * x;
    min = (std::min)(min, x);
    max = (std::max)(max, x);
    ++count;
});

float average = accu/float(count);
float stdev = sqrt(accu2*count - accu*accu)/count;
Écart type en une passe

First things first

Avant toutes choses, il faut passer à la caisse histoire d’agglutiner quelques accessoires.

Le Raspberry Pi et quelques accessoires

Capture écran de la commande passée pour le RPi.
Capture écran de la commande passée pour le RPi.

Liste de matériel:

  • 1x boîtier (plastique transparent). Faire attention, certains boîtiers ne donnent pas accès aux pins GPIO une fois fermés.
  • 2x Carte SD 8 GO. J’ai pris 2 SD Card parce que j’imagine que c’est plus souple pour expérimenter différents OS. On garde un OS plutôt stable et on fait des bêtises sur la seconde carte… Enfin on verra.
  • 2x dongles WI-FI. Pourquoi deux dongles ? Parce qu’à terme, le Raspberry Pi ira dans le cabanon du jardin (dossier arrosage, à venir dans un hypothétique futur ultérieur). Et le second dongle, c’est pour tester sur le Lego Mindstorms EV3 (dossier Lego, à venir dans un futur tout aussi hypothétique et tout aussi ultérieur que le précédent). Les dongles WI-FI Edimax sont tout petits et sont compatibles avec les Lego Mindstorms.  doivent pouvoir fonctionner avec les Lego Mindstorms moyennant un peu de configuration. Se trouvent pour moins de 10€ chez votre marchand de dongles favori.

facture : environ 75€.

Le module RF 433 MHz

Pour le module de réception radio, j’ai retenu le module QAM-RX1-433, essentiellement pour les raisons invoquées ici. Amazon.fr ne vendant pas de module  RF 433 MHz (ni trop de pièces d’électronique en général), je me suis tourné vers Digi-Key.  Le module y est tout à fait abordable (~5€). Mais attention, il faudra ajouter 18€ de livraison si la commande ne dépasse pas un certain seuil. Une recherche sur eBay peut permettre de trouver le même produit avec des frais de livraisons considérablement moins élevés.

MOD RCVR AM SUPER HETERDYNE SMT
Commande du module RF QAM-RX1-433

 

Il ne reste plus qu’à attendre le facteur…

Objectif Bidouille #1

Depuis un certain temps, j’ai agrémenté mon jardin d’une station station météo WMR86 faite par Oregon Scientific. La station possède plusieurs capteurs extérieurs qui envoient leurs données via un signal radio à la station de base (qui elle est dans le salon).

  • Une sonde Thermo Hygromètre – THGN800
  • Un Anémomètre/ Girouette – WGR800
  • Un Pluviomètre – PCR800

Regarder ces informations sur l’écran LCD de la station de base est certes amusant, mais stocker et exploiter les données me semble beaucoup plus intéressant.

Oregon Scientific propose bien des modèles avec options WI-FI, mais l’option n’est pas disponible sur le modèle dont je dispose.

Après un peu de recherches, il m’a semblé que j’avais enfin un projet pour un Raspberry Pi… De plus, Ce lien semble montrer que le décodage de certains capteurs est possible.

En résumé il faut :

  • Un récepteur RF 433MHz pour intercepter les signaux des capteurs extérieurs ;
  • Un Raspberry Pi ;
  • Un peu de temps et de patience pour décoder les trames des capteurs.