Programmation

Emulateur Gameboy Flash

Comment retranscrire la magie d’un jeu tel que Super Marioland en flash ? En considérant le nombre de planques et le gameplay inimitable et old school, la magie du pixel art… Autant écrire un émulateur Gameboy, et charger la ROM !

Plus une sorte de défi Geek qu’un truc utile, ou même innovant (après quelques recherches on trouve même des émulateurs GB en JS), voila de quoi bien occuper quelques journées. Le résultat:

Tester l’émulateur Gameboy Flash

Je profite de cette expérience low-level pour faire quelques commentaires sur la programmation, bon ok le code de l’émulateur est plutôt sale et pourrait être optimisé (ce qui me prendrais beaucoup de temps pour juste refaire un travail déja existant), mais l’approche d’un processeur (équivalent au Zilog 80 pour les connaisseurs) tel que celui là et des techniques un peu roublardes de l’ASM pousse à se poser des questions.

Questions d’espace

Au final, le fichier SWF (Flash) obtenu pèse … aux alentours de 13K. Et la ROM de mario en fait 64K (seulement).

Un jeu, simple certes mais quand même aussi complet soit t-il et qui rentre au final sur moins de 100K, je ne sais pas ce que vous en pensez, mais je trouve ça plutôt impressionant. Imaginez que l’on essaie de faire la même chose entierement en flash, je vous garantie que vous dépasserez cette taille très très vite!

Notons que le processeur est un processeur 8bits et que les adresses sont codées sur 16Bits, ce qui ne fait que 64K adressable. Parmis les adresses accessibles, seulement 32K de la ROM sont visibles, il est nécéssaire pour les développeurs de switcher manuellement les morceaux de la ROM qu’il sera possible d’acceder à un moment donnée!

Les graphismes

Bien entendu, les développeurs de jeux Gameboy ne s’amusaient pas à écrire la tête de Mario pixel après pixel. Pour cela, ils utilisent des tiles. En gros, ce sont des motifs qui sont chargés dans une zone spéciale de la mémoire vidéo (videoram) et qui sont par la suite réutilisés dans le jeu. Voici une palette de Tiles extraite de Mario:

Tiles (motifs) utilisés durant une partie de Mario

Une fois ces tiles chargés, le jeu écrit un mappage de ces derniers dans une autre mémoire pour constituer une image avec. L’image crée ainsi est plus grande que celle de l’écran de la Gameboy, le jeu écrit aussi des valeurs (SCROLLX et SCROLLY) dans des registres spéciaux de manière à spécifier quelle partie doit être dessinée sur l’écran (ce qui permet d’anticiper les déplacement du joueur, en « scrollant l’image »).

Le hic, c’est que ces coordonnées X et Y peuvent être modifiées à tout moment, y compris pendant le tracé des lignes sur l’écran LCD. Prenons par exemple Mario, les informations en haut (Vies, score, temps etc.) restent fixe alors que le décor bouge lorsque vous vous déplacez, le jeu profite en fait d’une interruption spéciale se déclenchant exactement à la dernière ligne du bloc d »informations en haut pour changer les valeurs de SCROLLX et de SCROLLY. Roublards !

Un petit exemple

Bien Geek mais y’en a à qui ça fera sans doute plaisir, voici un morceau d’assembleur extrait du jeu Tetris que j’ai commenté:

000002CD:	LD A,(FF80h)	; Registre ou le jeu stocke
				; l'état des bouttons appuyés

000002CF:	AND 0Fh		; "Et" logique, pour qu'il ne
				; reste que les 4 derniers bits

000002D1:	CP 0Fh		; On le compare à %00001111
				; c'est à dire les 4 bits à 1
				; (Ici, A+B+START+SELECT)

000002D3:	JP Z,021Bh	; Si c'est égal, on saute en
				; 021B, qui est ici l'adresse
				; de réinitialisation du jeu

Maintenant, vous savez pourquoi quand vous appuyez sur A+B+START+SELECT sur GB, le jeu est réinitialisé!

La difficulté du débuggage

