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!