dimanche 31 janvier 2010

Développer son MMORPG - Architecture

5ème partie, où je soutiens que faire "comme les grands" peut avoir des avantages inattendus.

Je ne dirais pas que le plus grand risque du développeur de fond est d'abandonner son projet, mais plutôt de se laisser perdre dans l'exploration de solutions techniques. Ainsi, l'on se retrouve à démarrer bille en tête sur de la 3D, tout jeter pour passer à la 2D quand les difficultés deviennent insurmontables, puis revenir en 3D lorsque l'on vient juste de découvrir un nouveau moteur graphique, puis décider de passer à un moteur de jeu complet, puis se rendre compte de ses faiblesses et revenir à la 2D...

Il est malheureusement difficile d'échapper à ce genre de cycles, et c'est pour cela qu'il faut s'y préparer et développer en gardant en tête que l'on aura sûrement à changer quelques fondamentaux dans un futur proche. Et avoir de bonnes bibliothèques bien génériques est un pas dans la bonne direction.

Il est très peu probable qu'une refonte, même massive, change beaucoup le code de sérialisation, ou l'authentification, ou les logs, ou les utilitaires de bases de données, etc. Mettre ce code dans des bibliothèques bien séparées (et si possible bien testées), c'est l'assurance d'avoir déjà beaucoup de bon code lorsque l'on sonde de nouvelles possibilités.

Mais l'on peut pousser plus loin: l'on peut séparer de grands ensembles du tronc commun, et construire des services entiers qui soient réutilisables partout. Autant les MMORPGs commerciaux distribuent l'authentification, les logs, les données statiques du monde pour des raisons de performance, autant l'amateur peut construire ces mêmes services comme étant des blocs solides dans une architecture instable, lesquels tourneront d'ailleurs gentiment sur la même machine. Et si le succès est au rendez-vous, il sera d'autant plus simple de distribuer.

Un serveur de logs - C'est pas comme si écrire dans un fichier ou une base de données était très dépendant des fonctionnalités du jeu. Une application indépendante qui tourne en tâche de fond, une API, et basta, voilà une belle brique sur laquelle se poser.

Un serveur d'authentification - Encore un service on ne peut plus générique. Un compte, des permissions sur des applications, des permissions plus précises au sein de ces applications... Au fur et à mesure que l'on développe son jeu, l'on peut enrichir le serveur d'authentification avec des fonctionnalités de type rôles, création de compte via un serveur Web, accumulation de statistiques... qui pourront rester stables au fur et à mesure que l'on travaille sur les modules plus proches du gameplay.

Et autres - Peut-être un serveur qui fournit des données statiques? Peut-être des éléments de GUI?

A vrai dire, l'on pourra sans doute changer de langage en cours de route, ces services resteront (pour peu que les communications soient raisonnablement portables).

Bien sûr, il faut éviter de perdre son temps à généraliser du code, mais si un effort mesuré augmente ses chances d'être encore là après deux ou trois itérations, ça vaut le coup.

jeudi 28 janvier 2010

OMake et fichiers générés

J'ai tout une série de classes C++ générées à partir d'un petit programme ocaml. Comment s'assurer que le bon vieux OMake génère tout dans le bon ordre? Malgré quelques subtilités, c'est plus facile qu'il n'y parait.

Voilà mon fichier OMakefile:


LIBFILES[] =
RequestMsg

GENERATEDFILES[] =
MsgId.h
RequestMsg.h
RequestMsg.cpp

CGeneratedFiles($(GENERATEDFILES))

LIB = ../lib/libmessages

.DEFAULT: $(StaticCLibrary $(LIB), $(LIBFILES))

.PHONY: clean
clean:
rm -f *~ *.o adh

.PHONY: gch
gch:
$(CXX) -c $(CXXFLAGS) All.h

$(GENERATEDFILES): messages.xml ../bin/dsgen
../bin/dsgen messages.xml


En premier, la liste des fichiers pour construire la bibliothèque, comme dans tout OMakefile qui se respecte.

