mardi 30 juin 2009

Îles - Gestion du niveau de détail

C'était un peu confus dans ma tête, mais il me semblait bien que mon design séparant la description mathématique de mon île et la génération de la grille d'une résolution donnée allait beaucoup m'aider dans ma gestion du niveau de détails. Voilà le code: je génère une fois la description mathématique de mon île, créée à partir de la racine 37 (et placée à l'origine). Ensuite, j'utilise un osg::LOD auquel j'ajoute des osg::Drawable créés à partir de ma description de l'île et d'une résolution: 200, puis 100, puis 50, puis 20. Une fois toutes les grilles calculées, l'on peut se promener dans un monde qui va ajuster tout seul (à travers la magie d'OpenSceneGraph) le niveau de détail des îles.


IslandGenerator islandGenerator;
boost::shared_ptr t = islandGenerator.generateIsland(0, 0, 37);

osg::LOD * islandLod = new osg::LOD;

osg::Drawable * grid1 = createGrid(*t, 200, 1, 0.05, 20);
osg::Geode * geode1 = new osg::Geode;
geode1->addDrawable(grid1);
islandLod->addChild(geode1, 0, 500);

osg::Drawable * grid2 = createGrid(*t, 100, 1, 0.05, 20);
osg::Geode * geode2 = new osg::Geode;
geode2->addDrawable(grid2);
islandLod->addChild(geode2, 500, 1000);

osg::Drawable * grid3 = createGrid(*t, 50, 1, 0.05, 20);
osg::Geode * geode3 = new osg::Geode;
geode3->addDrawable(grid3);
islandLod->addChild(geode3, 1000, 2000);

osg::Drawable * grid4 = createGrid(*t, 20, 1, 0.05, 20);
osg::Geode * geode4 = new osg::Geode;
geode4->addDrawable(grid4);
islandLod->addChild(geode4, 2000, 10000);

lightsource->addChild(islandLod);


Voilà le résultat:



