Projet GraphGame

Le projet GraphGame est un jeu, qui se joue seul. L'objectif du jeu est de supprimer les noeuds d'un graphe, jusqu'à ce qu'il n'en reste plus rien, tout en minimisant un score.

Pour supprimer un noeud du graphe, on clique simplement dessus. Ceci a pour effet de supprimer le noeud lui même, mais aussi tous ses voisins. Au score est alors ajoutée la valeur du noeud cliqué.

Lorsque le graphe a complètement disparu, le score est donc la somme des valeurs de tous les noeuds que l'on a cliqué. Ce score est à minimiser. Parce qu'il est humain de vouloir toujours plus… le score obtenu en faisant la somme des valeurs des noeuds est transformé en 2000 / (score + 1). Ce nouveau score est donc à maximiser.

Un serveur est installé à cette adresse : [[http://lsignac.pythonanywhere.com/]]. Un compte invité et une clé invité ont été créées (on les voit au début du fichier client_graphe.py).

Pour jouer, il suffit de lancer le client (programme python) et de cliquer sur “Nouvelle partie”. Un des graphe apparaîtra alors :

Les nœuds peuvent être déplacés avec le bouton gauche de la souris (drag/drop). Pour supprimer un nœud, il faut faire un clic droit dessus.

Éventuellement, le serveur peut proposer une disposition particulière des nœuds. S'il ne le fait pas ce sera au client de le faire : si le programme neato (logiciel Graphviz) est installé sur le client, il est utilisé. Sinon, un plongement moins lisible sera utilisé, comme :

Dans tous les cas, l'utilisateur peut déplacer les nœuds pour y voir plus clair.

Le projet se compose

1. d'un serveur Web (Python + Flask) qui peut :
   • servir quelques pages (consultation des graphes, des scores, création d'un compte, génération d'une clé pour le client…)
   • communiquer avec un client (API Rest)
2. d'un client (Tkinter) qui peut communiquer avec le serveur pour récupérer un graphe, puis le jeu se fait en local, et la partie est ensuite transmise au serveur qui la valide ou non, et enregistre le score.

Les fichiers utiles au serveur sont :

• bdd.py : gestion de la base de données SQLite (comptes, scores, clés, mais pas les graphes)
• graphe.py : module de manipulation des graphes (génération, accès aux voisins, aux arêtes, suppressions des noeuds, itérations sur le graphe etc..)
• int_graphe.py : quelques graphes particuliers préenregistrés
• server.py : Le serveur Web (utilise Flask) qu'on peut lancer localement avec python3 server.py
• server_api.py : La partie API Rest du serveur (ce qui est utilisé pour que l'application cliente communique
• server_common.py : fonctions utiles à la fois dans server.py et server_api.py
• templates/ : contient les templates html (Jinja2) pour les pages Web du serveur
• instance/ : contient la base de données SQLite
• static/ : est actuellement vide

Les fichiers utiles au client sont :

• graphe.py : module de manipulation des graphes (génération, accès aux voisins, aux arêtes, suppressions des noeuds, itérations sur le graphe etc..). C'est le même fichier que pour le serveur.
• client_graphe.py : le client Tkinter

Il est possible de travailler indépendamment sur plusieurs parties du projet, que j'espère assez bien organisé. Les choses les plus intéressantes à faire sont :

• développement d'un client (on utilisera alors le serveur déjà en ligne ou le serveur fourni en le lançant en local)
• développement du serveur
  • partie API pour fonctionner avec un client
  • partie pur Web pour présenter les scores, les différents graphes
• développement des outils sur les graphes
  • recherche de solutions optimales au problème
  • génération de graphes plus intéressants
  • calcul de plongements
• développement de la partie BDD

Il est aussi possible d'améliorer ce qui est fourni. Par exemple, le serveur (partie Web) pourrait proposer une visualisation des graphes. Le client pourrait permettre à l'utilisateur de choisir sur quel graphe il veut jouer (plutôt que d'en envoyer un au hasard).

La communication est réalisée au travers d'une API simple. Le client peut interroger le serveur ou lui envoyer des informations au travers de requêtes Web ordinaires (types GET). Le serveur répond en utilisant le format Json, facile à traiter par le client.

Toutes les requêtes ont la même forme :

http://adresse_serveur/commande/login/cle/parametres

où :

• commande est la commande à passer au serveur (get_game, post_game)
• login est le login utilisé par le client
• cle est une clé au format uuid que l'utilisateur a obtenu sur le site (et qui remplace le mot de passe pour la communication avec le serveur)
• parametres est présent pour certaines commandes

Il n'y a que quatre commandes.

• get_game (commande GET) renvoie au format json un graphe au hasard. Il n'y a pas de paramètre.
• post_game (commande POST) permet au client d'envoyer sa partie pour validation par le serveur. Il n'y a pas de paramètre dans l'url, mais des données (décrivant la partie) à passer en post.
• get_this_game (commande GET) renvoie au format json le graphe demandé en paramètre (non utilisé dans le client fourni, qui ne permet pas de choisir son graphe)

Il est facile de tester quelques requêtes, sans programmer, en utilisant juste un navigateur. Par exemple, en entrant l'URL :

http://localhost:5000/get_game/invite/06064a1f-e01e-4e0b-b0c0-e5541b74f45e

Si tout est correct (login, clé, adresse du serveur), on récupère ainsi un dictionnaire au format Json contenant 4 couples clé/valeur : graph, name, values et status.

{
"graph_edges": 
    [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], 
    ["C", "D"], ["C", "E"], ["D", "E"]],
"name": "gr_k5", 
"status": 1, 
"values": {"C": 7, "D": 8, "A": 5, "B": 6, "E": 9}, 
"positions": 
    {"C": [-0.07, -1.0], "D": [-0.515, 1.0], "A": [-1.0, -0.17], 
    "B": [1.0, -0.355], "E": [0.72, 0.875]}
}

La conversion du Json en dictionnaire est immédiate :

• graph_edges est une liste de couples décrivant les arêtes
• name est le nom du graphe
• status indique si la requête s'est bien déroulée (1 pour oui)
• values est la liste des valeurs associées aux noeuds.
• positions est un tableau associatif (dictionnaire) donnant pour chaque noeud, sa position (par un couple x,y de valeurs comprises entre -1 et 1.

Si la requête précédente peut être testée dans un navigateurs, il est facile également de la programmer en Python avec le module standard : urllib.request.urlopen ou avec le module request. Le résultat (Json) peut être converti en dictionnaire soit avec le module json, soit directement par request.

Cette commande permet à l'utilisateur d'envoyer sa partie au serveur, qui va la valider ou non et enregistrer son score. Pour décrire une partie, il suffit de donner, dans l'ordre la liste des noeuds supprimés en cliquant. Le serveur utilisera cette liste pour rejouer la partie, la vérifier (on ne peut pas supprimer un noeud qui n'eexiste plus par exemple, ni dire que la partie est finie s'il reste des noeud) et enregistrer le score.

Une requête POST (HTTP POST) permet, outre la consultation d'une URL, d'envoyer des données (le système est souvent utilisé dans les formulaires par exemple, et les données que vous entrez dans le formulaire (nom, adresse….) sont passées en post). Dans le cas de la commande post_game, il faut envoyer 2 paramètres :

• name, qui contiendra le nom du graphe (par ex 'graphe2'),
• game, qui contiendra une liste, au format Json des coups à jouer dans l'ordre, par exemple '[“I”, “F”, “O”, “E”, “C”, “K”]'

De même que pour get_game cette requête peut être réalisée en Python avec urllib.request.urlopen ou request (il est plus difficile de la tester dans un navigateur, mais il existe des modules pour Firefox ou Chromium qu permettent de choisir les données qu'on envoie en POST).

Voici un exemple de retour du serveur suite à un post_game:

  
  {'message': 'Solution valide : 62.500 pts. Vous avez déjà fait mieux', 'status': 1}

Pour toutes les commandes, le serveur renvoie un dictionnaire au format Json, dont une des clés est status. Si la valeur est 1, c'est que la commande s'est bien déroulée. Si la commande est 0, c'est que la commande a échoué et il y a généralement une clé message indiquant en clair la source du problème.

Outre la mise à disposition d'une API, le serveur Web permet de :

• créer de nouveaux comptes
• renouveler une clé associée à un compte
• consulter les graphes à disposition
• obtenir les meilleurs scores de chacun pour chaque graphe (la partie API doit à ce moment gérer l'enregistrement de ces données dans la base)

La réalisation de ces pages nécessite (sauf dans la consultation des graphes) d'utiliser une base de données (par exemple une base sqlite, très facile à gérer). Le schéma de la base utilisée est le suivant (on peut tout à fait en prendre un autre, il faut juste s'assurer que la partie API utilise le même) :

CREATE TABLE keys(login text primary key, key text);
CREATE TABLE scores(login text, graph_name text, score real, PRIMARY KEY(login, graph_name));
CREATE TABLE accounts(login text primary key, password text);

Nous avons donc 3 tables, keys, scores, et accounts.

• La table accounts contient 2 colonnes de texte : login (clé primaire contenant le login de l'utilisateur) et password contenant une version hachée (SHA256, avec salage, mais on peut changer) du mot de passe.
• La table keys contient 2 colonnes : login (clé primaire contenant le login de l'utilisateur), et key, contenant un uuid. Cet uuid est la clé qu'il faut rappeler dans les requêtes API. Utiliser une telle clé permet : de jouer avec le client sans divulguer son mot de passe (la clé, si elle est découverte, peut être changer facilement), et de «prêter» des parties, en donnant la clé à quelqu'un (il suffit ensuite de révoquer la clé pour révoquer l'accès). Toutefois, pour bien faire, la clé devrait être transmise autrement que dans l'URL des requêtes…
• la table scores contient 3 colonnes. login est le nom d'utilisateur, graph_name le nom du graphe, et score le score maximal obtenu sur ce graphe par l'utilisateur. La clé primaire est le couple login, graph_game, ce qui signifie qu'on enregistre qu'un seul score par utilisateur et par graphe.

Tout ce qui est relatif à la base de données est dans le module bdd.py. Cela signifie qu'aucun autre fichier ne fait de supposition sur la manière dont la base est organisée. Par exemple serveur_api, lorsqu'il soit mettre à jour un score, appelle bdd.set_score(login, graph_name, score).

Il est donc tout à fait possible de réécrire le module de bases de données, avec éventuellement une implémentation très différente, tant que l'interface est respectée, c'est à dire tant que les fonctions utilisées par les autres modules sont présentes et font leur travail. Ces fonctions sont :

* bdd.check_account(login, hashpassword) : vérifie un couple login/pass * bdd.set_score(login, name, res) : met à jour le score (mais uniquement s'il est supérieur au score déjà enregistré, notez bien que c'est le module bdd qui fait cette vérification) * bdd.get_key(login) : renvoie la clé de l'utilsateur (None si pas de clé) * bdd.set_new_key(login, key) : stocke une nouvelle clé * ''bdd.new_account(login, hashpass): '' crée un nouveau compte * bdd.get_scores_graph(name) renvoie la liste des scores pour un graphe particulier sous la forme : [('toto', 12), ('titi', 60)]

Notez que le hachage du mot de passe n'est **PAS FAIT** dans le module bdd, mais en l'occurrence dans le module server.py. De même le calcul de la clé n'est pas fait dans le module bdd. Du point de vie de bdd, n'importe quelle chaîne fait l'affaire. Le calcul de la clé (et donc le choix d'uuid est fait dans ''server_common''.

On pourra consulter le site Web en ligne (demandez l'URL et le mot de passe pour vous créer un compte) pour se faire une idée des fonctionnalités. Pour la mise en page, le site en question utilise Bootstrap.

Les modules sont documentés (pas très bien, mais j'espère suffisamment). La doc est dans le code, mais dans le cas où on essaie de re-développer le module, il sera plus intéressant de ne pas jeter un oeil au code en question. Voici les documentations de certains modules, sans le code :

• graphe
• bdd

L'image ci-dessous illustre les rapports entre les différents modules de la partie client. Elle peut vous aider à appréhender la partie client dans son ensemble: