lundi 20 décembre 2010

Bug!

Les rails sont de retour, mais j'ai du rater une étape:



Voyage mouvementé en perspective?

Contrôle

Avec la réorganisation du système d'entités graphiques, construire sa voie ferrée devient plus facile (ou moins frustrant, c'est selon). Voici donc mon petit message de Noël en traverses de chemin de fer:

jeudi 16 décembre 2010

C++0x - Moins de Boost, plus de Standard

Je me suis livré à un petit nettoyage de mes en-têtes précompilées, en enlevant les en-têtes Boost pour lesquelles j'avais un remplacement en C++0x.

Peu de gain, au final, puisque j'économise environ 12Mo sur des précompilations faisant entre 120 et 300Mo, mais c'est toujours ça de pris, sans compter un code plus cohérent. Voici les remplacements:

  • <boost/shared_ptr.hpp> est remplacé par <memory> et son std::shared_ptr

  • <boost/scoped_ptr.hpp> et <boost/scoped_array.hpp> sont remplacés par l'excellent std::unique_ptr

  • <boost/static_assert.hpp> est remplacé par static_assert

  • <boost/optional.hpp> vire à cause des soucis d'aliasing

  • <boost/enable_shared_from_this.hpp> est fourni par std::shared_from_this

  • <boost/thread.hpp> est remplacé par <thread>. Attention cependant, pas encore de groupes de threads dans le standard!

  • <boost/non_copyable.hpp> est remplacé par les suppressions de méthodes (mot-clé delete)

samedi 11 décembre 2010

Bibliothèque piglet

La bibliothèque piglet pour "Platform Independent Graphical Layer Entity Tools" (désolé, pas pu m'empêcher...) sépare enfin le système d'entités, lequel reçoit un lifting à la mesure de son importance. J'ai des pages couvertes de diagrammes de classes, mais l'idée est d'avoir plusieurs types d'entités, contenant chacun un objet graphique abstrait. L'implémentation OSG s'effectue en implémentant l'interface d'objet graphique, et la modification d'objets s'opère via un visiteur (après toutes ces années, j'ai enfin compris qu'un visiteur n'était qu'un double dispatch un peu bidouillé, mieux vaut tard que jamais...).

Dans l'immédiat, ça ne va pas donner beaucoup de différences à l'écran (et ça commence à faire un moment, me hurlera ma horde de fans déchaînés, qui n'aura pas tort), mais cela permettra enfin, je l'espère, d'implémenter de manière à peu près correcte des objets qui s'animent en temps réel, notamment les voies lors de l'ajustement des waypoints.

C'est reculer pour mieux sauter, et c'est probablement la meilleure manière d'arriver quelque part. Le système d'entités a démarré très simplement, et a fait un boulot admirable jusqu'ici. Les besoins autour de l'affichage des objets graphiques sont maintenant plus clairs, et surtout j'ai une implémentation qui marche. C'est donc maintenant, ni trop tôt et ni trop tard, qu'est le moment idéal pour retravailler le module en profondeur.

Sinon, et sur un tout autre sujet, je pense enfin pouvoir me débarrasser des derniers boost::shared_ptr du code et les remplacer par des std::shared_ptr, avec l'espoir, entre autres, de virer quelques fichiers d'en têtes de ma pré-compilation pour retarder du même coup le moment où il va me falloir investir dans quelques barrettes de RAM.

mardi 7 décembre 2010

C++0x - Chronomètres

Enfin, et c'est pas trop tôt, une interface C++ pour mesurer le temps. Celle-ci vient de plus avec d'intéressantes fonctionnalités. Mais voyons d'abord un petit programme d'exemple:


#include <chrono>
#include <iostream>

int main()
{
auto t1 = std::chrono::system_clock::now();
usleep(100000);
auto t2 = std::chrono::system_clock::now();

std::cout << (t2 - t1).count() << std::endl;

return 0;
}

Tout bête! Remarquez l'utilisation de auto pour ne pas avoir à m'ennuyer à définir le complexe type retourné par la méthode statique. Cependant, et c'est là que je trouve que le standard fait très fort, les types fournis permettent de s'affranchir totalement des problèmes d'unités souvent rencontrés dans ces cas là: quelle est la précision fournie par la bibliothèque? Et quelle est la précision voulue par l'utilisateur? C'est là que le type duration (ici implicite) de (t2 - t1) donne toute sa mesure. Regardons plutôt:

#include <chrono>
#include <iostream>

int main()
{
auto t1 = std::chrono::system_clock::now();
usleep(100000);
auto t2 = std::chrono::system_clock::now();

std::chrono::nanoseconds n = (t2 - t1);
std::cout << n.count() << std::endl;

std::chrono::microseconds u = (t2 - t1);
std::cout << u.count() << std::endl;

std::chrono::duration<double> d = (t2 - t1);
std::cout << d.count() << std::endl;

return 0;
}

Là où ça devient magique, c'est que la valeur est automatiquement convertie dans l'unité demandée. Le programme affiche:

100059000
100059
0.100059

Ces types std::chrono::nanoseconds et std::chrono::microseconds sont des typedef sur le type duration, lequel prend comme paramètres templates le type de base, et un ratio (avec un défaut de 1, pour les secondes).

Et, cerise sur le gâteau, g++ refusera même de compiler une conversion non exacte. La ligne
std::chrono::seconds s = (t2 - t1);
renvoie le message d'erreur suivant:
error: static assertion failed: "the resulting duration is not exactly representable"
En effet, le typedef std::seconds prenant en type de base un entier, la conversion perd en précision. Pour que cela marche, il faut utiliser un double, comme dans l'exemple précédent.

Qui a dit que le C++ n'était pas intuitif? :)

lundi 6 décembre 2010

C++0x - std::atomic

Les variables atomiques dans c++0x fournissent (enfin!) une manière standard pour protéger les types de base, avec un support automatique des instructions atomiques quand elles sont disponibles. Voyons le programme suivant avec g++4.4.


#include <thread>
#include <iostream>

void increment(int & counter)
{
for(size_t i = 0; i < 10000; i++)
{
counter++;
}
}

void decrement(int & counter)
{
for(size_t i = 0; i < 10000; i++)
{
counter--;
}
}

int main()
{
int counter;

std::thread t1(&increment, std::ref(counter));
std::thread t2(&decrement, std::ref(counter));

t1.join();
t2.join();

std::cout << counter << std::endl;

return 0;
}

C'est prévisible, le programme va afficher des nombres totalement farfelus en sortie, car counter n'est pas protégé.

Maintenant, protégeons counter:

#include <cstdatomic>
#include <thread>
#include <iostream>

void increment(std::atomic<int> & counter)
{
for(size_t i = 0; i < 10000; i++)
{
counter++;
}
}

void decrement(std::atomic<int> & counter)
{
for(size_t i = 0; i < 10000; i++)
{
counter--;
}
}

int main()
{
std::atomic<int> counter;

std::thread t1(&increment, std::ref(counter));
std::thread t2(&decrement, std::ref(counter));

t1.join();
t2.join();

std::cout << counter << std::endl;

return 0;
}

Magie de la technologie moderne, le programme affiche systématiquement un beau 0 tout rond. Un appel de la méthode is_lock_free() sur counter (atomic_is_lock_free() sur gcc 4.5, plus avancé au niveau des standards) vous dira si votre architecture supporte les instructions atomiques.

Voilà, c'est à peu près tout! A noter cependant que l'en-tête atomic a fait son arrivée dans gcc 4.5. Avec cette version, le programme d'exemple (de mémoire), serait (et avec les lambdas, s'il vous plait!):

#include <atomic>
#include <thread>
#include <iostream>

int main()
{
std::atomic<int> counter;

std::thread t1([&counter]()
{for(size_t i = 0; i < 10000; i++) counter++;});
std::thread t2([&counter]()
{for(size_t i = 0; i < 10000; i++) counter--;});

t1.join();
t2.join();

std::cout << counter << std::endl;

return 0;
}

mercredi 1 décembre 2010

C'est mieux

Les UserObject et les callbacks semblent donner un design un peu plus raisonnable. L'envers de la médaille, c'est que je suis revenu d'un bon en arrière, et je me retrouve à ré-implémenter la création des waypoints (va falloir que je trouve bon un nom en français).

Rendez-vous dans quelques semaines pour redécouvrir Openrailz pareil qu'aujourd'hui :)