La transition entre 40000 polygones et 10000 polygones (regardez l'ombre du petit pic de droite)




La transition entre 10000 polygones et 2500 polygones (le petit pic de droite est sacrément diminué)




La transition entre 2500 polygones et 400 polygones (sacrément raboté!)


Bien sûr, j'ai fortement exagéré les niveaux de détail pour apercevoir la transition, mais en étant moins agressif, l'on peut obtenir une bonne réduction du niveau de détail sans que le passage d'un niveau à l'autre soit trop visible. Ainsi, il devient possible d'afficher des centaines d'îles simultanément!

lundi 29 juin 2009

Génération automatique de terrain - Des îles!

J'ai commencé à bidouiller la génération d'îles, et les résultats sont encourageants. J'ai ressorti du placard mon système de collines, en y ajoutant la génération des normales par calcul du gradient de mon exponentielle, ce qui devrait donner de meilleures ombres.

La génération se contente donc d'ajouter plusieurs collines en même temps, et est basée sur un unique nombre qui est la racine de mon générateur aléatoire. L'on donne son entier, et hop, l'archipel surgit des flots!

Un avantage supplémentaire est la séparation de la définition de l'île, comme étant une liste de collines, et de sa représentation graphique, qui est une grille. En faisant jouer la résolution, l'on peut très facilement créer des niveaux de détail différents, et les changer de manière dynamique, permettant d'afficher efficacement les îles lointaines, et de réserver les détails aux îles plus proches.

Voici quelques exemples d'îles générées:


L'île n°5. Les petites bosses correspondent aux toutes petites collines qui ajoutent au relief général.



L'île n°17. Remarquez le petit étang! Certaines collines sont générées inversées, ce qui peut créer des lacs.



L'île n°190. Vue de plus bas, pour le reflet dans la mer.



L'île n°2009. Sacrément biscornue!


Le relief n'est pas la seule chose à générer: je veux pouvoir créer des textures afin d'avoir des couleurs et des aspects différents selon les îles. Ensuite, il faudra ajouter quelques outils au client afin que le maître du jeu puisse créer une île à un endroit donné, juste à partir de son numéro. En essayant plusieurs numéros, il tombera bien sur une île qui lui plaît, laquelle sera alors ajoutée à la carte du monde au niveau du serveur, et envoyée chez tout le monde.

vendredi 26 juin 2009

AdH - rapport d'activité

Voici un extrait du rapport d'activité pour le CA de l'association Reves d'Autres Mondes.

Où en sommes-nous?

AdH est actuellement un client, un serveur et un lanceur, lesquels compilent et fonctionnent sous Windows et sous Linux, nonobstant quelques bugs graphiques dus aux différences entre les cartes au niveau des shaders.

Le lanceur est probablement la grande nouveauté par rapport aux moutures précédentes de l'authentification et de la mise à jour des ressources.
- Le lanceur s'occupe de la gestion des comptes: création d'un login, création d'un avatar
- Le lanceur vérifie la présence des ressources, et télécharge celles qui manquent. Grâce à ce mécanisme, il suffit de permettre aux joueurs de télécharger les deux exécutables (lanceur et client), de quelques mégaoctets, et de laisser le lanceur s'occuper de tout le reste. Le système de téléchargement de ressources est bête comme chou, puisqu'il ne s'agit que de copier les fichiers de ressources et un fichier de description des ressources sur un site Web.
- Le lanceur gère les serveurs multiples: il est possible de voir en même temps l'état (ping et nombre de joueurs) de tous les serveurs référencés d'AdH qui tournent, et de choisir celui sur lequel on veut aller.

Tel qu'il est, le lanceur est considéré "feature complete", et devrait très peu changer, à part peut-être pour la partie "création d'avatar".

Le client fonctionne raisonnablement bien, cependant qu'en termes d'interface il reste très limité. L'utilisation des shaders a permis une très bonne amélioration du rendu, notamment sur les effets d'océan, mais cela veut dire que la qualité de la carte graphique devient particulièrement importante pour avoir de bonnes performances. Il est possible de voir les autres joueurs évoluer dans le monde, avec, contrairement à Bérénice, le support de l'orientation. Les performances réseau sont plutôt bonnes, avec un cout de 5 kb/s par client qui se déplace.

Le serveur est robuste et sobre, sans aucun souci en vue pour la montée en charge, qui sera probablement limitée d'abord par la bande passante. La persistance est encore très limitée, et un redémarrage du serveur perdra les positions des joueurs (mais pas les comptes, qui sont sauvés à la création dans la base de données). A part gérer les conversations et les positions des joueurs, le serveur ne fait pas grand chose!

La prochaine étape

Tout d'abord, une release! Les ressources ont été ajoutées à aubedesheros.net, il va nous falloir remettre Lea sur pied, et nous pourrons sortir une version jouable permettant à tout un chacun de se connecter pour crapahuter dans le monde. Cela nous donnera une première idée des problèmes de compatibilité graphique et de performances.

A long terme

Le modèle basé sur des îles permet de beaucoup simplifier le système de terrain, notamment en permettant d'avoir un niveau de détail différent par île sans tomber dans les soucis de bordures de zones. Je suis en train de remettre en place un système de terrain procédural, avec multitexturing à base de shaders. Il semble hors de notre portée de développer un éditeur de monde, mais quelques fonctions "god-mode" dans le client devraient faire l'affaire.

Les gros morceaux à venir sont le système physique pour les déplacements, sur lequel on pourra ajouter un système basique de combat. A ce stade, AdH sera orienté exploration / baston. Et sur cette base, nous pourrons ajouter les autres systèmes.

Les constantes

Au vu de nos capacités techniques, voilà certains points qui ne changeront probablement pas:
- Animations extrêmement limitées. Ne vous attendez pas à voir des gens bouger, c'est totalement au dessus de notre portée, aussi bien en terme de moteur graphique que de capacités à créer et animer des modèles. Ce sera déjà une victoire si les monstres volants battent des ailes!
- Beaucoup d'eau, quelques îles, plutôt Micronésie qu'Australie. Les grands terrains nécessitent de bons systèmes de niveau de détails, que nous n'implémenterons pas.
- Plutôt plusieurs serveurs séparés qu'un grand système avec tout le monde. J'aimerais être l'Eve-online antique, mais 100 joueurs par serveur semble un maximum. Je suppose qu'un modèle comme le nôtre se dirigera plus vers une liste de serveurs indépendants, qui peut-être se fédèreront pour maintenir une liste commune. Le lanceur supporte totalement ce modèle, puisqu'il permet au joueur de visualiser toute une série de serveurs d'un coup d'oeil, et de rapidement créer un compte pour commencer à jouer dans un autre monde.

dimanche 21 juin 2009

Développer son MMORPG - Persistance!

3ème opus de la série, où l'on parlera de la partie "persistance" dans "univers persistants". Que ce soit pour définir le monde ou pour récupérer l'état du serveur après une panne ou une séance de maintenance, pouvoir compter sur sa couche de persistance est indispensable.

Base de données relationnelle? Listes de clés-valeurs? XML? Gros fichiers binaires? Une chose est sûre, il faudra bien d'une manière ou d'une autre sauver ses précieuses données. AdH a fait très tôt le choix de la base de données relationnelle (Postgresql, pour être précis, mais cela aurait pu être Mysql, ou encore Oracle si on avait les sous).

Voici quelques avantages des bases de données relationnelles:

  • Les données sont accessibles directement à partir des outils fournis avec le système. Changer une position ou réparer un inventaire, c'est juste quelques lignes de SQL.

  • Les données sont en sécurité! Ces systèmes sont stables, utilisés dans d'innombrables projets à travers le monde. Les données sont centralisées, et les outils sont fournis pour sauvegarder et restaurer la base.

  • Il existe probablement déjà une bibliothèque pour accéder à la base depuis votre langage de programmation préféré.

  • Les données sont accessibles pour d'autres applications. Il est très aisé d'extraire des statistiques pour les afficher sur une page Web, ou encore de générer des rapports sur l'activité des joueurs.

Et quelques inconvénients:
    Ecrire le schéma prend du temps, et écrire la couche relationnelle dans le code en prend également.
  • Les changements de schéma peuvent être lourds: une colonne qui change dans une table, et il faut potentiellement changer ses index, ses procédures stockées, son SQL dans le code, et enfin le code lui-même.

  • Il faut installer une base pour faire tourner le serveur, en s'assurant que les binaires sont bien à la même version que le SQL.

Ces derniers temps, l'on a beaucoup parlé des bases de données de type clé-valeur, souvent utilisées dans le Web. Très dynamiques, elles permettent d'étendre le modèle de données très simplement, et sont d'une extensibilité sans pareille. Rajouter des paramètres à ses objets devient un jeu d'enfant. Par contre, être aussi dynamique a un coût: la base peut vite devenir bordélique, et les clés et les valeurs de plus en plus complexes et difficiles à interpréter. Sauver du XML en place des valeurs peut être une bonne manière de permettre de sauver simplement des données complexes, mais on se retrouve alors à définir un schéma et donc perdre tous les avantages du dynamisme.

Enfin, reste la solution du bon vieux fichier. Facile à lire, un peu plus difficile à modifier si l'on veut juste changer un petit quelque chose au milieu, il a l'avantage de ne nécessiter l'installation d'aucun logiciel supplémentaire. Par contre, la protection des données, la définition du schéma, leur accès en dehors de l'application, tout cela est entre vos mains. Ça fait un peu beaucoup, non?

Une fois que l'on est content de sa couche de persistance, encore faut-il décider de quand y accéder. D'un côté, il est possible de tout charger en mémoire au démarrage, et de tout sauver de temps en temps (mettons toutes les 10 minutes, dans un thread séparé pour un maximum de performances). C'est rapide. Mais cela veut dire qu'il faut mapper strictement toutes les données de la couche de persistance vers les objets du code. C'est du boulot! Enfin, il faut trouver le bon équilibre pour les sauvegardes: trop souvent, et les performances souffrent. Trop rarement, et un crash inopiné zappe une bonne partie de l'avancement des joueurs, à leur grande colère. Et enfin, arrive un moment où tout ne tient plus en mémoire... De l'autre côté, l'on peut accéder la couche de persistance uniquement quand on a besoin d'une donnée, et l'écrire à chaque fois qu'elle change. On ne perd rien en cas de crash, par contre, le système peut devenir très lent.

Il s'agit de trouver le bon équilibre entre les deux: quelles données peuvent être chargées à la volée? Peut-on les cacher en mémoire? Quelles donnés ont besoin d'être écrites immédiatement, quelles autres peuvent attendre? Comment s'assurer que tout est synchronisé? Typiquement, on fera la distinction entre les données importantes (une transaction entre deux joueurs, un avancement de quête) et celles qui le sont moins (monstre tué, ressources prises). Personne ne se plaindra si après un crash, une créature n'est pas exactement à la même position, ou si la mine contient encore les minerais que l'on a extrait (mais attention quand même, si un joueur découvre comment faire crasher le serveur, il pourrait se fabriquer une mine infinie?).

Enfin, quand il s'agit de coder tout ça, rappelez vous que moins on en écrit, mieux on se porte. Profitez au maximum des bibliothèques, écrivez du code générique pour binder vos données le plus efficacement possible, ou, encore mieux, utilisez des couches de persistance toutes faites (Hibernate?). Et sauvegardez. Tout. Tout le temps.

On se risque sur le bizarre?

Un petit test à partir d'une grille de 2 millions de triangles. La vitesse d'affichage demeure raisonnable, avec manifestement un goulot d'étranglement au niveau des entrées sorties de la carte: le processeur tourne presque à vide, passant la majorité de son temps à attendre.

De toutes façons, là n'était pas le but. La grille tient le coup, mais maintenant, il reste à voir si j'arrive à faire fonctionner les textures multiples comme je le sens.





Et puis, ça m'aura fait réviser les gradients.

lundi 15 juin 2009

Développer son MMORPG - Communications client serveur

Le combat épique, le duel au sommet: binaire ou XML? AdH a beaucoup changé non seulement sur ce choix de base, mais également sur la manière de l'implémenter.

Récapitulons:


  • Performances: Le binaire est le grand vainqueur. Difficile de faire mieux, puisqu'il n'y a généralement aucune transformation entre les données internes du programme et les données envoyées sur le fil. De son côté, XML devra transformer toutes les données en texte et rajouter des balises un peu partout, et ça prend du temps.

  • Taille: Le XML est généralement plus gros, mais l'on peut parfois avoir des surprises! Par exemple, un petit entier au format texte prendra moins de place qu'en binaire. Comparez: <l>1,2,1,1,1,2,5,2,1,2</l> fait 27 octets, mais passer ces 10 entiers 32 bits en binaire prendrait 40 octets! Certes, les puristes me feront remarquer que séparer les entiers par des virgules n'est pas franchement du XML. Et enfin, compressez!

  • Compatibilité Voilà un sujet dans lequel le XML est roi. Ce n'est que du texte, dans un encodage défini dans le message, il est très difficile de se tromper. Alors qu'en binaire, l'on va devoir parler de grand endian contre petit endian, de taille des types de base, de conventions pour passer la taille d'une chaine ou d'un tableau. Et si ça marche bien chez vous, qui sait ce que ça donnera quand vous enverrez le message à un Mac 64 bits?

  • Lisibilité: Le XML est le gagnant toutes catégories. On dira ce que l'on voudra sur la lecture de gros fichiers XML, mais c'est quand même mieux que de regarder des colonnes d'hexadécimal.

  • Maintenance: C'est sur ce point capital qu'avoir une bonne stratégie fera toute la différence, que ce soit en XML ou en binaire. Tout d'abord en XML: n'écrivez pas votre parseur, malheureux! N'écrivez pas non plus le code qui traduit les structures XML en structures de votre langage. Gé - Né - Rez. De nos jours, pléthore d'outils, tels Codesynthesis XSD et gSoap pour le C++, Microsoft XSD pour .NET, JAXB pour Java, et même mlxsd pour Ocaml (non, je déconne, n'utilisez surtout pas mlxsd pour quoi que ce soit de serieux!), vous font de belles classes qui savent se sérialiser toutes seules à partir d'un beau schéma. Changement de données? On change le schéma, on génère, on compile, on résout toutes les erreurs de compilation, on recompile (car seuls les cons pilent, ah ah!), et voilàte, ça marche! Et pour le binaire, alors? Attendez, on y arrive.


Par chance, comme pour la plupart des problèmes récurrents, il existe multitudes de frameworks qui vous les résoudront, tout en apportant une panoplie de difficultés nouvelles. Mais au moins, l'on ressent un certain soulagement à changer sa peine.

Blague à part, ICE, Corba, gsoap et beaucoup d'autres utilisent l'idée que les messages doivent être définis de manière centralisée via un langage de description, utilisé ensuite par des générateurs de code. Et ça, c'est un concept qui marche aussi bien en binaire qu'en XML. En plus, pour ceux qui auraient quand même décidé de coder le client et le serveur dans des langages différents, il suffit que le générateur de code puisse causer dans ces deux langages, et on est sortis d'affaire.

AdH a démarré sur du binaire, puis est passé au XML, revenu sur le binaire puis fait un dernier petit tour en XML avant de revenir fermement en binaire. N'ayant pas à supporter plusieurs langages, j'ai été faible, et j'ai décidé d'écrire moi-même mon générateur de code. L'avantage principale de mon approche est que je passe directement dans la description les types C++ supportés par mon sérializeur, ce qui veux dire que je peux passer des types très forts, tel mon AvatarId dans l'exemple du post en lien. Tous les autres frameworks m'auraient probablement obligé à passer un entier et perdre le typage, ou à décrire chaque type fort séparément, ce qui aurait sérieusement alourdi la chose.

En conclusion, choisir du XML ou du binaire a beaucoup moins d'importance que la manière dont on va maintenir et utiliser sa structure de messages. De plus en plus, il me semble indispensable d'avoir un bon framework qui pourra générer sans erreurs des brouettes de code ennuyeux. Choppez donc en un, et faites le bosser! Et si vous décidez de l'écrire vous-même, assurez vous que les fonctionnalités que vous rajoutez par rapport à un framework existant vous feront vraiment gagner du temps. Depuis, j'ai rajouté à mon générateur de code l'option de lier certains champs à la base de données, me permettant en quelques lignes de code d'extraire mon objet de la base et de l'envoyer sur le réseau!

samedi 13 juin 2009

Développer son MMORPG - Choisir un language

Premier épisode d'une petite série qui durera ce qu'elle durera! A travers ces années à essayer un peu tout et n'importe quoi, voilà quelques idées sur le sujet des langages de programmation pour les MMO.

Les forums de développement de jeu regorgent de questions relatives aux langages qui sont les mieux adaptés à tel ou tel type de jeu. Lorsque l'on rajoute par dessus les besoins de performance et la complexité du développement d'un MMO, la question du langage devient particulièrement épineuse.

Avec AdH, on a un peu tout essayé: serveur en ocaml et c++, client en ocaml et c++, outils en ocaml, c++, java. Rajoutez quelques essais web avec PHP et .NET, une couche de SQL d'une épaisseur plus que changeante. Voilà donc ce qui a donné l'impression de marcher:


  • Il n'y a pas de langage parfait, et entre deux choix raisonnables, le mieux est de choisir quelque chose qui soit bien connu par les membres de l'équipe, et qui soit suffisamment utilisé par ailleurs pour trouver tout un tas de ressources sur le sujet. Développer son Tetris ou son Pacman pour apprendre un nouveau langage, c'est une excellente idée. Démarrer un WOW-killer à cloche pied avec l'idée d'apprendre en route, beaucoup moins! Également, il est préférable d'éviter les langages trop ésotériques, et choisir des technologies stables, matures et pour lesquels il sera facile de trouver de l'aide.


  • Choisir un langage, c'est aussi choisir un écosystème. Pour cette raison, il est important d'identifier les bibliothèques disponibles. Pour les graphismes, une implémentation OpenGL bas niveau ne suffit généralement pas: avez vous vraiment envie de développer un graphe de scène, d'écrire le code de chargement pour les objets 3D, ou de devoir convertir toutes vos images dans un seul format? Vous aurez suffisamment à coder comme ça pour vous embêter à écrire une couche de base de données, un moteur graphique, une couche réseau haut niveau, un bon support des threads, des bibliothèques pour charger et jouer les sons, charger les images, et j'en oublie.


  • Un même langage pour le client et le serveur. C'est un point très discuté, et pour cause. Avec un serveur et un client qui ont fondamentalement des buts très différents (graphismes et sons, portabilité, performances brutes pour le client - réseaux, bases de données, montée en charge pour le serveur), il est tentant de choisir deux langages. Notre expérience est qu'avec deux langages et une petite équipe, on se heurte à tout une série de problèmes:

    • Souvent, les membres de l'équipe se spécialisent, et il est difficile de faire bouger des gens du serveur au client et vice-versa

    • Tous les utilitaires bas-niveau doivent être ré-écrits deux fois

    • La communication entre le client et le serveur devient plus complexe, il y a d'avantages de risques liés à la sérialisation des données

    • De manière générale, une perte de temps bien supérieure aux gains potentiels


  • Un langage plus agile pour les outils. L'émergence de nouveaux langages de script tels Python, Ruby, Perl et autres peuvent fournir des opportunités pour développer rapidement des outils. La difficulté est de bien s'assurer qu'ils seront peu couplés avec l'application principale: par exemple, un éditeur de monde avancé aura probablement besoin des mêmes structures que le client et le serveur, et le choix d'un langage différent pourrait au final causer une perte de temps. En revanche, la création rapide de donnés, d'un panneau administratif, ou encore la génération de code, peuvent bénéficier des langages de script. Par exemple, dans AdH, le langage Ocaml est utilisé pour générer le code C++ de sérialisation des messages, ce qui a sauvé beaucoup de temps de développement.


Allez hop, maintenant on s'y met!

jeudi 11 juin 2009

Functions, requêtes préparées, ou les deux?

Comme souvent, mes choix technologiques correspondent souvent à de grands coups de volant d'un extrême l'autre. Découvrant les fonctions postgresql, je me suis précipité dessus en voulant les utiliser partout. Un peu plus tard, je découvre qu'elles ne sont pas la panacée:

- Pas de protection particulière contre l'injection, puisque l'appel à la fonction est fait d'un appel SQL normal
- Le plan est compilé une fois pour toutes. Si l'on créé une fonction alors que la table est vide, le planificateur peut choisir d'ignorer les index, ce qui provoquera des performances épouvantables si la table devient tout d'un coup énorme
- Enfin, la modification de la signature d'une fonction entraîne un changement dans la base, ainsi qu'un changement dans le code.

Utilisons les requêtes préparées, donc! Compilées au démarrage de l'appli, lors de leur enregistrement, elles permettent un plan plus optimal, protègent de l'injection, et un changement de requête se fait dans le code, au plus près de leur utilisation.

C'était sans compter les requêtes complexes que nécessitent mon système d'authentification... Les requêtes préparées devenaient alors trop compliquées, forçant beaucoup d'allers-retours entre l'application et la base de données. Et libpqxx, pour être une bibliothèque très bien conçue, nécessite beaucoup de code pour faire tenir une requête dans une transaction et pour en récupérer les résultats.

Je me suis donc remis à écrire des fonctions, au moins pour le système de gestion de compte (création et vérification d'un utilisateur, création et vérification d'un avatar). J'appellerai les fonctions via des requêtes préparées, histoire d'améliorer la sécurité. J'espère ne pas trop avoir à modifier mes fonctions, et je les recompilerai autant de fois qu'il le faudra pour que le planificateur prenne des décisions qui montent en charge!

Ma règle devient donc d'utiliser les requêtes préparées quand je le peux, et des fonctions quand je le dois! Certes, avec du recul, c'est évident, mais ça va mieux en le disant.

D'ailleurs, en parlant de choses qui vont mieux en le disant, il est maintenant beaucoup plus facile de rajouter le support du langage pl/pgsql dans sa base (au moins à partir de Postgresql 8.3). Alors que jusqu'à présent j'indiquais systématiquement le chemin vers la bibliothèque, il suffit en fait de faire:


create language plpgsql

C'est quand même plus simple et mnémotechnique, non?