Ces jeux qui m'ont marqué - A IV Network$

Prononcez A4 Networks, il s'agit d'une simulation économique dans laquelle vous prenez la direction d'une société de transports et d'investissements. Chaque carte représente une ville en 3D isométrique, dans laquelle vous pouvez ajouter des lignes de train et de bus et construire ou acheter des immeubles, golfs et autres. Chaque carte propose un défi particulier, comme de redresser le réseau de métro de Londres, ou de construire les îles Caïman à partir de zéro.

En tant qu'aficionado des jeux de gestion ferroviaire, je ne pouvais m'en passer et me jetais dessus quasiment dès sa sortie. Au final, c'est malheureusement un mauvais jeu, ce qui ne m'a pas empêcher d'y passer des heures. Et ses qualités tant ses défauts rendent son étude tout à fait intéressante. Voyons donc d'abord là où les développeurs se sont complètement plantés.

La simulation ferroviaire est ratée

Contrairement par exemple à Transport Tycoon, où les trains sont gérés via des signaux, et qui permettaient d'atteindre une complexité étonnante, les trains dans A4 Networks sont gérés par horaires: chaque train sait l'heure à laquelle il doit quitter la gare. C'est proprement ingérable, puisqu'il est très difficile de savoir si oui ou non deux trains vont se tamponner à un aiguillage, et impossible à forcer un train a prendre un côté plutôt qu'un autre dans une route à deux voies. Assez rapidement, l'on se retrouve à faire d'abord des lignes simples en point à point, et lorsque l'on commence à vouloir placer plus d'un train par ligne, à faire des lignes circulaires, sans aucun aiguillage.

L'alternance jour/nuit est gérée, mais elle est trop rapide par rapport à la vitesse des trains, ce qui rend impossible la gestion du rush hour. L'on tente donc d'avoir une densité de trains importante, en espérant qu'ils arrivent en gare au bon moment.

Le transport des marchandises est également sans queue ni tête: les trains de marchandises se remplissent à une gare, et se vident à la suivante, mais si par exemple une usine n'a pas eu le temps de se réapprovisionner, le train repart à vide, et se met à ramener les marchandises vers l'usine! Il faut manuellement aller inverser sa direction pour repartir dans le bon sens.

La simulation économique est ratée

Le jeu est très difficile à prendre en main, car les transports rapportent extrêmement peu par rapport à leurs coûts (ce qui est réaliste, ceci dit), jusqu'au moment où l'on se rend compte que par un curieux effet, le prix des immeubles s'écroule à chaque début d'année, vous permettant d'acheter quantité de bâtiments en solde, et de les revendre à 2 ou 3 fois le prix quelques mois plus tard. Une fois compris, ensuite, que l'impôt sur les bénéfices vous mettra vite sur la paille, et qu'il faut donc toujours investir tout son cash, la stratégie gagnante devient triviale: acheter le plus possible de bâtiments, les revendre juste avant le point de chute, et tout racheter. Ne vendre (et donc générer du cash) que pour construire autre chose, par exemple vos lignes de train. Au bout de quelques années, vous dépasserez les 2 milliards de cash, moment où l'entier 32 bits contenant votre argent durement gagné se retrouve tout d'un coup très négatif, vous forçant à une faillite prématurée. Dommage, non?

Évoquons à peine le mode bourse, qui fonctionne en dépit du bon sens. Certains scénarios demandent à obtenir une participation majoritaire dans plusieurs compagnies, mais il est parfaitement impossible de savoir quel est le pourcentage d'actions que l'on possède. En revanche, il est possible de se faire racheter, et donc de perdre au milieu du jeu sans pouvoir rien faire. La seule solution que j'ai trouvée est d'acheter ses propres actions dès qu'il y en a de disponibles.

Une antiquité à sa naissance

Graphiquement, ce n'est pas tout à fait ça. Alors qu'il est sorti plusieurs années après Transport Tycoon, la où TT proposait des animations et un scrolling de terrain fluide, A4 redessine péniblement la carte, carré par carré, à chaque recentrage, et les trains sautent de section de voie en section de voie. Alors certes, les cartes sont grandes, mais c'est très décevant.

Quel dommage!

Alors que beaucoup d'efforts et d'argent a été mis en œuvre pour la vidéo d'introduction avec James Coburn, l'on se dit que peut-être les designers auraient dû réduire leurs prétentions et sortir quelque chose qui marche. Parce que des points positifs, il y en a!