samedi 27 novembre 2010

C++0x - shared_ptr, bind, et for_each

Pour ceux qui utilisaient déjà Boost, rien de fondamentalement nouveau sous le soleil: C++0x fournit enfin en standard une implémentation de pointeur partagé, ainsi que la fonction de bind qui va bien. Le vieux code Boost peut être mis à jour simplement en remplaçant vos boost:: par des std::, hormis cependant une petite subtilité: les paramètres tels _1, _2, ne sont pas dans le namespace global comme avec boost, mais dans le namespace std::placeholders. L'on pourra soit faire un using namespace std::placeholders;, soit, pour éviter les conflits si l'on inclut également Boost, créer un alias afin de réduire la verbosité du code.


#include <iostream>
#include <algorithm>
#include <memory>
#include <vector>
#include <string>

namespace p = std::placeholders;

class Miaou
{
public:
Miaou(const std::string & v):
m_v(v)
{
}

void print()
{
std::cout << m_v << std::endl;
}

private:
std::string m_v;
};

int main()
{
std::vector<std::shared_ptr<Miaou> > v =
{std::shared_ptr<Miaou>(new Miaou("a")),
std::shared_ptr<Miaou>(new Miaou("b")),
std::shared_ptr<Miaou>(new Miaou("c"))};

std::for_each(v.begin(),
v.end(),
std::bind(&Miaou::print, p::_1));

return 0;
}


Avec ces constructions additionnelles de ce côté, et les lambdas de l'autre, ce sont tous les algorithmes qui deviennent bien plus utiles. Je rêve de pouvoir enfin donner à std::accumulate la place qui lui revient!

mercredi 24 novembre 2010

Ça n'aura pas duré longtemps...

mais mon design est pourri. Je vous rappelle l'idée: faire dériver chaque objet (station, section de rail, etc) à la fois d'un objet logique et d'un objet graphique. Le problème, il est que les objets sont inter-dépendants: la création d'une station force la création de sections de rails associés. Donc, quand l'objet logique station est créé, comment fait-il pour créer les objets complets (logique + graphique) pour la section? L'on n'est limité à passer de complexes factories un peu partout. C'est moche, c'est compliqué, et c'est intestable. Bref, à jeter.

Je suis vraiment au carrefour de l'architecture du truc, si je le fais bien, ça ira tout seul, sinon, je risque fort de me lasser à force de me battre avec le code.

C'est pas grave, j'ai des tas d'idées. Dériver de l'objet logique était bien pour la gestion des objets, de leur construction et de leur destruction. Je garde donc l'idée que l'objet logique doit pouvoir posséder l'objet graphique, mais j'essaie de découpler.

Chaque objet logique possède donc un "UserObject", qui dérive d'une interface. En plus de cela, la classe World est munie d'un dispatcheur, qui permet au système graphique de détecter toutes le créations et destructions d'objets logiques. À la création d'un objet logique, le système graphique peut ainsi ajouter un "UserObject" graphique. A la destruction, l'objet graphique s'en va en même temps que l'objet logique.

Le concept de user objets est très courant, comme par exemple dans wxWidgets ou dans Open Scene Graph. J'ai donc bon espoir que l'idée colle également à ma logique.

dimanche 21 novembre 2010

Boost asio - Queues de messages - Un exemple complet

Voilà un exemple complet avec un service unique, et des queues de messages parallélisables (pour Prime) et séquentielles (pour Logger). Dans l'objet Logger, plutôt que de maintenir une référence sur le service, on construit un objet strand, lequel garantit que tous les appels passés par lui seront séquentiels.

Notez la création et la destruction de l'objet m_work. Lorsqu'il est détruit, il assure que les appels à io_service::run vont retourner une fois que tous les messages auront été traités, ce qui permet de terminer l'application une fois que toutes les requêtes auront été complétées. Afin également d'éviter la destruction prématurée des objets Logger et Prime, les appels à boost::bind prennent un shared_from_this qui va garder une référence sur l'objet au sein du message.

Pour compiler sous Unix:

g++ main.cpp -o main -lboost_system-mt -lboost_thread-mt


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace boost::assign;

class Service : public boost::noncopyable
{
public:
Service(int nbThreads):
m_work(new boost::asio::io_service::work(m_service))
{
for(int i = 0; i < nbThreads; ++i)
{
m_threadGroup.create_thread
(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)));
}
}

~Service()
{
m_work.reset();
m_threadGroup.join_all();
}

boost::asio::io_service & getService()
{
return m_service;
}

private:
boost::asio::io_service m_service;
boost::scoped_ptr m_work;
boost::thread_group m_threadGroup;
};

