jeudi 29 juillet 2010

Bon ben ça y est, c'est codé...

Sénèque disait: "Ce n'est pas parce que les choses sont difficiles que nous n'osons pas, c'est parce que nous n'osons pas qu'elles sont difficiles". M'est avis qu'il était programmeur!

L'adage s'est donc vérifié, et ma routine de génération de route s'est gentiment codée, couvée des yeux par de nombreux test unitaires. Résultat: rien n'est prêt pour accueillir le bébé! Mon architecture n'est pas encore capable d'utiliser la routine, parce que je ne m'attendais pas à ce qu'elle fonctionne si tôt. Je revois donc mes diagrammes de classe, et essaie de caser la chose de manière naturelle.

Au passage, j'ai simplifié la méthode du post précédent sur le sujet.



Je calcule i, intersection des vecteurs de départ et d'arrivée. Je vérifie ensuite que i est devant le premier vecteur, et derrière le second. Ceci fait, je calcule les distances entre chaque vecteur et i. La plus petite distance devient d1, que je transfère de l'autre côté de i. Cette section sera ma section courbe, dont je calcule le centre en prenant les orthogonales qui se coupent en c. Le reste de la voie est une droite.

Cette méthode se contente donc de deux intersections, et de quelques calculs de distances et de vecteurs orthogonaux. Probablement suffisamment efficace pour la faire tourner en temps réel, pour que l'utilisateur puisse voir la trace de sa voie au fur et à mesure qu'il ajuste ses vecteurs.

mardi 27 juillet 2010

Développer son MMORPG - Threads