Une très grande liberté dans la pose des rails

Avec 3 niveaux en dessous du sol et 7 au dessus, l'on peut mettre les voies dans tous les sens: métros souterrains et aériens, croisements multiples, c'est un vrai plaisir.

Une ambiance particulière

L'alternance jour/nuit avec les dernières lumières dans vos gares, la musique d'ambiance pour chaque saison, et, paradoxalement, la sensation de vide qui vient du manque d'animations (les seules choses qui bougent sont vos propres véhicules), rend une atmosphère hors du temps, un peu bizarre, et très propice aux longues séances de jeu.

D'avoir proposé des scénarios basées sur de vraies villes est également un plus: l'on peut bidouiller le métro de Paris, développer New York ou Vienne.

Le nombre de bâtiments différents est également très important, et permet des villes variées. L'on pourra ainsi développer un quartier entier en s'assurant qu'il est bien desservi en transports, y installer quelques commerces, puis des bâtiments plus importants.

Une approche économique sérieuse

Quand bien même la simulation est défectueuse, l'idée de départ était bonne. Les rapports sont complets, le bilan de fin d'année est remarquable, et l'on gagne vraiment à les étudier en détail.

Face au mastodonte qu'est OpenTTD, la référence en gestion de transports, et, à mon humble avis, la référence tout court en matière de jeux libres, beaucoup de jeux font aujourd'hui pâle figure. A4 Network$ aurait pu connaître plus de succès sans ses nombreux bugs, mais il apparaît aujourd'hui bien plus dépassé que de nombreux jeux d'époque. Notons que la série des A-Train à laquelle appartient A4 continue de s'étendre, le dernier né de la série, A-Train 9, est sorti en 2010, dans la discrétion la plus absolue.

Ces jeux qui m'ont marqué - Railroad Tycoon

L'ancêtre des jeux de train! Railroad tycoon, sorti en 1990 et qui tournait comme une bête sur mon 386 portable monochrome (eh oui, ça existait!) et tenait à l'aise sur une disquette, proposait au joueur de devenir un magnat du rail aux États-Unis, au Royaume-Uni, ou en Europe.

Le joueur peut donc installer ses rails et ses stations à travers la carte pour relier les villes et les industries et tenter d'optimiser son réseau pour maximiser les profits, en bon capitaliste qui se respecte. Au fur et à mesure du temps, de nouvelles locomotives plus performantes voient le jour, tandis que de nombreux compétiteurs installent eux-mêmes leurs réseaux.

Les contrôles sont fins, et il est possible de donner des ordres complexes à ses trains, comme par exemple de zapper les petites stations.

Le jeu est bourré d'humour, avec des titres de journaux délirants qui apparaissent régulièrement, les commentaires de fin d'année (mes actionnaires étaient apparemment "outrés" de mes résultats) ou encore la fin du jeu, où l'on obtient une certaine retraite en fonction de l'argent récolté (si l'on finit dans le noir, l'on se voit notifié une reconversion en ramoneur!).

Une autre très bonne idée est d'avoir fourni de vraies zones du monde pour jouer: il est très plaisant de créer sa ligne Paris-Lyon, ou encore de creuser sont tunnel sous la manche.