class Logger : public boost::noncopyable,
public boost::enable_shared_from_this
{
public:
Logger(boost::asio::io_service & service):
m_strand(service)
{
}

void log(const std::string & message)
{
m_strand.dispatch(boost::bind(&Logger::doLog,
shared_from_this(),
message));
}

private:
void doLog(const std::string & message)
{
std::cout << message << std::endl;
}

boost::asio::io_service::strand m_strand;
};

class Prime : public boost::noncopyable,
public boost::enable_shared_from_this
{
public:
Prime(boost::asio::io_service & service,
const boost::shared_ptr & logger):
m_service(service),
m_logger(logger)
{
}

void nthPrime(size_t n)
{
m_service.dispatch(boost::bind(&Prime::doNthPrime,
shared_from_this(),
n));
}

private:
void doNthPrime(size_t n)
{
std::vector primes(1, 2);
size_t current = 2;
while(primes.size() < n)
{
current++;
size_t i;
for(i = 0; i < primes.size(); ++i)
{
if(current % primes.at(i) == 0)
break;
}
if(i >= primes.size())
{
primes.push_back(current);
}
}
std::ostringstream str;
str << n << "th prime is " << primes.at(n - 1);
m_logger->log(str.str());
}

boost::asio::io_service & m_service;
boost::shared_ptr m_logger;
};

int main()
{
boost::shared_ptr service
(new Service(3));
boost::shared_ptr logger
(new Logger(service->getService()));
boost::shared_ptr prime
(new Prime(service->getService(), logger));

std::vector values;
values +=
20000, 10000, 5000, 7500, 15000,
17000, 14000, 11000, 21000, 11000;

std::for_each(values.begin(),
values.end(),
boost::bind(&Prime::nthPrime, prime, _1));
}


Asio fournit bien plus qu'une couche d'abstraction au dessus des sockets réseau. Il serait dommage de cantonner cette bibliothèque à la communication client serveur, alors qu'elle fournit un paradigme puissant pour construire des applications événementielles sans avoir à s'arracher les cheveux sur les problèmes bas-niveau.

Boost asio - Queues de messages

La bibliothèque Asio, intégrée à Boost, permet de gérer des événements de manière asynchrone. Principalement utilisée pour le réseau, elle peut également être très utile pour résoudre des problèmes de programmation concurrente. Un exemple très simple: la gestion de queues de messages.

Prenons donc une classe qui affiche des messages sur la console. Une manière de gérer l'accès concurrent est de mettre un bon vieux mutex autour de l'appel à std::cout, forçant chaque thread à attendre sur des opérations d'entrées sorties potentiellement longues. Une autre manière, souvent plus efficace, est d'ajouter le message sur une queue, laquelle est lue par un thread unique chargé de l'affichage. Comment faire de même avec Asio?


class Logger
{
public:
Logger():
m_work(m_service),
m_thread(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)))
{
}

~Logger()
{
m_service.stop();
m_thread.join();
}

void log(const std::string & message)
{
m_service.dispatch(boost::bind(&Logger::doLog, this, message));
}

private:
void doLog(const std::string & message)
{
std::cout << message << std::endl;
}

boost::asio::io_service m_service;
boost::asio::io_service::work m_work;
boost::thread m_thread;
};

Cette classe s'utilise simplement en instanciant l'objet Logger, puis en appelant la méthode log. L'appel à log est thread safe, et peut donc être appelé par n'importe quel thread de l'application. L'affichage, lui, ne tourne que depuis le thread interne de la classe. Pas de mutex, pas de conditions, tout est planqué dans Asio.

Remarquez l'objet work, qui indique à m_service qu'il y a toujours quelque chose à faire, pour éviter que m_service.run() ne retourne prématurément.

Et pour l'opération inverse, c'est à dire l'utilisation d'une queue de messages pour faire tourner des calculs potentiellement lourds simultanément? C'est à peine plus complexe, comme par exemple dans cette classe qui calcule le n-ième nombre premier.


class Prime
{
public:
Prime():
m_work(m_service)
{
m_threadGroup.create_thread(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)));
m_threadGroup.create_thread(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)));
m_threadGroup.create_thread(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)));
m_threadGroup.create_thread(boost::bind(&boost::asio::io_service::run,
boost::ref(m_service)));
}

~Prime()
{
m_service.stop();
m_threadGroup.join_all();
}

void nthPrime(size_t n)
{
m_service.dispatch(boost::bind(&Prime::doNthPrime, this, n));
}

private:
void doNthPrime(size_t n)
{
std::vector primes(1, 2);
size_t current = 2;
while(primes.size() < n)
{
current++;
size_t i;
for(i = 0; i < primes.size(); ++i)
{
if(current % primes.at(i) == 0)
break;
}
if(i >= primes.size())
{
primes.push_back(current);
}
}
std::cout << primes.at(n - 1);
}

boost::asio::io_service m_service;
boost::asio::io_service::work m_work;
boost::thread_group m_threadGroup;
};

Faisant tourner 4 threads à partir du bon vieux thread pool de chez Boost, cette classe va empiler les requêtes et n'en faire tourner que 4 maximum à la fois.

L'étape suivant serait d'appeler Logger depuis Prime, afin de n'afficher le résultat que depuis un seul thread. L'on peut ainsi construire un programme à partir de briques de base qui gèrent elles-mêmes l'accès concurrent, sans avoir à se (trop) se préoccuper de l'accès concurrent ou d'interbloquages.

Cette approche est cependant limitée par l'explosion du nombre de threads dans l'application, chaque brique gérant un certain nombre de threads indépendants. Lorsque la charge de travail est lourde, l'on risque de se retrouver avec beaucoup plus de threads tentant de s'exécuter que de processeurs.

L'on peut alors modifier quelque peu son approche, pour partager un même service asio au sein du programme, et laisser à la bibliothèque le soin d'ordonnancer les tâches.

S'assurer que l'accès à certaines ressources demeure séquentiel, comme pour notre Logger, peut se faire grâce aux strands. Démonstration dans un prochain post.

vendredi 19 novembre 2010

Pas assez d'objet?

Je ne suis pas satisfait de mon design autour des concepts principaux d'OpenRailz que sont les sections de rails et les stations. Peut-être ais-je péché par excès d'anti-POO primaire, et, cherchant un style plus fonctionnel, me retrouve avec quantités de collections d'objets. Je cherche donc à centraliser un petit peu, pour une fois, en utilisant le bon vieil héritage multiple (que je pourrais transformer en interface à un moment ou à un autre, c'est à voir).

Le résultat, c'est que plutôt que de séparer ma station de l'entité la représentant, je créé une classe StationEntity qui dérive à la fois de Station et de OsgEntity.

Nous verrons ce que cela donne.