Ensuite, la première subtilité. Je liste tous les fichiers qui seront générés par l'application (l'on peut probablement créer la liste à partir de la première liste de fichiers). Puis l'on indique via la commande CGeneratedFiles que ces fichiers sont générés. OMake va donc chercher dans l'ensemble des make files la règle qui lui indiquera comment construire ces fichiers. Ça tombe bien, tout en bas (au milieu, c'est du standard), il y a une règle qui dit que les fichiers dans $(GENERATEDFILES) peuvent être générés à partir de ma description xml et du programme de génération, et donne la commande à faire tourner pour les construire.

Deuxième subtilité, vu que le programme pour construire lesdits fichiers est lui-même créé par un autre make file du même groupe, j'indique le programme comme dépendance, ce qui veut dire qu'il cherchera à compiler le programme d'abord s'il ne peut pas le trouver.

Ansi, tout changement aussi bien dans mon fichier de description de classes (le "messages.xml") que dans le programme qui génère le code forcera une regénération. Et comme OMake se base sur un hash des fichiers pour déterminer si il y a eu changement, une modification cosmétique du générateur, par exemple, qui ne changerait pas le format de fichiers, se traduira par une execution du générateur, et c'est tout: les fichiers n'ayant pas changé, il est inutile de recompiler la bibliothèque, de lier les exécutables...

samedi 23 janvier 2010

Taille d'une base de données Postgresql

C'est pourtant facile!


select datname, pg_size_pretty(pg_database_size(datname))
from pg_database

Valgrind

J'expérimente un petit peu avec Valgrind, et notamment avec callgrind, lequel génère le graphe des appels de fonctions, avec le nombre d'instructions passées dans chaque. C'est très instructif, et fondamental lorsque l'on essaie d'optimiser son programme. Et en plus, le magnifique kcachegrind est l'application graphique qui permet de visualiser les résultats.

Lançons donc un beau test:

valgrind --tool=callgrind ./unittests

Ceci génère un fichier callgrind.out., que l'on charge dans kcachegrind.
kcachegrind callgrind.out.16532


Et voilà le travail!


En regardant par exemple une de mes fonctions les plus coûteuses, la bien nommée geom::isCollision, l'on voit qu'en dehors d'elle même, elle a principalement passé son temps à récupérer les listes d'axes et de vertex pour les cylindres. La collision de cylindres coûte cher, n'en doutons pas!

mercredi 13 janvier 2010

Collisions - Un peu d'UML

Dans ma folle jeunesse, j'avais une haine farouche d'UML, et je craignais le jour où je commencerais à bosser et à devoir l'utiliser tout le temps. Heureusement, je me suis rendu compte que dans l'industrie (du moins dans la mienne), personne n'utilise UML. Au mieux, l'on dessinera un petit croquis avec trois cases et deux flèches pour s'expliquer.

C'est pourquoi, en doses homéopathiques, j'ai fini par apprécier le sous-ensemble d'UML qui me permet juste de mettre quelques idées à plat. En plus, je trouve ça généralement joli.

Voilà donc ma hiérarchie de classes pour la gestion des collisions!



La partie en bas à droite (en dessous de BasicShape) est implémentée et testée. La partie CompoundShape me permettra d'effectuer des collisions entre des solides plus complexes unions de solides simples, comme par exemple un château fort et ses tours fait à partir d'un pavé et de 4 cylindres. La collision des objets complexes sera un bête calcul bourrin de recherche de collisions entre les solides simples.

Enfin, la classe mère Shape fournira une interface renvoyant la boite englobante alignée sur les axes, qui sera la clé de voûte de mon octree (d'ailleurs, il n'y a pas l'air d'avoir de traduction d'octree, même Wikipedia l'utilise... Que pensez-vous d'octarbre?).

dimanche 10 janvier 2010

Tutorial - Détection des collisions

Je me suis enfin penché pour de bon sur la détection des collisions, sujet qui m'a toujours paru insurmontable. Mais cette fois-ci, et grâce à quelques recherches sur GameDev.net, j'ai fini par comprendre et implémenter la technique basée sur le théorème de séparation des convexes.

Le principe est simple: deux solides convexes sont séparés si et seulement si il existe un hyperplan (c'est à dire un plan pour la dimension 3, ou une droite pour la dimension 2) de telle sorte que l'un soit d'un côté, et l'autre de l'autre.



Quand bien même cette définition est utile pour tout solide, c'est pour les polygones et les polyèdres qu'elle devient foudroyante. Prenons la dimension 2, par exemple. S'il existe une infinité de droites potentiellement séparatrices, il suffit en fait de vérifier chaque droite correspondant à un côté de chacun de notre polygone. Et comment vérifie-t-on que les polygones sont séparés? Tout simplement en prenant une droite orthogonale à notre droite séparatrice, et en projetant chaque point de chaque polygone sur cette droite. Si les projetés sont séparés, l'on a une droite séparatrice, et l'on peut s'arrêter.



Toutes les faces ne fourniront pas une droite séparatrice, comme par exemple ici:



L'algorithme est donc très simple: l'on prend chaque face de chaque polygone. L'on prend la normale à la face, et l'on projette chaque point sur la normale, via un bête produit scalaire. L'on garde le plus petit et le plus grand des produits scalaires pour chacun des deux polygones, et s'il n'y a pas intersection, les polygones sont séparés et l'on s'arrête. Si après avoir testé toutes les faces des deux polygones, l'on a toujours pas réussi à les séparer, c'est qu'il y a collision.

En 3 dimensions, c'est pareil, l'algorithme permet de transformer un problème complexe en 3D en plusieurs problèmes triviaux en 1D. Voilà le pseudo code:


Pour chaque axe n de chaque polygone
pour chaque vertex v du polygone 1
p = v * n
min1 = min(tous les p)
max1 = max(tous les p)
pour chaque vertex v du polygone 2
p = v * n
min2 = min(tous les p)
max2 = max(tous les p)
si (min1, max1) séparé de (min2, max2)
pas de collision, sortir
Chaque axe a été testé négatif, collision, sortir


J'ai parlé d'axes au lieu de normales aux faces, c'est parce que certaines formes ont des faces qui ont des normales dans la même direction, et qu'il est donc inutile de dupliquer l'effort. Par exemple, pour un cube, on pourra se contenter de tester 3 axes au lieu des 6 normales.

mercredi 6 janvier 2010

La P5W - Revue de détail

Justement, revenons-y, à ma carte mère Asus P5W. A ce qu'il me semble, une carte mère, c'est comme l'eau courante: c'est quand ça foire qu'on se rend compte que ça existe. Au final, je n'ai eu que deux problèmes sous ma Debian: le micro, et, plus tard, les problèmes d'ACPI.

Quand j'ai commencé à l'utiliser, je ne pouvais rien enregistrer, et l'entrée micro était grisée dans alsamixer. Sous Windows, il a également fallu batailler avec le logiciel de configuration du son, le chipset Via essayant manifestement d'être trop intelligent pour son bien. Heureusement, au bout d'un moment, une mise à jour d'un paquet de Squeeze (le noyau? alsa? autre chose?) a tout remis en place, et je peux maintenant utiliser Skype.

Le deuxième problème était celui de l'ACPI. Assez rapidement, j'ai pensé à mettre à jour le Bios, mais c'était une opération qui m'inquiétait un petit peu. La crainte que ça ne foire et que je me retrouve avec un bout de plastique inutilisable me refroidissait. De plus, l'opération en elle-même me semblait compliquée, basée sur des outils Dos.

Mais en fait, c'était tout bête. En effet, la P5W sait lire les clés USB, ce qui rend l'opération triviale:

- Copier le fichier ROM (dézippé) sur la clé
- Redémarrer la machine, aller dans le Bios
- Démarrer l'outil de flash du bios, lequel détecte la clé, et affiche le fichier
- Tant qu'à faire, sauvegarder le bios courant
- Installer la mise à jour
- Redémarrer, et se caler confortablement dans son fauteuil

Pour le reste, tout fonctionne exactement comme il faut sans m'embêter. Le réseau est content, la RAM est contente, les multiples prises USB sont contentes, et il y a même tout un tas de connecteurs dont je ne sais même pas à quoi ils servent. Linux repère gentiment les capteurs de température et de vitesse des ventilos. Le Bios regorge d'options pour ajuster tout ça, avec peut-être la possibilité de réduire le bruit, mais j'ai de bons ventilos, alors je préfère ne pas toucher à tout ça.

Seul bémol: le temps de démarrage est assez long. Il faut bien entre 25 et 30 secondes entre le moment où j'appuie sur le bouton et où Grub affiche les choix. J'ai vaguement essayé de tripatouiller quelques options pour réduire ce temps, mais sans succès. Ça ne m'empêche pas de dormir non plus, ceci dit.

lundi 4 janvier 2010

Enfin, je fais tourner un noyal 2.6.30!

Je commençais à désespérer: cela faisait plusieurs mois que j'étais coincé sur un noyau 2.6.26 sur ma Debian, à cause d'un problème d'ACPI. Ma carte mère, une Asus P5W, refusait de démarrer les noyaux plus récents, me sortant les segfault les plus ésotériques. J'ai bien essayé de démarrer avec les options de boot acpi=off, nolapic et autres, mais le mieux que j'ai obtenu c'est un système avançant comme un escargot.

Finalement, j'ai pris mon courage à deux mains, et j'ai mis à jour le Bios, passant de la version 0404 à la version 0501. Et là, miracle! Je démarre!

Bon, entre temps, c'est le driver de la carte vidéo qui fait tout planter et qui m'a forcé à revenir en mode non-accéléré, mais c'est pas grave. Je coderai des routines mathématiques en attendant que ça revienne.

vendredi 1 janvier 2010