Le jeu est maintenant disponible gratuitement en abandonware, il tourne très bien sous DosBox. Une fois passé la première impression (c'est quand même assez moche), les vieilles sensations sont de retour.

Où l'on reparle des heuristiques

J'ai eu l'occasion récemment de me remettre aux heuristiques des fonctions Postgresql, que j'avais mentionnées dans un post précédent

Voyons le problème: l'on a un certain nombre de valeurs que l'on veut rechercher dans une grande table. On insère donc ces valeurs dans une table temporaire, et l'on fait une jointure. En fonction du nombre de valeurs dans la table temporaire, le planificateur de tâches va soit utiliser l'index, soit ordonner la table temporaire et faire un merge join. Sauf que depuis l'application, l'on prépare le plan à la première exécution, et l'on a donc aucune certitude sur le plan choisi. Pire, souvent les premières requêtes chargent un grand nombre de valeurs, et optimisent donc le plan pour ce cas, alors qu'ensuite le système se stabilise sur de toutes petites recherches, qui prennent donc beaucoup plus de temps.

create table data(i integer not null);
insert into data select generate_series(1, 1000000);
create index data_idx on data(i);

create temp table search(i integer not null);
insert into search select generate_series(1, 1000);
analyze search;
select d.i
from data d
join search s on d.i = s.i

truncate search;
insert into search select generate_series(1, 1);
analyze search;
select d.i
from data d
join search s on d.i = s.i

L'on pourrait empêcher la préparation du plan, ce qui oblige l'application à différencier entre les requêtes que l'on peut préparer et les autres. Mais il y a aussi une solution: doucement orienter le planificateur de requêtes vers le plan le plus efficace en moyenne, à l'aide d'une fonction et de hints bien choisis.

create or replace function get_search() 
returns table(i integer) 
rows 1 
volatile as
$$
 select * from search;
$$ language sql;

truncate search;
insert into search select generate_series(1, 100000);
analyze search;
select d.i
from data d
join get_search() s on d.i = s.i

L'on aura beau mettre autant de lignes que l'on veut dans la table search, le plan passera toujours par l'index de la grande table:

Postgresql - Arguments nommés

Je ne m'en étais même pas rendu compte: Postgresql 9.2 permet maintenant d'utiliser des paramètres nommés au sein de ses fonctions, en place des paramètres positionnels. C'est à dire qu'avant, il fallait écrire:

create function myadd(int, int) returns int as
$$
 select $1 + $2;
$$ language sql;

Mais maintenant, l'on peut écrire:

create function myadd(x int, y int) returns int as
$$
 select x + y;
$$ language sql;

Ce qui est quand même nettement plus lisible, non?

Un coalesce en colonnes

Ça faisait longtemps que l'on avait pas fait de SQL, non? Alors, petit exercice. Soit une table contenant pour chaque date le nom d'un champ qui change de valeur, et sa nouvelle valeur. Comment transformer cette approche historique en approche par état, où l'on voit à chaque instant la valeur de chaque champ?

Tout d'abord, créons la table.

create table history(t serial, field text, value integer);
insert into history values(default, 'a', 1);
insert into history values(default, 'b', 12);
insert into history values(default, 'a', 3);
insert into history values(default, 'c', 101);
insert into history values(default, 'b', 12);
insert into history values(default, 'b', 14);
insert into history values(default, 'a', 3);
insert into history values(default, 'a', 1);
insert into history values(default, 'c', 102);
insert into history values(default, 'a', 2);
insert into history values(default, 'b', 13);

Pour visualiser la valeur de chaque champ, on donnera à chaque champ sa colonne, pour l'associer à l'ensemble des moments qui nous intéressent. Une jointure gauche s'impose donc:

select m.t, a.value as a, b.value as b, c.value as c
from history m
left outer join history a on m.t = a.t and a.field = 'a'
left outer join history b on m.t = b.t and b.field = 'b'
left outer join history c on m.t = c.t and c.field = 'c'
order by m.t


t
a
b
c
1
1

2
12

3
3

4
101
5
12

6
14

7
3

8
1

9
102
10
2

11
13

C'est à peu près ça, sauf qu'il faut maintenant remplir les vides avec la dernière valeur disponible. Une sorte de coalesce, mais vertical.

Les sous-requêtes viennent rapidement à notre aide: pour chaque champ, l'on veut récupérer la dernière valeur en ordonnant par le temps, ce qui est facile grâce à limit. Voici donc:

select
 m.t,
 (select value from history h 
  where h.t <= m.t 
  and field = 'a' 
  and value is not null 
  order by h.t 
  desc limit 1) as a,
 (select value from history h 
  where h.t <= m.t 
  and field = 'b' 
  and value is not null 
  order by h.t desc 
  limit 1) as b,
 (select value from history h 
  where h.t <= m.t 
  and field = 'c' 
  and value is not null 
  order by h.t desc 
  limit 1) as c
from history m


t
a
b
c
1
1

2
1
12

3
3
12

4
3
12
101
5
3
12
101
6
3
14
101
7
3
14
101
8
1
14
101
9
1
14
102
10
2
14
102
11
2
13
102

Byzance! Mais arrêtons nous un instant: n'est-ce pas terriblement inefficace d'avoir des sous-requêtes dans le select? Peut-on trouver une autre solution, en utilisant par exemple des window functions? Ça vaut la peine d'essayer. Je ne crois pas qu'il existe de window function qui remplisse exactement ce rôle, mais une approche possible consiste à commencer par écrire la requête qui a un t donné donne le dernier t disponible pour le champ, en demandant à la window function d'aller chercher le max(t) pour un champ donné. La fenêtre par défaut allant jusqu'à la ligne courante, et les entrées nulles de notre jointure gauche étant par définition plus petites que le temps précédent, ça marche plutôt bien:

select 
 m.t, 
 max(a.t) over (order by m.t) as a,
 max(b.t) over (order by m.t) as b,
 max(c.t) over (order by m.t) as c
from history m
left outer join history a on m.t = a.t and a.field = 'a'
left outer join history b on m.t = b.t and b.field = 'b'
left outer join history c on m.t = c.t and c.field = 'c'
order by m.t


t
a
b
c
1
1

2
1
2

3
3
2

4
3
2
4
5
3
5
4
6
3
6
4
7
7
6
4
8
8
6
4
9
8
6
9
10
10
6
9
11
10
11
9

Une fois que le temps attendu est disponible dans sa colonne, il est trivial d'obtenir la solution en joignant la table ainsi créée avec la table "history", pour chaque champ, afin d'en retrouver la valeur. La requête a pris du poids:

select h.t, a.value, b.value, c.value
from
 (select 
  m.t, 
  max(a.t) over (order by m.t) as a,
  max(b.t) over (order by m.t) as b,
  max(c.t) over (order by m.t) as c
 from history m
 left outer join history a on m.t = a.t and a.field = 'a'
 left outer join history b on m.t = b.t and b.field = 'b'
 left outer join history c on m.t = c.t and c.field = 'c'
 order by m.t) as h
left outer join history a on h.a = a.t and a.field = 'a'
left outer join history b on h.b = b.t and b.field = 'b'
left outer join history c on h.c = c.t and c.field = 'c'
order by t

Alors, est-ce plus rapide que l'approche par sous-requêtes dans le select? Malheureusement, non... Je m'attendais à une grosse différence, mais le planificateur de requête est loin d'être bête, et avec les bons index, les deux approches se valent, avec un léger avantage pour l'approche par sous-requête.

En cadeau bonus, cependant, le plan de notre dernière requête:

Bug, partie 2

Je l'ai trouvé! Une saleté de race condition qui m'a bien pourri la vie pendant 4 jours. Nous avons en effet dans le code le concept de souscription via callbacks vers des objets, et mon code en regardait la valeur avant de souscrire: résultat, si l'état changeait entre le moment où l'on regarde la valeur, et le moment où l'on souscrit, boum, un trou, et l'on restait sur l'ancienne valeur. Il a suffi d'utiliser une autre primitive qui permettait de souscrire et de récupérer la valeur atomiquement, et tout est rentré dans l'ordre.

Cela me rappelle un autre bug qui m'avait également tenu en haleine pour un bon bout de temps: au final, c'était juste une fonction de hachage qui avait un buffer marqué par erreur comme "static", c'est à dire grosso modo global. Cela rendait la fonction non ré-entrante, et causait donc des erreurs de lookup dans les tables de hachage lors des pics de charge.

Bug

Je le traque depuis plusieurs jours. Au début, je n'avais aucune idée de l'animal que je poursuivais, je ne retrouvais que les dégâts causés bien après son passage, de sorte qu'il m'était impossible de l'attraper. Pendant près d'une journée, je me suis complètement fourvoyé sur des traces que je pensais être à lui, mais j'ai fini par me rendre compte que ces traces étaient normales et que c'était juste une fausse piste.

Alors j'ai posé des pièges. Je sait par où il passe, et je voulais tenter d'en apprendre plus. J'ai confectionné, puis tendu mes filets, hier vers 11h. Puis je suis parti rejoindre des collègues à Borough Market, et mangé d'excellentes pâtes au sanglier, suivies d'un bretzel (ohhh...) et d'un morceau de tarte au chocolat (ahhhh!). Je suis revenu, et j'ai regardé si j'avais été chanceux.

Je ne trouvais que quelques crottes insignifiantes, l'animal était bien passé par là mais n'avait rien laissé d'utile. Je vaquais donc à d'autres occupations, et vérifiais vers 16h. Bingo! Non seulement il était passé, mais il m'avais laissé une magnifique trace, que je m'empressais d'étudier.

Hier soir, j'en savais beaucoup plus sur l'animal. Pas suffisamment pour savoir exactement ce que c'était, et donc m'en débarrasser, mais assez pour sérieusement raffiner mes pièges. J'ai bon espoir de l'attraper Lundi.