6ème partie (enfin! s'écrie mon public en délire), où j'évoque les tentations du multithreading, et laisse entendre qu'il faut mieux les laisser aux grands garçons (et aux grandes filles).

Ceux qui, comme votre serviteur, auront passé trop de temps sur les forums de développement de jeux vidéos (même stack overflow s'y met: regardez!) auront pu découvrir un certain nombre de questions qui peuvent se résumer ainsi: où est-ce que je met mes threads?

Le jeune scarabée s'empresse de lister alors une série de composants, et leur assigne unilatéralement un thread, histoire de dire que. L'on se retrouve avec un thread par zone, un thread pour la physique, un thread pour les communications, un thread pour le commerce, un thread pour le pathfinding, etc. Côté client, on imagine un thread pour le rendu, un thread pour la GUI, un thread pour la physique, un thread pour la musique, un thread pour les communications avec le serveur, und so weiter.

Arrêtez là, malheureux! Écoutez les paroles de celui qui s'est lamentablement planté avant vous sur exactement le même chemin.

Pas de threads. Nope. N'essayez pas, ce n'est même pas la peine. Non seulement ce n'est pas la peine, mais je soutiens qu'un effort non négligeable est nécessaire pour supprimer, ou du moins abstraire, tout ce qui pourrait avoir besoin d'un thread (mettons, le réseau).

La raison est tout simplement qu'il est horriblement compliqué de gérer la synchronisation des threads. Et qu'en plus, les bibliothèques externes sont rarement thread safe, et qu'il faut donc coder nombre de couches d'abstractions pour garantir que l'on ne va pas exploser en vol. Je ne parle même pas des test unitaires et du débuggage.

Du côté serveur, prévoyez également une simple boucle, éventuellement pilotée par les événements réseau. La bibliothèque boost::asio est particulièrement pratique pour ce cas de figure: elle autorise à faire tourner des routines basées sur un chronomètre d'une part, et sur les messages réseau d'autre part, mais toujours dans le même thread.

Enfin, pour ceux qui s'inquiètent de voir les trois quarts de leur puissance de calcul inutilisés, voici ce que vous pouvez en faire:


  • Faire tourner plusieurs instances du serveur

  • Calculer des statistiques à partir de la base de données

  • Compiler du code pour ajouter des fonctionalités!



Quant à ceux qui se laissent tenter par le chant des sirènes, j'attends avec impatience vos retours d'expérience, statistiques à l'appui. Bon courage!

dimanche 25 juillet 2010

Des petits riens

Peu d'avancées notables, mais des petites touches ça et là. J'ai rajouté un contrôle pour pouvoir démarrer et arrêter le train à volonté, ce qui s'est avéré ludique pendant au moins 5 minutes. J'adore l'idée de Julien d'avoir une vue depuis le train, j'ai donc commencé à réfléchir aux changements à apporter à l'architecture du code pour permettre de changer le point de vue. Et j'ai également commencé à coder l'algorithme de disposition de voies, le tout lourdement muni de tests unitaires, parce qu'il va y en avoir besoin!

J'ai également essayé de modéliser un arbre en utilisant le moteur de textures de Blender (voyez la capture), mais l'export est méchamment parti en vrille, donc je n'ai pas pu l'intégrer au paysage.

jeudi 22 juillet 2010

Bézier & Co

Julien et Kokuma ont très justement noté dans le post précédent que le genre de problème consistant à trouver des courbes à partir de points de contrôle se résout très bien en utilisant des courbes de Bézier.

C'est une approche tout à fait valide, et qui est probablement plus compréhensible pour l'utilisateur. Cependant, les courbes de Bézier souffrent de quelques désavantages dans le cas qui nous occupe.

Le plus criant est la difficulté de calculer une longueur sur la courbe. Mes trains se déplaçant à vitesse fixe, je dois pouvoir aller chercher un point à distance x de ma courbe, et de facilement trouver quelle est ma position et mon orientation en ce point. Il faut également définir quelle est la distance jusqu'à la fin de la courbe, pour savoir quand passer à la suivante.

Moins gênant dans l'immédiat, mais également problématique, le calcul de la courbure. En effet, la vitesse maximale du train sur une section de rail dépend de la courbure, ce qui est réaliste d'une part, et propose un défi intéressant à l'utilisateur qui doit optimiser ses voies pour la vitesse d'autre part. D'ailleurs, en travaillant à partir de courbes de Bézier, il est moins évident pour l'utilisateur d'observer la courbure maximale de son rail. Avec des arcs de cercle, la courbure est constante, et il est beaucoup plus facile pour l'utilisateur de percevoir les contraintes de vitesse.

Ces deux problèmes peuvent bien entendu se résoudre numériquement, mais sont triviaux avec des droites et des arcs de cercle.

Il est d'ailleurs intéressant de noter à quel point la difficulté d'implémentation s'équilibre: les droites et les courbes rendent les déplacement du train très faciles, mais sont difficiles à disposer. Les courbes de Bézier rendent les voies très simples à installer, mais le déplacement du train devient alors problématique.

J'ai un instant pensé à utiliser des arcs d'ellipses (avouez que ça aurait eu de la gueule!), mais j'ai vite déchanté en voyant la formule de calcul de la circonférence. L'ellipse est donc plutôt du côté Bézier, plutôt plus facile à disposer, puisqu'un seul arc peut s'adapter aux points de contrôle, mais beaucoup plus difficile en termes de navigation.

mercredi 21 juillet 2010

Puisqu'on parle d'intersections...

Parlons donc de rails!

Voici un petit schéma du problème et de la solution. L'utilisateur a entré chaque borne du rail, définie par une position et un vecteur tangent au rail (en noir sur le schéma). Quel est le rail défini par ces contraintes?
Tout d'abord, traçons les droites normales aux bornes. Elles se croisent en un point nommé C1.

Ensuite, définissons C2 à l'intersection de la droite la plus longue, et d'une droite parallèle à la droite la plus courte, de manière à ce que la distance entre la borne et C2 soit identique à la distance entre C2 et l'intersection de notre parallèle avec la droite issue de la deuxième borne (il y a du Thalès là dedans. Si je pensais que je le ressortirais un jour, celui là!). Si ces explications vous semblent confuses, regardez où est C2 sur le schéma: les deux segments de droite marqués a sont de longueur identique.

C2 définit maintenant le centre de l'arc de cercle correspondant à la partie courbe de la voie, la partie droite de la voie continuant simplement. La voie est indiquée en bleu sur le schéma.

Les quelques détails supplémentaires à régler pour obtenir une implémentation solide sont la gestion des cas impossibles, et l'affichage en temps réel du chemin proposé, pour que l'utilisateur sache où il aille.

De beaux défis en perspective.

Intersection de droites

Étant donné deux droites dans le plan définies chacune par un point et un vecteur, trouver leur intersection (si elle existe).

C'est autour de ce problème que je procrastinais depuis un certain temps, et une fois le boulot fait, force est de reconnaître que c'est trivial. Il fallait bien s'y mettre, puisque cette routine est à la base de nombreux systèmes de définition des rails (et notamment des courbes). Enfin, voici la bête:


boost::optional<dVector2>
geom::intersect(const dVector2 & v1,
const dVector2 & n1,
const dVector2 & v2,
const dVector2 & n2)
{
double denominator = n2(0) * n1(1) - n2(1) * n1(0);

if(std::abs(denominator) > 0.000001)
{
double numerator =
(v1(0) * n1(1) - v1(1) * n1(0)) -
(v2(0) * n1(1) - v2(1) * n1(0));

return boost::optional<dVector2>(v2 + n2 * (numerator / denominator));
}
else
{
return boost::optional<dVector2>();
}
}

En regardant la formule de près, je trouve qu'il y a beaucoup de calculs de type Ax * By - Ay * Bx, qui me font furieusement penser à un produit vectoriel. Il y a peut-être moyen d'effectuer ce calcul en utilisant des opérations sur les vecteurs au lieu de leurs composantes. À creuser.

Au rapport!

Tout ça pour ça :(

Je me suis battu toute la soirée pour essayer d'afficher un beau rapport en utilisant une wxGrid, mais pour une raison que j'ignore, celle-ci me bloque les événements d'une manière bizarre, et toutes les applications du bureau virtuel courant refusent de répondre! Est-ce qu'il y avait un bug dans mon code, ou étais-ce dû au fait que j'utilise la version Beta de wxWidgets (souvenez-vous, pour avoir l'antialiasing!), je ne sais. Finalement, j'ai abandonné, et je suis revenu à une bonne vieille wxListCtrl, qui a le bon goût de marcher sans faire de vagues.



J'espère que remplir le rapport en question sera moins frustrant.

jeudi 15 juillet 2010

GUI - Rafraîchissement

Le gros intérêt de se baser sur le système d'événements de wxWidgets est de pouvoir gérer séparément le rafraîchissement des différents éléments du programme.


  • La simulation et l'affichage 3D tournent aussi vite que possible, à partir d'un événement OnIdle. L'on peut aller jusqu'à 1500 images par secondes.

  • La plupart des éléments de la GUI doivent se mettre à jour suffisamment lentement pour être visibles (cela ne fait aucun sens de mettre à jour la date 1000 fois par seconde!), mais suffisamment rapidement pour ne pas rater d'informations utiles, ou paraître saccadés. Pour la date, la vitesse des trains, le compte en banque de l'utilisateur... Un wxTimer tournant 10 fois par seconde rend très bien.

  • Enfin, certaines données sont plutôt des moyennes à grande échelle, comme par exemple l'affichage du taux de rafraîchissement. Dans ce cas, un autre wxTimer affichant l'information 1 fois par seconde est amplement suffisant.

Le tout avec un seul thread, ce qui simplifie grandement la vie.

Youpie pour la programmation événementielle!

dimanche 11 juillet 2010

Des trains qui foncent

Enfin! Après une semaine à coder toute l'infrastructure autour du déplacement des trains sans rien pouvoir tester (enfin, autrement que par mes tests unitaires, bien sûr!), mon petit train galope sur son chemin de fer (à cheval?).

Ni une, ni deux, j'en ai fait une vidéo, que je m'empresse de faire partager:



Ainsi qu'une image, pour voir le train d'un peu plus près (c'est du programmer's art, vous êtes prévenus!).



Ah, et le nom (temporaire?) du projet devient "OpenRailz".

mardi 6 juillet 2010

Pas de code!

Sensations de brûlure dans la main, le poignet et le coude... Pas en état d'écrire du code en soirée, il faut que je me réserve pour la journée, faut bien croûter! Cependant, pour satisfaire la curiosité des millions de fans, je poste ma locomotive et mon wagon. J'espère bientôt les voir rouler sur ma voie ferrée!


dimanche 4 juillet 2010

C++0x - Initialisation

Vous en avez assez d'écrire des tartines de code pour initialiser vos conteneurs? Ça tombe bien, C++0x pense à vous! Sans plus attendre, comparez:


std::vector<int> vi;
vi.push_back(1);
vi.push_back(2);
vi.push_back(3);
vi.push_back(4);
vi.push_back(5);
à

std::vector<int> vi {1, 2, 3, 4, 5};

Cool, non? La bibliothèque boost::assign fournissait déjà des utilitaires similaires, mais c'est beaucoup plus facile à utiliser comme ça. Bien entendu, ça marche également pour les types plus complexes:

std::vector<std::string> vs {"a", "b", "c", "d"};


Et, cerise sur le gâteau, on peut imbriquer les initialisations:

std::vector<std::vector<int> > vvi {{1, 2}, {3, 4, 5}};

std::vector<std::vector<std::string> > vvs
{{std::string("a"), std::string("b")},
{ std::string("c"), std::string("d"), std::string("e")}};

Notez cependant que dans le second exemple, il faut passer le constructeur, car g++ (au moins) ne le fait pas implicitement comme pour l'exemple non-imbriqué.

Je trouve cette fonctionnalité particulièrement intéressante pour écrire des tests unitaires, car c'est typiquement là que l'on a besoin d'objets déjà définis. Plus d'excuses pour ne pas en écrire, donc!

vendredi 2 juillet 2010

Downgrade de fglrx sous Debian

La dernière mise à jour de Squeeze m'ayant cassé mon driver (blocks noirs dans Firefox, vachement pratique...), je me suis mis dans la tête, après avoir infructueusement tenté de trouver une option qui résoudrait le problème, de downgrader le paquet. C'est moins technique qu'il n'y parait:

Tout d'abord, vérification des paquets à changer. Ça tombe bien, le cache contient les paquets récemment mis à jour:


$ cd /var/cache/apt/archives/
$ ls | grep fglrx
fglrx-atieventsd_1%3a10-5-1_amd64.deb
fglrx-atieventsd_1%3a10-6-1_amd64.deb
fglrx-driver_1%3a10-5-1_amd64.deb
fglrx-driver_1%3a10-6-1_amd64.deb
fglrx-glx_1%3a10-5-1_amd64.deb
fglrx-glx_1%3a10-6-1_amd64.deb
fglrx-glx-ia32_1%3a10-5-1_amd64.deb
fglrx-glx-ia32_1%3a10-6-1_amd64.deb
fglrx-modules-dkms_1%3a10-5-1_amd64.deb
fglrx-modules-dkms_1%3a10-6-1_amd64.deb


Ah ah! On dirait bien qu'il faut redescendre de la 10-6-1 à la 10-5-1. Installons chacun des paquets fglrx en version 10-5-1 avec dpkg:

$ dpkg -i fglrx-driver_1%3a10-5-1_amd64.deb
$ dpkg -i fglrx-modules-dkms_1%3a10-5-1_amd64.deb
$ dpkg -i fglrx-glx_1%3a10-5-1_amd64.deb
$ dpkg -i fglrx-glx-ia32_1%3a10-5-1_amd64.deb
$ dpkg -i fglrx-atieventsd_1%3a10-5-1_amd64.deb

(bon, d'accord, on peut mettre tous les paquets sur la même ligne).

Reboot...

Et je retrouve l'accéleration, et Firefox sans le mode "protection des témoins". Pfiou!