jeudi 24 octobre 2013

Les jeux qui m'ont marqué - Dungeon Master

Ah, le bon vieux Dungeon Master! Sorti sur Atari, ce fut un hit qui lança un genre à lui tout seul. Comme les Doom-like et les Warcraft-like, il y eut (et il y a, voyez la série des Diablo) les Dungeon Master-like.

Le principe: vous montez une équipe de 4 personnages à choisir parmi une vingtaine, et parcourez un donjon en tous sens pour y basher des créatures et récupérer un artefact puissant qui sauvera le monde. Là où Dungeon Master s'est démarqué de ses prédécesseurs, c'est dans la représentation 3D du donjon, et le jeu en temps réel. Pour ajouter à l'ambiance, les éclairages sont dynamiques (il faut récupérer des torches, ou apprendre à en créer des magiques), les seuls bruits sont ceux des monstres qui s'approchent, et le décor, quoi que répétitif, est vite angoissant.

En plus des monstres à dégommer, il faudra résoudre des énigmes de plus en plus complexes mettant en jeu des trappes, des clés, des passages secrets, des téléporteurs, augmenter l'expérience de ses personnages, et trouver de l'équipement.

Ajoutons que les 13 niveaux du jeux sont de véritables labyrinthes. Il m'a fallu cartographier les niveaux petit à petit, sur des doubles feuilles à grand carreaux, notant les monstres, les mécanismes divers... Sans compter que pendant que l'on note les détails de la carte, nos personnages ont faim et soif. Il faudra donc s'y prendre à plusieurs fois, tellement il est facile de perdre en tombant dans une trappe, en tombant à court d'eau, ou tout bêtement en ayant pas trouvé suffisamment d'équipement pour terrasser les monstres de plus en plus puissants.

Le système de magie était également novateur, avec un système de runes à invoquer. L'on trouve des parchemins contenant des formules, mais il est possible de deviner certains sorts: ainsi, "feu" fait apparaître une torche magique, mais "feu" puis "aile" envoie une boule de feu.

C'est probablement un de mes premiers flips vidéo-ludiques: tourner au coin d'un couloir glauque, se retrouver nez à nez avec une sorte de lézard avec des dents à la place du cou, repartir en courant dans l'autre sens, se perdre et se retrouver dans un cul-de-sac avec la bestiole qui s'approche... Ça marque! Et je dois avouer n'avoir jamais réussi à aller plus loin que le 4ème ou 5ème niveau, mon niveau d'anglais plus que limité à l'époque n'aidant pas à résoudre les énigmes ou à comprendre les sorts. Mais Dungeon Master reste le mètre étalon du genre: choix de personnages charismatiques, gestion de la nourriture et du sommeil, sorts avancés, équipements complexes, expérience gagnée au fur et à mesure dans les classes de prêtre, sorcier, combattant et ninja, niveaux tentaculaires, et tout cela sur une disquette de 720 ko!

vendredi 18 octobre 2013

Les jeux qui m'ont marqué - Another World

Développé par Éric Chahi, légende du jeu vidéo s'il en est, Another World est en (très) gros Prince of Persia chez les aliens. S'il possède la même vue de côté, la même fluidité de mouvements, il s'en démarque en revanche par une action plus variée entrecoupée de cinématiques en polygones, et bien entendu d'un univers complètement original.

Le gameplay est complètement old-school. Voyons à quoi ressemble le début de partie. Après une cinématique expliquant comment vous vous êtes fait transporter dans cet "autre monde", vous apparaissez dans une sorte de piscine glauque. Des algues apparaissent du bas de l'écran, vous attrapent. Fin de partie. Vous recommencez dans la piscine. Tentez les contrôles. Ah, on peut monter! Vous sortez de la piscine.

À gauche, un ravin. À droite, quelques ruines, d'où tombent des sortes de sangsues. L'une d'elle passe à proximité, et vous mord. Fin de partie, retour dans la piscine. Vous sortez, évitez les sangsues, et vous retrouvez nez à nez avec une sorte de sanglier furieux qui vous démolit. Fin de partie, retour dans la piscine. Retour devant le sanglier, vous repartez dans l'autre sens, ratez votre saut pour éviter les sangsues. Fin de partie, retour dans la piscine.

L'on meurt donc beaucoup, mais l'on progresse assez vite. De plus, l'action est vraiment variée, entre sauts, combats avec un pistolet à 3 modes (tir normal, bouclier, tir chargé) et énigmes. L'on se fera un allié d'un des autochtones, que l'on retrouvera à plusieurs moments de l'aventure.

L'on retrouve beaucoup de points de design qui ont depuis fait leur chemin, mais à l'époque étaient très novateurs: cinématiques non seulement au début, mais également au milieu de l'action, interface minimaliste sans barre de vie ni autres compteurs pour une meilleure immersion, l'exploration d'un monde cohérent et mystérieux... Another World m'avait complètement scotché, et me scotche encore.