L’écriture d’un émulateur prend du temps et le débuggage peut par moment s’avérer extrement difficile. J’ai remarqué que la plupart de mes erreurs étaient dues à des OPCodes (instructions processeur) mal implémentées, faussant par la suite le comportement du jeu.

Au delà de ces instructions, il faut également vérifier que les registres gérés en temps normal par le processeur sont à peu près cohérents, ainsi en oubliant de mettre à jour un de ces registres incrémentés plusieurs milliers de fois par seconde (et servant en général de générateur pseudo-aléatoire), je me suis retrouvé face à un jeu de Tetris me servant toujours la même pièce !

Heureusement, j’ai pu profiter de plusieurs ressources:

Tetris ASCII

Pour les ennuyés du TTY voici un petit Tetris en mode console écrit en C.

Télécharger l’archive (Tetris-1.0.tgz)

La largeur et la hauteur sont modifiables directement (cf main.c). Vous pouvez également regarder le code source qui est normalement relativement propre et modifier les figures ou les niveaux !

Touches:

  • Q: Gauche:
  • S: Bas (acceleration)
  • D: Droite
  • [ESPACE]: Tourner

Les bases de données

Depuis de nombreuses années plusieurs concepts progressent concernant les bases de données, on peut cependant remarquer que, premièrement, le modèle relationnel est le plus largement utilisé, et ensuite que nous continuons d’écrire des requêtes SQL dans nos codes sources, mélangeant ainsi deux langages.

Resterons nous perpetuellement bloqué sur le modèle relationnel et ses jointures, ou trouverons nous un jour une façon plus simple d’appréhender un modèle de donnée complexe ?

Seul l’avenir répondra à cette question, mais pas forcément un avenir si proche qu’on le pense, en effet une thèse écrite en 1993 fait déja état des SGBD Orientés Objets et propose un concept de langage persistant, mais pourtant les bases relationnelles ne trouvent toujours pas de sérieux concurents. En attendant, voici quelques remarques et commentaires pratique sur l’utilisation des bases de données.

Modulabilité

Le premier problème posé est que nous utilisons d’un coté un langage (PHP, Java, C++ …) et d’un autre un SGBD (MySQL, PostgresSQL, Oracle…). Le traitement des données est donc doublement dépendant des technologies utilisées, car les requêtes sont spécifiques et diffèrent d’un SGBD à un autre. Les solutions d’interopérabilité sont assez intéréssantes, mais trouvent leurs limites. Il s’agit en général d’utiliser des classes spéciales du langage utilisé qui serviront en grande partie à la communication avec le serveur (intermédiaires).

Cette approche est appellée mapping objet-relationnel, autrement dit l’illusion d’utiliser une base de données orientée objet alors que tout est relationnel. Ces systèmes se nomment « ORM » (Object-relational mapping), on en trouve en PHP comme Propel, Doctrine ou pdoMap. Ainsi il est par exemple possible d’écrire:

$u = new User;
$u->prenom = "Jacques";
$u->age = 32;
$u->insert();

(L’ORM Est une classe abstraite de laquelle hérite User). Et l’ORM s’occupe automatiquement de générer les requêtes SQL correctes. Autre exemple:

$u = new User;
$u->get(35);
$u->age++;
$u->update();

Et pour les requêtes un peu compliquées, les ORM vont jusqu’à créer des langages, comme le JDOQL (Java) ou le DQL (PHP), qui servent à requêter non pas les bases de données mais les classes (ce qui engendre naturellement des requêtes vers la base, mais de manière opaque). Ces requêtes sont généralement plus courtes et plus expressives que le langage SQL.

On remarque ainsi plusieurs avantages:

  • La syntaxe du langage peut s’appliquer aux champs de la base (comme le « age++ »), la lisibilité du code ainsi obtenu peut être très bonne
  • Les fonctions SQL « CRUD » (Create, Retrieve, Update & Delete) se font très facilement, plus une seule ligne de code SQL à écrire
  • La syntaxe est en théorie la plus indépendante du SGBD possible, le concept « utopique » étant que le changement d’SGBD ne nécéssiterait que du bricolage dans l’ORM et non pas dans le code PHP
  • Les mêmes ORM sont parfois présents dans plusieurs frameworks, on retrouvera Propel dans Symfony par exemple
  • L’ORM peut servir d’intermédiaire pour établir des mécanismes de Cache