dimanche 14 novembre 2010

Fallout 3 - New Vegas - C'est plié

Après 50 heures de jeu, me voilà déjà à la fin... Ou plutôt, une des fins. Fallout 3 New Vegas a tenu toutes les promesses, les quêtes étaient intéressantes, interactives et profondes, les personnages attachants, et l'histoire tout à fait prenante.

J'hésite maintenant entre reprendre une sauvegarde un peu en arrière et essayer d'autres fins, ou tout redémarrer du début avec une ligne très différente. Mais là, tout de suite, je vais plutôt me remettre à coder. Faut que je me remette de mon overdose!

jeudi 4 novembre 2010

Coder efficacement avec Emacs - Partie 5: Scripts utiles

Ou comment sauver un temps précieux avec quelques fonctions simples. Voici deux scripts glanés ici, adaptés par mes soins, qui facilitent la vie. Ajoutez les à votre .emacs, et voyez si ça vous plaît.

Ce script écrit de lui-même les #ifndef / #define / #endif des fichiers en-tête C et C++, en se basant sur le nom du fichier et du répertoire courant.


(defun headerize ()
"Adds the #define HEADER_H, etc."
(interactive)
(let ((flag-name (replace-regexp-in-string
"[\. \(\)]" "_"
(upcase (file-name-nondirectory (buffer-name)))))
(dir-name (upcase(file-name-nondirectory (directory-file-name(file-name-directory (buffer-file-name)))))))
(goto-char (point-max))
(insert "\n#endif\n")
(goto-char (point-min))
(insert (concat "#ifndef __" dir-name "_" flag-name "__\n"))
(insert (concat "#define __" dir-name "_" flag-name "__\n"))
)
)


Ouvrez un fichier, et tapez M-x headerize. Hop, voilà les en-têtes! Le fichier peut être modifié pour ajouter une mention de copyright, un auteur, etc. C'est toujours ça de moins à taper.

J'adore celui-ci: en pressant la touche F9, l'on passe automatiquement du fichier source au fichier d'en-tête, et réciproquement (à condition que les fichiers aient le même nom et soient dans le même répertoire, c'est pas magique non plus!).