mardi 8 octobre 2013

Generalized attributes

Quelles autres surprises g++4.8 nous réserve dans sa besace? Eh bien, une nouvelle fonctionnalité de C++11 est la gestion des attributes généralisés. L'idée est de permettre de spécifier un comportement via des directives, certaines standard, d'autres spécifiques au compilateur. La syntaxe est plutôt ésotérique: autant définir un attribut est trivial, puisqu'il s'installe [[entre double crochets]], autant le placement de l'attribut en lui même est moins évident puisqu'il va indiquer s'il s'applique à un type ou à une instance. Je vous renvoie aux exemples pour les détails sordides, intéressons nous plutôt aux attributs qui sont dès maintenant disponibles

Le premier de ces attributs est [[noreturn]], qui permet d'indiquer que la fonction ne retournera jamais (elle peut en revanche lancer une exception). Par exemple:

void runForEver [[noreturn]] ()
{
  while(1);
}

int main()
{
  runForEver();
  
  return 0;
}

L'utilité d'un tel attribut est de permettre au compilateur d'optimiser un pareil cas, en ne générant pas le code qui gère le retour de la fonction. D'ailleurs, si jamais vous vous amusiez à faire une fonction qui retourne bien qu'ayant l'attribut [[noreturn]], le verdict serait sans appel: d'abord un warning

attributes.cpp: In function ‘void runForEver()’:
attributes.cpp:3:1: warning: ‘noreturn’ function does return [enabled by default]
 }
 ^

Et ensuite, avec g++ tout du moins, un beau crash lorsque vous faites tourner le programme. Par contre, vous êtes tout à fait autorisés, comme indiqué précédemment, à lancer une exception:

#include <stdexcept>

void countToTen [[noreturn]] ()
{
  for(size_t i = 0; i < 10; ++i);
  throw std::runtime_error("End of the road");
}

int main()
{
  countToTen();
  
  return 0;
}

Les deux autres attributs sont [[final]] et [[align]]. L'attribut [[final]] sur une méthode virtuelle permet d'empêcher la redéfinition de cette méthode dans une classe fille, et sur une classe permet d'empêcher sa dérivation. Ces fonctionnalités sont déjà fournies par les explicit virtual overrides, décrits ici. Quant à l'attribut [[align]], il permet de définir l'alignement des données, ce qui est une fonctionnalité déjà fournie par une autre spécification. Comme d'habitude, le C++ fournit beaucoup trop de manières différentes de faire la même chose... Mais c'est pour ça qu'on l'aime?

jeudi 3 octobre 2013

thread_local

Voyons maintenant une autre fonctionnalité C++11 ajoutée dans g++ 4.8, longtemps attendue par les aficionados, et complètement ignorée par les autres: thread_local. Ce mot-clé s'ajoute devant une variable globale, variable statique, ou variable de classe statique, et indique que cette variable sera locale au thread, c'est à dire que chaque thread aura accès à son bout de mémoire propre. Prenons un exemple bête pour illustrer cela. Voici un programme qui fait tourner 4 threads, lesquels incrémentent une variable miaou, puis l'impriment. L'affichage est protégé par un mutex, mais pas l'accès à la variable. Puis, lorsque tous les threads sont complets, l'on affiche le résultat.

#include <thread>
#include <mutex>
#include <iostream>

std::mutex mutex;

int miaou = 0;

void run()
{
  for(size_t i = 0; i < 1000000; ++i) ++miaou;
  std::lock_guard<std::mutex> lock(mutex);
  std::cout << miaou << std::endl;
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  std::cout << miaou << std::endl;
  return 0;
}

Ayant fait tourner le programme, l'on obtient un résultat de ce type:

1164088
1177191
1229070
1222696
1222696

Les threads se sont battus pour la variable, et son évolution est donc plutôt ésotérique. Maintenant, passons miaou comme étant thread_local:

#include <thread>
#include <mutex>
#include <iostream>

std::mutex mutex;

thread_local int miaou = 0;

void run()
{
  for(size_t i = 0; i < 1000000; ++i) ++miaou;
  std::lock_guard<std::mutex> lock(mutex);
  std::cout << miaou << std::endl;
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  std::cout << miaou << std::endl;
  return 0;
}

Le résultat, cette fois-ci, est complètement déterministe:

1000000
1000000
1000000
1000000
0

Chaque thread a obtenu sa propre variable miaou, et l'a incrémenté jusqu'à 1000000. Le thread principal a également obtenu sa variable, et n'en a rien fait, sa valeur est donc 0.

Bien entendu, mon exemple est complètement artificiel. Quels pourraient donc être les utilisations de la fonctionnalité?

Gérer une mémoïsation thread safe, par exemple, peut être fait en utilisant une variable statique thread_local. Voyons donc le bon vieil exemple de Fibonacci mémoïsé:

#include <unordered_map>
#include <iostream>

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

int main()
{
  for(size_t i = 1; i <= 50; ++i)
  {
    std::cout << fib(i) << std::endl;
  }

  return 0;
}

Voilà un petit programme qui affichera les 50 premiers nombres de Fibonacci, transformant l'algorithme récursif usuel à complexité exponentielle en un algorithme à complexité linéaire (on laissera de côté l'algorithme linéaire sans mémoïsation, ainsi que l'algorithme logarithmique dont on parlera peut-être un autre jour). Rien que pour rigoler, enlevez la mémoïsation, et admirez votre CPU en train de souffrir.

Tout va bien jusque là? Alors voyons ce qu'il se passe lorsque vous avez plusieurs threads accédant à la même fonction.

#include <thread>
#include <mutex>
#include <unordered_map>
#include <iostream>

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

std::mutex mutex;

void run()
{
  for(size_t i = 1; i <= 50; ++i)
  {
    size_t f = fib(i);
    std::lock_guard<std::mutex> lock(mutex);
    std::cout << i <<  " " << f << std::endl;
  }  
}

int main()
{
  std::thread t1(&run);
  std::thread t2(&run);
  std::thread t3(&run);
  std::thread t4(&run);
  std::thread t5(&run);
  std::thread t6(&run);
  std::thread t7(&run);
  std::thread t8(&run);
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  t5.join();
  t6.join();
  t7.join();
  t8.join();
  
  return 0;
}

Le résultat est bien entendu indéfini, et en effet, en faisant tourner quelques fois, l'on obtient le cas où un thread accède à la map avant qu'elle ne soit mis à jour, et l'on obtient par exemple fib(50) = 2971215073 au lieu de 12586269025. Passez donc la map statique comme étant thread_local, comme ceci:

size_t fib(size_t n)
{
  if(n <= 2)
    return 1;
  
  thread_local static std::unordered_map<size_t, size_t> memo;
  auto result = memo.insert(std::make_pair(n, 0));
  if(!result.second)
  {
    return result.first->second;
  }
  else
  {
    return (result.first->second = (fib(n - 1) + fib(n - 2)));
  }
}

Maintenant, chaque thread a son propre cache, quel que soit le nombre de threads et le moment auquel ils ont été créés. L'on pourrait bien sûr partager le cache, au prix d'un mutex. Il est donc parfois plus efficace de donner son cache à chaque thread, ce qui est trivial avec le nouveau mot-clé.

Une autre utilisation possible pourrait être dans des routines de log, par exemple, chaque thread stocke les messages localement, et c'est uniquement lorsque le nombre de messages dépasse un certain seuil qu'un mutex global est pris et les messages envoyés vers l'écran ou dans un fichier. Ou encore, une fonction ayant besoin d'un buffer dynamique pourrait le déclarer en statique afin d'éviter une allocation si l'appel suivant n'a pas besoin d'un buffer plus grand, et être thread safe avec un buffer thread_local. Il n'y a plus qu'à essayer!

mercredi 2 octobre 2013

Inheriting Constructors

Avec g++4.8 qui vient de débarquer dans Debian Jessy, c'est l'occasion de se pencher sur les nouveautés C++11 de cette version du compilateur. On a vraiment l'impression que l'on racle les tiroirs du standard, parce qu'il ne manquait quand même pas grand chose. Cependant, une fonctionnalité intéressante débarquant dans 4.8 est la possibilité d'hériter un constructeur.

L'idée est qu'il est fréquent que les constructeurs d'une classe fille se contentent de passer leurs arguments à la classe mère. Dans ce cas, pourquoi s'embêter à re-déclarer le constructeur? En utilisant le mot-clé using, l'on peut donc tirer le constructeur dans la classe fille. Voyons donc un exemple.

#include 
#include 

class A
{
public:
  A(std::string a):
    _a(std::move(a))
  {
  }
  
private:
  std::string _a;
};

class B : public A
{
public:
  B(std::string b):
    A(std::move(b))
  {
  }
};

int main()
{
  B b("abc");
}

Rien de bien compliqué. Notez tout de même l'utilisation du passage par valeur du paramètre et du std::move, qui optimisent le cas où la valeur peut être déplacée. Eh bien, avec l'héritage de constructeurs, B devient simplement:

class B : public A
{
  using A::A;
};

Et ça marche exactement de la même manière. L'on imagine bien qu'avec un constructeur de classe de base prenant de nombreux paramètres, c'est beaucoup de code que l'on peut ainsi économiser.

Si A a plusieurs constructeurs, ils sont tous hérités (sauf le constructeur par copie et le constructeur par défaut, qui suivent les règles habituelles). Il est cependant possible de redéfinir un constructeur dans B avec la même signature, qui sera prioritaire sur les constructeurs hérités.