mardi 30 octobre 2007

Compressons du XML dans la joie et la bonne humeur

Notre bande passante étant limitée, l'efficacité des communications est primordiale à une bonne montée en charge du serveur. Cependant, nous avons choisi pour des raisons de simplicité de coder nos communications en XML, qui est un format plutôt verbeux. C'est là que la magie de la compression se met en place!

L'on pourrait en théorie simplement compresser chaque message XML vers du binaire, et envoyer directement le binaire vers l'autre côté. Cependant, cette solution présente le désavantage de nécessiter un changement complet au niveau de la couche communication: il faut par exemple envoyer un en-tête avec la taille du paquet, et il est peu commode d'envoyer sur un même canal du xml compressé et non compressé.

La solution standard est de mettre le xml compressé à l'intérieur d'un autre message xml. Par exemple: "<adH><auth><login>mon login</login><password>mon password</password></auth></adh>" compressé pourra ressembler à ceci: "<adh>s0lM8bCzSSwtybCzyclPz8yzy83PUwCzbPQhA
jYFicXF5flFKWApGMdGHy5sow/Rr5+YkmEHAA</adh>"

Pour rester dans la norme, il est important que le message compressé soit composé de caractères ASCII, ce dont se moquent éperdument la plupart des systèmes de compression (au hasard, l'excellent zlib). Là encore, la solution standard est d'encoder le binaire en base 64, comme on le ferait pour un fichier attaché dans un e-mail. L'encodage en base 64 contrecarre malheureusement un peu la compression, puisqu'un message encodé prendra environ 4/3 de la taille de l'original, mais zlib derrière est très performant, ce qui permet de faire de très bons gains de bande passante quand les messages dépassent une certaine taille. Pour les messages plus petits, comme par exemple le message de login donné plus haut en exemple, le généré, comme vous pouvez le voir, est plus grand que le message non compressé. Dans ce cas, puisqu'il est si facile d'envoyer du xml compressé ou non, l'on gardera le message tel quel.



Le graphe suivant a été réalisé en compressant via zlib puis encodage base 64 un message XML de test, et en comparant la taille du message compressé à celle du message original. L'on voit bien que le taux devient intéressant (inférieur à 1) à partir de 200 octets. C'est probablement dans cette zone qu'il faut définir le seuil à partir duquel l'on compressera la trame.

Il est également intéressant de noter à quel point la compression est efficace pour des fichiers plus gros: une trame de 1500 octets sera compressée à 358 octets!

lundi 29 octobre 2007

Mlxsd : Second Generation

Eh bien, ce fut un dimanche productif. Le support pour les choix est implémenté via des constructeurs de types et des types sommes, ce qui est probablement la manière la plus propre et la plus efficace de gérer la chose (les implémentations C++ utilisent généralement d'horribles isPresent(), ou renvoient des pointeurs pouvant être nuls, vive le typage fort!).

L'implémentation en elle même a été plutôt facile, puisqu'il ne s'agissait que d'un ajout. Le code à modifier était donc très réduit. Mais c'est maintenant que tout se gâte, avec le support des cardinaux. Ce sera beaucoup plus sanglant, et c'est malheureusement nécessaire, beaucoup de messages ayant besoin de contenir des listes. L'implémentation en sera également moins efficace, puisqu'il faudra lire les éléments les uns après les autres et les comparer au modèle, plutôt que de faire du pattern matching sur toute la structure.

En guise de simplification, j'ai déjà l'intention de ne supporter que 3 cas: le cas normal (un seul élément), le cas optionnel (zéro ou un élement), et le cas de liste (de 0 à un nombre non déterminé d'éléments). Tous les autres cas (par exemple, 3 éléments exactement, ou au moins 7 éléments) seront assimilés à une liste. De toutes façons, s'il y avait vérification à faire, elle serait au niveau de l'analyseur xml, contre le schéma (et xml-light n'a pas le support des schémas, donc pas de remords à avoir).

Si cette étape est complétée en temps et en heure, je pourrai enfin m'attaquer au système de personnages!

dimanche 28 octobre 2007

Mlxsd : First Generation

Eh oui, la première génération complète de ma spécification XSD restreinte a vu le jour! Voilà un exemple simple de xsd, et du code ocaml généré (bon, d'accord, j'avoue, j'ai indenté à la main le code généré pour faciliter la lisibilité, mais bon, ça ne va pas changer à la compilation!):

simple.xsd


<?xml version="1.0"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">

<xs:complexType name="v_t">
<xs:sequence>
<xs:element name="x" type="xs:integer"/>
<xs:element name="y" type="xs:integer"/>
<xs:element name="z" type="xs:integer"/>
</xs:sequence>
</xs:complexType>

<xs:element name="v" type="v_t"/>

</xs:schema>


simple.ml

module V_t =
struct

type t =
{
x: int;
y: int;
z: int
}

let from_xml xml =
match xml with
[Xml.Element ("x", [], [Xml.PCData x]);
Xml.Element ("y", [], [Xml.PCData y]);
Xml.Element ("z", [], [Xml.PCData z])] ->
{x = int_of_string x;
y = int_of_string y;
z = int_of_string z}
| _ -> raise Not_found

let to_xml t =
[Xml.Element ("x", [], [Xml.PCData (string_of_int t.x)]);
Xml.Element ("y", [], [Xml.PCData (string_of_int t.y)]);
Xml.Element ("z", [], [Xml.PCData (string_of_int t.z)])]

end


type v = { v : V_t.t }

let v_from_xml xml =
match xml with
Xml.Element ("v", [], v) -> { v = V_t.from_xml v }
| _ -> raise Not_found

let v_to_xml t =
Xml.Element ("v", [], V_t.to_xml t.v)


Tout cela suivi bien entendu du petit exemple d'utilisation:


# #load "xml-light.cma";;
# #load "simple.cmo";;

# Simple.v_to_xml;;
- : Simple.v -> Xml.xml = <fun>
# Simple.v_from_xml;;
- : Xml.xml -> Simple.v = <fun>

# let input = "<v><x>9</x><y>8</y><z>7</z></v>";;
val input : string = "<v><x>9</x><y>8</y><z>7</z></v>"

# let xml = Xml.parse_string input;;
val xml : Xml.xml =
Xml.Element
("v", [],
[Xml.Element ("x", [], [Xml.PCData "9"]);
Xml.Element ("y", [], [Xml.PCData "8"]);
Xml.Element ("z", [], [Xml.PCData "7"])])

# let s = Simple.v_from_xml xml;;
val s : Simple.v =
{Simple.v = {Simple.V_t.x = 9; Simple.V_t.y = 8; Simple.V_t.z = 7}}

# Simple.v_to_xml s;;
- : Xml.xml =
Xml.Element
("v", [],
[Xml.Element ("x", [], [Xml.PCData "9"]);
Xml.Element ("y", [], [Xml.PCData "8"]);
Xml.Element ("z", [], [Xml.PCData "7"])])

# Xml.to_string (Simple.v_to_xml s);;
- : string = "<v><x>9</x><y>8</y><z>7</z></v>"


C'est maintenant que les difficultés vont commencer: le support des choix, et des cardinaux!

samedi 27 octobre 2007

Mise en abîme

En plus bien sûr des résultats espérés (c'est à dire au final un AdH de meilleure qualité, et plus rapidement sur nos disques durs), le développement de ce petit générateur xsd => xml est très intéressant à coder. Avoir non plus à réfléchir à "Qu'est-ce que ce code va faire?", mais "Qu'est-ce que ce code généré par ce code va faire?" est un exercice qui titille gentiment les neurones.

Pour l'instant, les capacités du programme sont réduites au strict minimum: pas de types imbriqués, pas de cardinaux (tous les éléments sont présent exactement une fois), pas de choix... Du fait, ces restrictions alègent beaucoup le code: le générateur est maintenant aux trois-quarts complet (il ne rèste que l'écriture du xml à partir des types ocaml), avec une taille d'environ 200 lignes de code (le double en comptant les tests unitaires).

L'ajout des choix d'abord, puis des cardinaux, va bien sûr alourdir la chose. Mais pour un début, c'est un début.

lundi 22 octobre 2007

Un générateur de XML en Ocaml

Il y a longtemps que ce genre d'outils existe en C++: Codesynthesis XSD, ou encore Roguewave Leif vont lire un schéma XML (format xsd) et générer des classes C++ correspondant aux structures définies.

Je n'ai pas trouvé d'outil équivalent en ocaml (du moins, pas que j'aie compris), et le code du serveur d'AdH était donc parsemé de bouts de code utilisant xml-light pour passer du xml aux types internes et inversement. Aujourd'hui, j'en ai donc eu assez, et je me lance dans l'aventure de l'écriture d'un mini-générateur xsd ocaml basé sur xml-light. Je n'ai aucune intention de supporter l'ensemble de la spécification xsd, et m'en tiendrai donc à ce dont les fichiers xsd d'AdH nécessitent. Pour l'instant, j'ai les types de base et quelques tests unitaires (le code est visible ici). C'est un peu dommage d'avoir à s'arrêter en milieu de développement pour faire ce genre d'outil, mais si tout fonctionne comme prévu, c'est beaucoup de temps gagné à la clé, pour la génération et la lecture de xml, bien sûr, mais également par la réduction du nombre d'erreurs de communication possibles, puisque à la fois le code C++ et le code Ocaml seront dérivés (correctement, on l'espère) des mêmes schémas.

jeudi 18 octobre 2007

De l'importance du système de suivi de bug

S'il y a quelque chose de vraiment fondamental que je n'ai compris qu'après avoir commencé à bosser, c'est bien que l'on ne peut travailler à plusieurs (et même tout seul) correctement sur un projet qu'avec un système de suivi de bugs. Le système en lui même est peu important, spécialement pour des projets relativement simples avec des petites équipes. Même celui de SourceForge, pourtant vraiment basique, est suffisant. Et il existe pléthore de systèmes propriétaires et libres, parmi lesquels l'on peut citer bugzilla.

Ensuite, il suffit de mettre en pratique les deux principes suivants:
- Un bug est dans son acception large n'importe quel changement qui devra être effectué dans l'application. Un défaut, une nouvelle fonctionnalité, un changement, une nouvelle icône... sont des bugs (la plupart des systèmes de suivi permettent de classer les bugs par type).
- Un bug qui n'est pas dans le système n'existe pas

Ensuite il faut qu'à chaque fois que l'on découvre un bug ou que l'on veut ajouter une fonctionnalité entrer le rapport de bug dans le système, le classer dans une release, et l'assigner à quelqu'un. Les discussions relatives au problème doivent être faites à cet endroit. Ainsi, l'on a très facilement une vue d'ensemble de ce qu'il faut faire pour la prochaine release ou celle d'après, et pour chaque bug un historique du problème et des différentes idées envisagées pour le résoudre.

Enfin, lorsqu'un nouveau venu débarque dans le projet, inutile de se faire des noeuds au cerveau pour lui trouver du travail à faire: "Va dans le système de suivi de bugs, et corrige les bugs les plus faciles!".

lundi 8 octobre 2007

Des joies d'être un amateur

Pourquoi, mais pourquoi est-ce que tant de bases de données sont aussi peu adaptées au C++?

Les développeurs de bases de données ne sont pas bêtes: ils se concentrent sur leur segment de marché principal, c'est à dire l'utilisation des bases de données pour le web. L'on a ainsi des frameworks pas mauvais du tout en php, asp, et autres.

Mais côté serveur, et principalement côté C++, c'est particulièrement galère (peut-être que Java fait mieux?). SqlServer, par exemple. Déjà, il faut faire un choix entre OleDb et ODBC. Les différences ne sont pas claires, mais il semblerait que les meilleures performances puissent être obtenues avec le driver natif OleDb. Allons donc pour OleDb, donc!

Et c'est là que tout se corse. Microsoft a bien essayé de faire une bibliothèque vaguement plus haut niveau, la OleDb Templates Library, mais c'est la croix et la bannière d'essayer de faire quelque chose de vaguement hors du commun, par exemple faire du bulk copy (transfert très performant d'un gros paquet de données vers la base, sans passer par une requête SQL). Pour ce genre de tâches, il faut retourner sur les bons vieux appels COM mal documentés. Il m'a fallu par exemple une demie-journée pour me rendre compte que j'utilisais le driver générique OleDb et pas le natif, et que c'est cela qui m'empêchait d'utiliser le bulk copy. Et de toutes façons, en plus d'être mal documentée, certains choix techniques sont tellement étranges qu'il faut parfois tout essayer au hasard, jusqu'à ce que cela marche (ou pas). Par exemple, en fonction des templates choisis, certaines requêtes SQL vont échouer, et l'utilisation des tables temporaires est complexe. Je ne parle même pas des reconnexions, des bindings avec les données, et des procédures stockées qui ne renvoient que l'erreur de la première sous-procédure (si ça foire ensuite, tant pis pour vous!). Et tout ça, parce que le management, dans son extrême sagesse, nous oblige à utiliser une technologie manifestement pas adaptée à nos besoins...

Heureusement, pour AdH, nous avons pu choisir notre base de données. Nous avons choisi Postgres, qui a de plus l'avantage d'avoir des bindings de toute première qualité, et je n'ai pas regretté notre décision une seule seconde!

mercredi 3 octobre 2007

Une caractéristique des mmorpgs, et probablement une bonne partie de leur attrait pour nous autres développeurs, est l'étendue des domaines qu'il est nécéssaire de maîtriser pour les concevoir. Bases de données, architectures n-tiers et/ou distribuées, réseaux, haute performance, robustesse, graphismes, et, entre autres, interface utilisateur.

Dans beaucoup de jeux amateurs, l'interface utilisateur est la dernière roue du carosse, et AdH ne fait pas exception: il est tellement plus simple de passer ses identifiants de connection par la ligne de commande! Cependant, arrive un moment où il n'est plus possible de dire au joueur d'apprendre par coeur toutes les commandes clavier, façon "Aller regarder votre inventaire dans la console, lorsque vous appuyez sur i". Il faut donc faire quelque chose, et c'est là que ça se corse.

Nous avons passé beaucoup de temps à essayer les diverses solutions d'affichage de GUI dans AdH, et n'avons rien trouvé de très probant. Il y a bien ceGUI, mais les contrôles sont limités, l'ensemble paraît plutôt lent, et l'intégration à Open Scene Graph plutôt compliquée. Sans compter la tonne de fichiers de skin et autres qu'il faut placer au bon endroit, sous peine d'être noyé dans un flot de messages cryptiques.

Nous avons également contemplé la possibilité de créer nous même notre GUI. Mais au vu des interactions complexes dont nous avons besoin (inventaires, commerce, chat, configuration, et j'en passe), un tel développement aurait été un projet à plein temps pour les quelques années qui viennent. En cherchant un peu, l'on découvre tonnes de projets inaboutis de GUIs pour SDL et autres: d'autres ont essayé et on failli avant nous.

Restait la dernière solution: utiliser une GUI qui ne soit pas intégrée à notre environnement 3D, c'est à dire par exemple GTK, Win32, ou plus particulièrement et pour être portable, QT ou wxWidgets.



Je connaissais déjà wxWidgets et avais été favorablement impressionné par ses qualités. Certes, la bibliothèque gagnerait à être plus intégrée à la STL et à utiliser du code plus idiomatique, mais l'on arrive à un résultat de qualité sans trop se battre (la documentation, plutôt complète, aide beaucoup).



Comme vous pouvez le voir sur les captures d'écran, l'intégration à wxWidgets donne à l'application un cachet "éditeur de terrain", qui n'est pas forcément le mieux pour l'immersion dans le jeu. Les contrôles wxWidgets ne sont pas skinnables, et il faudra donc compter sur le thème du gestionnaire de fenêtres pour rendre l'ensemble un peu plus symathique (tiens, c'est une idée, ça! Un thème Windows / Gnome / KDE / autres pour AdH!). Mais le plus important, c'est que nous soyons maintenant efficaces dans l'élaboration d'une bonne GUI qui donne envie de jouer!

mardi 2 octobre 2007

Types fantômes et typage fort

La plupart des programmes un peu gros font une utilisation massive d'identifiants pour référencer des entités. C'est particulièrement le cas pour un MMORPG: chaque joueur a un identifiant, chaque personnage, chaque monstre, chaque type d'objet, chaque objet, peut-être chaque ligne de dialogue, et bien d'autres encores, sont référencés via des nombres, qui sont utilisés en interne, dans la base de données, et dans les messages envoyés au client. L'on aura par exemple un message du type "Le personnage 23576 appartenant au joueur 17980 a pris l'objet 7894 de type 45 et l'a mis à la position 17 du sac 3 de son inventaire".

La multiplication des identifiants augmente les risques de les confondre les uns avec les autres, ce qui peut engendrer des bugs particulièrement retors. Une solution assez standard dans l'industrie consiste donc à "habiller" notre entier avec une information supplémentaire, le discriminant, qui n'est là que pour s'assurer que l'on ne mélange pas les tomates avec les carrottes.

Dans un language statique orienté objet, l'on va par exemple créer une classe par type d'identifiant, en surchargeant si le language l'autorise certains opérateurs, pour l'assurer que toute comparaison / tout assignement entre des types différents va engendrer une erreur à la compilation. L'on pourra même en C++ concevoir une classe template qui prendra le type discriminant comme paramètre. L'on pourrait alors utiliser la classe comme suit:


class DiscriminantJoueur;
Class DiscriminantPersonnage;

typedef TypageFort JoueurIdT;
typedef TypageFort PersonnageIdT;

JoueurIdT joueur1(5);
JoueurIdT joueur2(6);
JoueurIdT joueur3(5);

PersonnageIdT personnage1(5);

assert(joueur1 == joueur3);
assert(joueur1 =! joueur2);
joueur1 == personnage1; // Erreur de compilation! Un joueur n'est pas un personnage

std::set joueurSet;
joueurSet.insert(joueur1);
joueurSet.insert(joueur2);
joueurSet.insert(personnage1); // Erreur de compilation!


Pour ceux que cela intéresse, AdH propose une implémentation en C++ d'une telle classe. Vous pouvez voir le code en ligne ici.

Les types fantômes en Ocaml permettent de fournir la même sécurité très simplement. Voici une implémentation d'un module permettant le typage fort d'entiers (Note: le code est complet, il est possible de directement copier/coller dans un top-level ocaml):


module T :
sig
type 'a t
val to_int : 'a t -> int
val from_int : int -> 'a t
end
=
struct
type 'a t = int
let to_int e = e
let from_int e = e
end;;


Le type fantôme est cet étrange type 'a t, qui a une signature dépendante d'un type quelconque 'a, mais qui en réalité est un simple entier. Passer du type 'a t à un entier et inversement est donc simplement l'identité. Cependant, ce 'a sera le discriminant de notre type. Voici un exemple d'utilisation:


let joueur1 : [`JOUEURID] T.t = T.from_int 5;;
let personnage1 : [`PERSONNAGEID] T.t = T.from_int 5;;
let personnage2 : [`PERSONNAGEID] T.t = T.from_int 6;;
let personnage3 : [`PERSONNAGEID] T.t = T.from_int 5;;

personnage1 = personnage2;;
- : bool = false
personnage1 = personnage3;;
- : bool = true

personnage1 = joueur1;;
This expression has type [ `PERSONNAGEID] T.t
but is here used with type [ `JOUEURID] T.t
These two variant types have no intersection


Bien sûr, l'ajout à une liste (ou toute autre structure de données) fonctionnera de la même manière:


let persoliste = [personnage1; personnage2];;
val persoliste : [ `PERSONNAGEID ] T.t list = [; ]
let persoliste = joueur1::persoliste;;
This expression has type [ `PERSONNAGEID ] T.t list
but is here used with type [ `JOUEURID ] T.t list
These two variant types have no intersection


En conclusion, les types forts, c'est bon, mangez en! En ocaml, de préférence :)

lundi 1 octobre 2007

Ocaml

Probablement la particularité technique principale de l'Aube des Héros, comparé à d'autres mmorpgs, est l'utilisation du language ocaml du côté serveur.

Au final, il y a assez peu d'experimentation (publique du moins) dans l'utilisation de languages un peu ésotériques , et encore moins dans les mmo mainstream. Notons toutefois Vendetta Online, qui utilise Lisp et Erlang. L'architecture distribuée d'Erlang semble effectivement particulièrement adaptée aux besoins de montée en charge d'applications de type mmo. De plus, la plupart des mmorpgs (voire tous les mmorpgs serieux?) utilisent des languages de haut niveau (lua, python, perl et une myriade de languages internes) pour coder la logique, comme par exemple l'intelligence artificielle, les interractions complexes avec l'environnement ou le système d'artisanat, en se basant sur des composants écrits dans des languages de plus bas niveau mais plus efficaces (dans la grande majorité du C++).

Pourquoi avoir choisi ocaml, alors?

Ocaml a beaucoup de qualités, les plus importantes à mes yeux étant l'expressivité, la sûreté du language, les bibliothèques disponibles, et enfin, ce qui ne gache rien, des performances tout à fait raisonnables.

Les trois premiers points sont liés, puisqu'ils influent directement sur la vitesse à laquelle il va être possible de fournir des fonctionnalités. Et pour nous autres amateurs qui n'ont pas d'équipes de 120 programmeurs travaillant 12 heures par jour, la vitesse de développement est fondamentale.

Ayant programmé plusieurs petites applications avec ocaml, j'étais curieux de voir comment le language se comporterait face à un programme plus gros, accédant à une base de données, et servant des données à de multiples clients connectés simultanément.

Avec la sortie d'Ajax, je peux le confirmer: ocaml pour le serveur valait vraiment l'effort fourni. Le serveur s'est avéré avoir au final très peu de bugs, et les quelques uns qui ont surgi ont été faciles à résoudre. L'avenir dira si l'architecture du serveur est suffisemment extensible, mais pour l'instant le language a beaucoup aidé à maintenir un ensemble cohérent et propre.

Dans un prochain post, je passerai en revue quelques constructions du language qui ont été particulièrement importantes et utiles lors du développement du serveur pour la version Ajax.