(define-key global-map [f9] 'switch-on-extensions)

(defun rewrite-filename (filename rules)
(if rules (or
(let ((current-rule (car rules)))
(and (string-match (car current-rule) filename)
;; The current rule can be applied, return the
;; modified filename
(let ((name (replace-regexp-in-string
(car current-rule) (cadr current-rule)
filename)))
;; We return the name if either it can be
;; created (the rule has 't' for third value) or
;; if it exists already.
(and (or (cadr (cdr current-rule)) (file-exists-p name))
name))))

;; In any other case, we go on looking for other rules
(rewrite-filename filename (cdr rules)))

(error (concat "No rewriting rule applicable for '" filename "'"))))

(defun switch-on-extensions ()
"Switches to a file whose name is derived from the name of the
current buffer. The rewriting rules are specified in
`switch-on-extensions-rules'."
(interactive)
(if (buffer-file-name)
(find-file (rewrite-filename (buffer-file-name) switch-on-extensions-rules))
(error "No file attached to this buffer!")))

(setq switch-on-extensions-rules '(
("\\.cpp$" ".h" t)
("\\.h$" ".cpp" t)
("\\.cc$" ".h" t)
("\\.h$" ".cc")
("\\.ml$" ".mli" t)
("\\.mli$" ".ml" t)
("" "" )
))

dimanche 31 octobre 2010

Fallout 3 - New Vegas

Voici donc la raison de mon silence radio de ces derniers temps (et cela risque de durer un peu plus longtemps!). Grand fan de Fallout 3, je ne pouvais laisser passer l'opus suivant, et la chose est tout à fait à la hauteur de ses ambitions. Pas de révolution, juste un univers encore plus complet et cohérent, une histoire prenante, des personnages déjantés, et des steaks de geckos.

C'en est au point que j'aperçois des radscorpions quand je vais au boulot le matin.

Les quelques crashs et bugs graphiques ne sont pas suffisants pour modérer mon enthousiasme. J'y retourne!

mercredi 20 octobre 2010

Le syndrome des 15 000 lignes

Je suis une fois de plus frappé par ce mal mystérieux qui surgit lorsque que mon application atteint la limite fatidique des 15 000 lignes. Je sais que je suis près d'avoir un système de destinations qui fonctionne, et je suis plutôt satisfait du moteur graphique. Je ne suis pas convaincu par la disposition des rails, mais à la limite cela peut se résoudre plus tard.

Mais voilà, la motivation m'a (momentanément) abandonnée. Je n'arrive plus à écrire la moindre ligne de code. Un petit peu de patience sera donc requise de la part de mes hordes de fans attendant avec avidité un Openrailz jouable :)

samedi 2 octobre 2010

GUI - Itinéraires et propriétés

Le système d'itinéraires commence à tenir la route. J'ai également rajouté un autre panneau pour afficher les propriétés de l'objet courant, comme une gare ou un train.



Ces nouveaux panneaux réduisent la partie 3D à sa portion congrue (et encore, question gui, vous n'avez rien vu!), mais c'est heureusement là que la possibilité de déplacer et de cacher certaines sections va être fondamentale.

dimanche 26 septembre 2010

Les boites de dialogue, c'est long à faire

Mais ça serait encore plus long à coder directement en OpenGl (et probablement pas moins moche), donc je persiste.



La boite de dialogue des itinéraires avance gentiment, il est maintenant possible d'aller sélectionner des gares sur le terrain pour les ajouter à un itinéraire.

Il reste un peu de plomberie à faire pour relier les trains et les itinéraires. Peut-être qu'après cela, enfin, il sera possible de contrôler ses trains.

samedi 25 septembre 2010

Moi, une référence?

Et pourtant, on dirait que mon post sur les en-têtes précompilées a suffisamment plu pour se retrouver sur une page pour les TPs de l'université de Metz (que l'on peut voir ici après s'être connecté en tant qu'invité). Allez les jeunes, et bon courage!

mercredi 22 septembre 2010

Feed RSS du projet

Yay, que de fun! J'ai ajouté sur la droite un feed vers les news du projet Sourceforge. C'est plus facile de voir les derniers commits!

dimanche 19 septembre 2010

Interface pour les itinéraires

Et une petite capture pour vous prouver que le week-end n'a pas été que glande.



Voici donc la section de l'interface pour gérer les itinéraires. Remarquez les magnifiques icônes sur la partie droite, tous droits sortis d'Inkscape. A terme, cette interface permettra de créer des itinéraires, c'est à dire la liste des stations à visiter, avec potentiellement quelques informations supplémentaires tels le temps à attendre à une station donnée, ou l'ordre de s'arrêter ou pas dans les stations intermédiaires.

vendredi 17 septembre 2010

Cityscape

Quelques avancées sur le code de rendu de ville. Voici donc 10 000 "bâtiments" normalement distribués sur le terrain (et un peu à côté, aussi, mais bon...).



Pour maintenir des performances correctes, je découpe le monde en cellules de 100x100. Chaque cellule contient ensuite un osg::LOD, qui va gérer 3 niveaux de détails.

  • Les bâtiments détaillés, à proximité de la caméra

  • Les bâtiments peu détaillés, un peu plus loin

  • Un nombre limité de bâtiments peu détaillés (par exemple, 1/4 des bâtiments habituels, plus les batiments spéciaux), encore plus loin

Et bien sûr, ne rien afficher au delà d'une certaine distance.

L'intérêt du troisième niveau, dit "clairsemé", est qu'il donne une bonne impression de distance, tout en n'étant pas trop méchant pour les performances. Au fur et à mesure que l'on s'éloigne, l'on verra tout d'abord certains bâtiments disparaître, puis, plus tard, les autres, ce qui est moins brusque qu'une zone entière devenant vide d'un coup.

mercredi 15 septembre 2010

Tutorial - Gérer le passage high-poly à low-poly avec Blender pour OSG

Ce petit tutorial décrit la marche à suivre pour créer un objet high-poly dans Blender, puis d'en sauver les normales dans une texture pour un objet low-poly.

Commençons par créer un objet high-poly. J'ai démarré du cube de base, subdivisé, puis ajouté quelques reliefs intéressants.





Ensuite, créons le même cube, mais sans subdivisions, à l'endroit exact du premier cube. Pour éviter la confusion, appelons le cube détaillé "HighCube" et le cube simple "LowCube".

Créons ensuite la texture du LowCube. Sélectionnez en mode edit, tapez "u", et faites un unwrap (j'aime bien la smart projection, sans l'option "stretch to bound"). Créez l'image, et sauvez. Blender vous montre à peu près ça:



Remarquez le rendu moche du cube, dû au Z fighting des deux cubes superposés.

Maintenant, sélectionnez les deux cubes, et allez faire un coup de "bake" pour les normales, en object space, avec l'option "selected to active".



Le rendu de la texture donne ceci, qui correspond aux normales aux faces:



Ajoutez maintenant un material par défaut à LowCube, et exportez le. En le passant dans Shadedit avec notre shader standard (à peine modifié pour ne pas s'embêter avec la texture de couleur), l'on a bien le cube simple, mais avec les normales déplacées comme pour le cube détaillé!

lundi 6 septembre 2010

Oh le beau bruit!



Une texture de bruit utilisée comme normal map. J'aime beaucoup les reflets obtenus, et c'est encore mieux quand ça bouge. Je posterais bien une vidéo si seulement kdenlive acceptait de les exporter sans planter lamentablement...

samedi 4 septembre 2010

Un shader plus complet


varying vec3 v;
varying vec2 t0;

void main()
{
gl_Position = ftransform();
v = vec3(gl_ModelViewMatrix * gl_Vertex);
t0 = gl_MultiTexCoord0.xy;
}



varying vec3 v;
varying vec2 t0;

uniform sampler2D textureMap;
uniform sampler2D normalMap;

void main()
{
vec3 lightVec = normalize(gl_LightSource[0].position.xyz - v);

vec3 normal =
gl_NormalMatrix *
(vec3(-1, 1, -1) *
normalize(texture2D(normalMap, t0).rgb * 2 - 1));

vec4 base = texture2D(textureMap, t0);

vec4 ambiantTerm =
gl_LightSource[0].ambient *
gl_FrontMaterial.ambient;

float diffuse = max(dot(normal, lightVec), 0.0);
vec4 diffuseTerm =
diffuse *
gl_LightSource[0].diffuse *
gl_FrontMaterial.diffuse;

float specular = pow(max(dot(reflect(lightVec, normal * 0.8), v), 0.0),
gl_FrontMaterial.shininess);
vec4 specularTerm =
specular *
gl_FrontMaterial.specular *
gl_LightSource[0].specular;

gl_FragColor =
ambiantTerm * base +
diffuseTerm * base +
specularTerm;
}


Un shader pour les normal maps de Blender

Après une après-midi à me battre avec mon shader, j'ai enfin réussi à maîtriser la bête. Il reste encore beaucoup pour obtenir le shader ultime, mais au vu de la complexité du processus, je vais commencer par un petit tutorial simple sur la manière d'obtenir des normal maps dans OpenSceneGraph.

La plupart des shaders que l'on trouve sur le net sont des shaders en tangent space, est à dire qu'ils correspondent aux normales, ou au déplacement de normales, tangentiellement à la surface au point appliqué. L'intérêt de ces shaders est multiple, entre autres, ils fonctionnent sur des objets déformables, et ils peuvent être appliqués localement pour perturber les normales, permettant ainsi d'avoir par exemple une petite texture de sable appliquée à l'ensemble de la plage.

Je n'ai rien contre le tangent space, mais malheureusement, OSG et Blender si. Blender ne sait pas exporter les tangentes, et OSG ne sait pas les importer. Je pourrais en théorie les calculer pour chaque objet, nécessitant soit de créer mon propre format au sein d'OSG, ou d'aller méchamment tripatouiller les modèles. Mon plan est donc d'utiliser une alternative en attendant qu'une bonne âme fournisse un worflow Blender OSG complet.

En attendant, je m'intéresse aux normales en object space, qui sont très proches des normales aux faces. La différence, c'est qu'au lieu de définir une normale par face ou par vertex, on définit la normale dans la texture.

Démarrons donc Blender, et tentons de créer un objet qui ait une surface intéressante.



Supprimons le cube de départ, et ajoutons une bête UV sphère, que l'on étirera dans la direction z. Un petit coup de "Set smooth" pour faire joli. Et c'est maintenant que tout démarre. Ajoutons un material et sa texture. Je choisis par exemple du Voronoï:



De retour dans les matériaux, sélectionnons notre texture comme étant appliquée aux normales. Renforçons également la valeur "Nor" à 5, afin d'avoir un relief plus profond.



Il est maintenant temps de créer la texture. Sélectionnons l'objet, et déroulons sa texture: (Tab) pour passer en mode édition, (u) pour le dérouler, choisir "Unwrap - Smart projection", déselectionner "Stretch to boun" pour éviter les distorsions.



En changeant la fenêtre à "UV/Image editor", l'on peut voir notre modèle tout aplati. L'on peut maintenant créer l'image qui va contenir la texture, en choisissant dans ce menu (Image) -> (New). Allons y franchement pour ce modèle, avec une texture en 1024x1024.



Effectuons le rendu: dans le menu de rendu, choisir (Bake), sélectionner (Normals) pour rendre uniquement les normales, et changez le normal space vers (Object). Clic sur Bake, et voilà, la texture est complétée! Sauvez là, et admirez:



L'on remarque que les couleurs dominantes changent, car elles correspondent aux directions des normales depuis l'objet. Par comparaison, la texture en espace tangent ressemble à ça:



Ensuite, l'on peut exporter l'objet, par exemple au format Open Inventor (.iv).

J'ai créé une petite application qui me permet d'ajuster l'objet et les shaders en temps réel. Je charge l'objet, ajuste mes shaders, et voilà, un bel œuf de dinosaure!



Voici le code pour le vertex shader:


varying vec3 v;
varying vec3 n;
varying vec2 t0;

void main()
{
gl_Position = ftransform();
v = vec3(gl_ModelViewMatrix * gl_Vertex);
n = normalize(gl_Normal);
t0 = gl_MultiTexCoord0.xy;
}

et le fragment shader:

varying vec3 v;
varying vec3 n;
varying vec2 t0;

uniform sampler2D normalMap;

void main()
{
vec3 lightVec = normalize(gl_LightSource[0].position.xyz - v);
vec3 normal =
gl_NormalMatrix *
(vec3(-1, 1, -1) * normalize(texture2D(normalMap, t0).rgb * 2 - 1));
float diffuseTerm = max(dot(normal, lightVec), 0.0);
gl_FragColor = vec4(1, 1, 1, 1) * diffuseTerm;
}


Je vais maintenant affiner le shader:

  • Passage au multitexturing, pour avoir à la fois les normales et les couleurs

  • Gestion de la lumière spéculaire, pour permettre par exemple un rendu "mouillé"

  • Amélioration du pipeline, et résolution des quelques points bizarres, telle la multiplication par (-1, 1, -1)

dimanche 29 août 2010

Une villa



Maintenant, tout le problème va être de l'exporter vers OSG!

vendredi 27 août 2010

Postgresql et window functions

Les window functions de Postgresql permettent d'écrire des requêtes bien plus avancées, et ainsi de résoudre de nombreux problèmes complexes en pur SQL. Par exemple, prenons la table et les données suivantes:


create table historical(
id integer not null,
valid_from timestamp not null,
valid_to timestamp not null);

insert into historical values(1, '17-04-2010', '19-04-2010');
insert into historical values(1, '19-04-2010', '20-04-2010');
insert into historical values(1, '20-04-2010', '03-05-2010');
insert into historical values(1, '07-05-2010', '08-05-2010');
insert into historical values(1, '08-05-2010', '14-05-2010');
insert into historical values(2, '17-04-2010', '18-04-2010');
insert into historical values(2, '20-04-2010', '21-04-2010');
insert into historical values(2, '21-04-2010', '24-04-2010');
insert into historical values(2, '25-04-2010', '27-04-2010');
insert into historical values(2, '30-04-2010', '02-05-2010');
insert into historical values(2, '02-05-2010', '05-05-2010');


Pour une raison ou pour une autre, les données historiques ont été ajoutées sans essayer de les combiner avec l'existant, et l'on se retrouve donc avec bien plus de lignes que nécessaire dans la base. Ansi, les entrées du 17 au 19, du 19 au 20 et du 20 au 3 pourraient être représentées par une seule ligne, valide du 17 au 3. La question est: est-il possible d'écrire une requête SQL qui renvoie les données compactées?

Avec les window functions, oui!

L'idée est d'abord d'utiliser la fonction "lag", qui renvoie la valeur dans la table un certain nombre de lignes avant ou après, afin de comparer chaque ligne à la précédente. Si elle est différente, retournons 1, sinon, retournons 0:

select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to

Cette requête nous renvoie une colonne supplémentaire, "agg", qui est à 0 lorsque la ligne pourrait être combinée avec la précédente.

1 2010-04-17 00:00:00 2010-04-19 00:00:00 1
1 2010-04-19 00:00:00 2010-04-20 00:00:00 0
1 2010-04-20 00:00:00 2010-05-03 00:00:00 0
1 2010-05-07 00:00:00 2010-05-08 00:00:00 1
1 2010-05-08 00:00:00 2010-05-14 00:00:00 0
2 2010-04-17 00:00:00 2010-04-18 00:00:00 1
2 2010-04-20 00:00:00 2010-04-21 00:00:00 1
2 2010-04-21 00:00:00 2010-04-24 00:00:00 0
2 2010-04-25 00:00:00 2010-04-27 00:00:00 1
2 2010-04-30 00:00:00 2010-05-02 00:00:00 1
2 2010-05-02 00:00:00 2010-05-05 00:00:00 0

Ceci fait, appelons maintenant la fonction "sum", pour renvoyer la somme courante des "agg", ce qui fournit un rang:

select id, valid_from, valid_to,
sum(agg) over (order by id, valid_from, valid_to) as ranked
from
(select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to) as agg_aggregated
order by id, valid_from, valid_to

Cette requête retourne maintenant un rang identique pour chaque ligne pouvant être combinée.

1 2010-04-17 00:00:00 2010-04-19 00:00:00 1
1 2010-04-19 00:00:00 2010-04-20 00:00:00 1
1 2010-04-20 00:00:00 2010-05-03 00:00:00 1
1 2010-05-07 00:00:00 2010-05-08 00:00:00 2
1 2010-05-08 00:00:00 2010-05-14 00:00:00 2
2 2010-04-17 00:00:00 2010-04-18 00:00:00 3
2 2010-04-20 00:00:00 2010-04-21 00:00:00 4
2 2010-04-21 00:00:00 2010-04-24 00:00:00 4
2 2010-04-25 00:00:00 2010-04-27 00:00:00 5
2 2010-04-30 00:00:00 2010-05-02 00:00:00 6
2 2010-05-02 00:00:00 2010-05-05 00:00:00 6

Il est maintenant trivial d'agréger les lignes ayant le même rang, et de retourner le plus petit "from" et le plus grand "to".

select
min(id) as id,
min(valid_from) as valid_from,
max(valid_to) as valid_to
from
(select id, valid_from, valid_to,
sum(agg) over (order by id, valid_from, valid_to) as ranked
from
(select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to) as agg_aggregated
order by id, valid_from, valid_to) as agg_ranked
group by ranked
order by id, valid_from

Le résultat est celui attendu:

1 2010-04-17 00:00:00 2010-05-03 00:00:00
1 2010-05-07 00:00:00 2010-05-14 00:00:00
2 2010-04-17 00:00:00 2010-04-18 00:00:00
2 2010-04-20 00:00:00 2010-04-24 00:00:00
2 2010-04-25 00:00:00 2010-04-27 00:00:00
2 2010-04-30 00:00:00 2010-05-05 00:00:00


Postgres peut ainsi combiner un million de lignes à la minute sur un PC de bureau, alors que les solutions alternatives allant du chargement et de la combinaison dans un programme séparé, à la solution itérative (mal) implémentée via une extension dans une BDD moins costaude, peuvent être de 5 à 1000 fois plus lents. Yay!

jeudi 26 août 2010

Mes bibliothèques

Voici un petit graphique de la structure des bibliothèques du projet, avec le nombre de lignes de code entre parenthèses:



Les bibliothèques mammouth sont les utilitaires bas niveau (c'est une bonne chose), la bibliothèque qui contient la logique (rail) (c'est une bonne chose aussi, puisqu'elle fait partie des tests unitaires), et enfin les utilitaires OpenSceneGraph. Ceux là sont moins évidents à tester, puisque le résultat est la plus part du temps graphique.

Mon dernier commit a déplacé un gros bout de la logique de osgutils vers rail, ce qui va me permettre de tester lourdement mon graphe représentant le réseau et comment s'y déplacer. J'en suis effectivement presque à devoir implémenter ma version de l'algo de Dijkstra, ce qui est toujours amusant.

dimanche 22 août 2010

Relier les gares

Les gares contiennent maintenant des rails, et ces rails fournissent en leur bout des waypoints, ce qui permet donc de relier les gares au réseau.



Prochaine étape: les trains dans les gares.

dimanche 15 août 2010

OpenRailz - Et maintenant?

La démo n'est pas vraiment sortie à un moment particulier du développement. C'est plutôt que j'ai réussi à m'extraire de la léthargie profonde dans laquelle toute mention de développement sous Windows me plonge, et de tenter de compiler. Néanmoins, ça fait toujours du bien de se souvenir d'où on va.


  • Compléter les gares - Ajout de rails au sein de la gare, et génération de waypoints statiques au bout des lignes afin de pouvoir relier la gare au réseau

  • Ajouter les dépôts - Il va bien falloir faire partir les trains de quelque part! Une alternative est de simplement pouvoir faire atterrir le train sur un bout de rail, peut-être m'en contenterai-je pour le moment

  • Gérer enfin les trains de bout en bout - Une fois qu'il y a des trains sur la ligne, et des gares où aller, je n'aurai plus d'excuses pour ne pas implémenter mon pathfinder, et permettre de donner des ordres aux trains

  • Monter en charge - Avec un bout de ligne sur un pauv' carré de terrain et un malheureux train, il n'est pas très difficile d'avoir un bon millier d'images par secondes. Cependant, le moteur tel qu'il est ne tient pas la route dès que l'on rajoute des voies supplémentaires. Il va donc falloir refondre le graphe de scène sous forme de quadtree, de gérer le niveau de détail pour chaque nœud du quadtree, et enfin de créer des nœuds d'états de manière à réduire au minimum les chargements de shaders.

Niveaux aléatoires

Je regardais cette question sur stack exchange gamedev, ce qui m'a ramené quelques années en arrière lorsqu'il avait fallu que je génère des niveaux aléatoires pour mon projet de fin d'études. Mon algorithme de génération était probablement la meilleure partie du projet, et j'avais été agréablement surpris du look de mes niveaux.

L'algorithme, basé sur une grille, était le suivant:


  • Générer aléatoirement des pièces rectangulaires, en précisant leur nombre, et les limites de largeur et de longueur

  • Utiliser un algorithme de recherche de chemin (mettons, A*), pour tracer des couloirs de chaque pièce à chaque autre pièce. En fonction des poids que l'on donne aux endroits déjà creusés (les pièces et les couloirs existants) par rapport reste du monde, l'on obtient un univers plus ou moins biscornu: un poids très élevé pour les zones non creusées va pousser l'algorithme à passer par les pièces et les couloirs déjà existants, ce qui génère des couloirs rares, mais très irréguliers. En revanche, un poids plus bas permet à l'algo de creuser plus de nouveaux couloirs, et l'on se retrouve avec des mondes plus labyrinthiques, avec de nombreuses façons d'aller d'un endroit à un autre.

Ce qui était plaisant, c'est qu'à partir de quelques paramètres de base, il était possible de générer des niveaux très différents, et le résultat (en terme de disposition du niveau, hein, pas en terme de qualité graphique!) n'était pas si loin des ténors du genre, type Diablo ou assimilés.

OpenRailz sous Windows

C'était pas de la tarte, mais ça y est, j'ai une version d'OpenRailz qui tourne sous Windows, disponible ici. Je n'ai pas pu tester sur une machine qui n'aie déjà Visual Studio 2010, il est donc possible qu'il faille installer les "redistribuables" pour compléter les DLLs.

Le plus difficile, ça a été de compiler toutes les dépendances sous Visual C++ 2010, car les binaires ne sont généralement pas disponibles. WxWidgets s'est montré particulièrement résistant, me forçant à aller bidouiller les fichiers de projet à la main.

Au menu des problèmes rencontrés lors du port:
- En plus des spécifications pour les constructeurs et les destructeurs, l'initialisation en {} n'est pas non plus implémentée dans VC 2010. Il m'a donc fallu rajouter les push_back et les insert qui vont bien
- Les Property Tree de Boost ne compilent pas! C'est la mauvaise surprise de la journée. C'est particulièrement ennuyeux parce que les ressources sont maintenant définies dans un fichier XML dans le format Boost, et que donc la seule manière de le remplacer soit de le réécrire moi-même, ce qui n'était franchement pas le but de la manœuvre. Pour les besoins de la démo, j'ai codé en dur toutes les ressources, mais je vais avoir besoin d'attendre soit que le compilo évolue, soit que Boost résolve le problème.
- J'utilise ça et là quelques types définis dans cstdint, comme par exemple uint32_t, qui n'ont pas l'air définis par Visual C++ 2010. Je n'ai pas franchement envie de les remplacer par du boost::uint32_t, j'aime bien Boost, mais j'ai quand même l'impression que je devrais pouvoir gérer mes types de base tout seul!
- Quelques différences dans wxWidgets: il faut par exemple appeler wxInitAllImageHandlers pour avoir le support du png, et appeler Realize() sur les barres d'outil pour qu'elles s'affichent, ce qui n'était pas le cas sous Linux. Plus ennuyeux: il semble que cliquer sur un menu, ou déplacer une boite de dialogue, peut bloquer le rendu. J'espère qu'il sera possible de résoudre ces problèmes.

Pour ceux qui auraient 5 minutes pour essayer, dites moi comment ça tourne!

samedi 14 août 2010

Release de la démo

On n'ira pas bien loin avec la démo, mais c'était l'occasion d'écrire un peu de documentation pour la compilation.

OpenRailz version 0.1 vient donc de débarquer chez SourceForge:

Les données

Le code

Comme je le mentionne dans la documentation, en sortir une version pour Windows ne sera pas une mince affaire: en l'état, en plus de la réunion de toutes les dépendances, il me faudra aussi adapter le code pour Visual Studio 2010, lequel implémente un différent sous-ensemble des fonctionnalités C++0x. Par exemple, il va me falloir remplacer toutes les spécifications "default" et "delete" pour les constructeurs et les destructeurs, par les corps de fonction correspondants.

lundi 9 août 2010

Tickets s'il vous plait!

Moi qui aime les structures monumentales, je vais être servi! Voici, tirés via quelques polygones grossiers, une gare ferroviaire. Si j'avais le courage, je me lancerais dans des textures semi-transparentes pour l'arche, mais pour l'instant, le gris souris sera de mise!



Modéliser un prototype sous Blender, c'est probablement l'aspect le plus amusant: avec quelques commandes de base, on tripatouille quelques volumes simples en essayant de trouver les éléments qui vont faire reconnaître le modèle du premier coup d'œil. Ici, des quais, des petits ponts, et une grande arche, hop, c'est une gare!

Le deuxième aspect, qui est l'effet d'échelle, est généralement facile à obtenir par l'ajout de quelques éléments qui donnent immédiatement une comparaison avec une taille humaine. Ansi, un petit rebord transforme tout de suite un gros pavé en un immeuble, et, ici, le petit pont par comparaison donne de l'ampleur à la longueur des quais.

dimanche 8 août 2010

Les aiguillages?

Les voici!



J'ai cassé une bonne partie du code d'installation des voies pour concevoir quelque chose de plus construit et si possible de plus utilisable. Ce n'est pas encore particulièrement ergonomique, mais l'on peut déjà faire des aiguillages!

mercredi 4 août 2010

Une nouvelle vidéo

J'étais content de voir l'installation des rails fonctionner, donc j'ai pondu une petite vidéo un poil plus construite que la précédente. Fondus au noir, musique "originale", et tout le toutim. Pour ceux que ça intéresse, j'ai utilisé Rosegarden pour la musique, et kdenlive pour l'édition. Il a fallu se battre un peu avec l'export, qui s'entêtait à coller la vidéo plus vite que la musique, mais au final c'est venu tout ensemble raisonnablement gentiment.



Les rails s'installent plutôt bien à partir du moment où l'on se contente de rendre des formes jolies. Pour l'efficacité, on repassera: il est au final assez difficile d'aller à un endroit donné. Par exemple, simplement continuer en ligne droite est plutôt malaisé. Il va donc falloir ajouter des outils pour visualiser tout cela un peu mieux, et fournir des modes de tracé de rail plus intuitifs. Peut-être la possibilité de poser ses vecteurs, puis de les ajuster pour voir le tracé, pourrait aider.

Je réfléchis également à la manière d'installer les gares. La question se pose entre avoir un type de gare fixe, ou permettre à n'importe quel bout de rail de devenir une gare, ce qui serait plus flexible, mais pas forcément plus clair pour l'utilisateur, et très certainement beaucoup plus compliqué à implémenter (allez rendre une gare jolie quand elle part dans tous les sens!). Il va falloir continuer à réfléchir.

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!

mardi 29 juin 2010

Gestion des véhicules

Enfin, le problème de la gestion des véhicules est résolu!

Enfin, quand j'aurais implémenté mon design que voici:



En effet, le souci, c'est que, comme beaucoup de gens, j'imagine, j'ai mes idées dans les endroits les plus ésotériques (c'est à dire dans les endroits où réfléchir est la chose la plus intéressante disponible). Je me précipite dès que possible donc sur un papelard pour fixer tout cela au clair.

L'idée principale, ici, c'est que chaque véhicule possède un chemin, et suit ce chemin sans discuter. Le chemin permet donc d'abstraire tout ce qui est en dessous: vitesse max, arrêts nécessaires, position des wagons pour les trains. Lorsque le véhicule arrive au bout du chemin, il peut alors demander au réseau (ferré ou routier, hein, pas le réseau de communications. Quoique...) comment, à partir de sa position actuelle, aller à sa prochaine destination. Le réseau fait tourner son petit Dijkstra (que je vais probablement préférer à A*, mais j'en recauserai), et renvoie un nouveau chemin que le véhicule peut apposer à son chemin courant. Et c'est reparti!

dimanche 27 juin 2010

Créer ses textures dans Blender

Enfin, j'ai compris comment générer ses textures dans Blender! Le "Node edit" mode, que je n'avais jamais vu auparavant, permet en effet de graphiquement définir de complexes textures procédurales. Tout est expliqué dans cet excellent tutoriel.

Voilà le mur tel que je l'ai généré:



Cela m'ouvre beaucoup d'horizons pour la modélisation des bâtiments. Ces textures donneront je l'espère vie aux bâtiments high-poly, et se laisseront "cuire" gentiment vers le low-poly.

samedi 26 juin 2010

OpenSceneGraph et cache

C'est tout bête, et pourtant il m'a fallu tâtonner un petit peu. Par défaut, OSG recharge chaque ressource en un nœud complétement séparé, même si le fichier est le même. Changer mes 100 gratte-ciel identiques prenait donc environ 10 secondes, et faisait grimper la mémoire à 600 megs.

Perte de temps, perte de mémoire, et c'est exactement pour cela qu'il existe l'objet "osgDB::ReaderWriter::Options". Voyez plutôt:


osg::ref_ptr<osgDB::ReaderWriter::Options>
cachingOptions(new osgDB::ReaderWriter::Options);
cachingOptions->setObjectCacheHint
(osgDB::ReaderWriter::Options::CACHE_ALL);

...

osg::Node * node =
osgDB::readNodeFile("truc.osg", cachingOptions.get());


Et voilà comment passer de 10 secondes à un chargement presque instantané, et de 600 à 280 megs. Facile!