Une villa

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

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!

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.

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.

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!

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.

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.

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!

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.