Mais aussi des inconvénients:

  • La gestion des bases de données complexes (ayant des multiples jointures) est assez peu aisée à manipuler
  • La lourdeur d’execution en prendra forcément un coup, ce type de classes faisant souvent appel à des accesseurs magiques ou à des éléments du modèle objet

Ce système permet aussi de profiter d’avoir des classes pour chaque table afin d’écrire des méthodes « custom ». Par exemple:

$u->addFriend($v);

Le découpage « un objet par table » prend généralement un sens assez pertinent.

Performances

Les performances sont aussi très importantes dans la communication avec un SGBD. Des politiques de mise en cache peuvent être adoptées. L’idée est assez simple, chaque requête du style « récupérer un enregistrement par sa clé » fait d’abord appel à une fonction du langage qui vérifie si le cache ne contient pas cet enregistrement.

Avantage immédiat, les enregistrements très récement et très souvent accédés restent « sous le coude ». C’est un peu comme si vous travailliez dans une grande bibliothèque, vous iriez chercher les trois livres dont vous avez besoin et vous les poseriez sur la table à coté de vous.

Ce mécanisme a été implémenté dans PHP par le biais d’APC (Alternative PHP Cache), qui permet de stocker ou de récupérer des éléments par leur index. Il existe aussi memcached, un serveur entièrement dédié à la mise en cache d’informations. Il est notament massivement utilisé par Facebook, le concept étant simple, on lui accorde une certaine quantité de mémoire et il se débrouille pour associer nos clés à nos données.

Autre détails, penser simplement à indexer la base de données sur les champs sur lesquels faire des recherches ou des jointures. Il faut parfois faire preuve d’un peu d’astuce pour parvenir à optimiser la base de manière à éviter les requêtes trop lourdes. Créer un Index « à chaud » peut être une opération très lourde, mais le gain par la suite sera forcément  très intéréssant.

Nouveau problème posé par ces mécanismes: la scalabilité. Imaginez que votre site web fonctionne bien et que vous vouliez supporter un plus gros traffic, le cache ne sera pas forcément très pratique, car il doit être global (d’ou l’interêt de memcache par rapport à APC par exemple)

Scalabilité

Voici une proposition de découpage possible assez arbitraire:

  • Un serveur executant le SGBD (prendre une grosse machine, car cette partie n’est pas facile à découper)
  • N Frontaux HTTP derrière un Rétro-proxy ou un load balancer
  • Eventuellement des frontaux dédiés aux fichiers statiques
  • Un ou plusieurs serveurs de cache (machines avec beaucoup de RAM, un processeur raisonable et un disque dur minimaliste)

La plus grande difficulté repose sur la répartition de la machine hébérgeant la base de données. Nous pouvons nous rassurer en nous disant que même des très grosses bases peuvent facilement tenir le coup pour peu qu’elles soient bien indexées, et que le réseau n’est pas un facteur très contraignant quant à la rapidité  (en LAN les performances sont plutôt bonnes entre les frontaux.

Maintenabilité

Un des concepts aussi employé dans les grosses architectures est l’éloignement de la base de données des serveurs applicatifs. Cet éloignement se fait par l’ajout de services, généralement conçus pour marcher via XML, et permet de garder la maitrise de l’ensemble des requêtes effectuées dans la base.

Ainsi les administrateurs de bases de données (DBA) entretiendront leur base et créeront des services associés à chaque type de requête qu’il sera possible de rencontrer. Ainsi les applications ne communiqueront jamais directement avec le SGBD mais avec des interfaces XML.

En conclusion, même si les bases relationelles restent franchement de la partie, un ensemble considérable d’outils et de couches qui viennent se greffer autour de ces derniers change l’environnement dans lequel les développeurs doivent évoluer.