2D Engine + Tetris AI

Début : Octobre 2013
Durée : 2 mois
Langage : C++
Bibliothèques/Outils : SDL2

Lien vers une vidéo du jeu
Lien vers une vidéo de l’IA

Lien vers le code source
Lien vers la documentation du code
Lien vers le dossier complet

Dans le cadre d’une matière de Programmation Orientée Objet à l’université de Strasbourg, nous avons reçu pour travail de développer le jeu Tetris et d’en réaliser une intelligence artificielle. Notre premier but était donc de réaliser le jeu, puis de concevoir une IA originale capable de tenir le plus longtemps possible en ne connaissant aucune pièce à l’avance. Une des contraintes importante était que le programme de l’IA devait être complètement indépendant du programme gérant le jeu, il nous fallait donc nous assurer de créer une communication entre les deux composants.

Ayant acquis de nombreuses connaissances pendant l’été en travaillant avec le livre Game Coding Complete, j’ai décidé de profiter de ce projet pour m’essayer à la création d’un petit moteur de jeu 2D. J’ai donc passé un mois et demi à développer exclusivement des outils qui permettraient ensuite la création du jeu. Le moteur se base sur les principes suivants :

• Un système de Process permettant la création de tâches qui se déroulent sur plusieurs frames. Chacun de ces Process est mis à jour à chaque frame en lui donnant la valeur du temps écoulé depuis la dernière frame et permet donc la création d’animations, de processus de gameplay, etc. La force de ce système réside surtout dans le fait de pouvoir créer des chaînes de Process, qui s’exécuteront alors successivement.
• Un système d’Event permettant de créer des événements et de les propager dans le système. Une classe EventManager gère une liste d’objets attachés à chaque type d’événement et appelle les méthodes de ces objets via un système de callback lorsqu’un événement est propagé (utilisation de la bibliothèque fastdelegate).
• Un système d’affichage graphique gérant le chevauchement des éléments graphiques grâce à une valeur de layer. Il est ainsi possible d’afficher du texte, des images avec ou sans transparence, et d’effectuer de multiples transformations et changement de couleurs (utile pour les animations).
• Un système de communication utilisant les sockets et le protocole TCP/IP pour dialoguer. Ce système permet de sérialiser des événements et de les envoyer à un programme distant. Ces événements seront ensuite propagés dans le programme d’arrivée (par exemple, le programme IA peut propager des événements d’inputs au programme du jeu Tetris).

Tous les détails ne sont pas donnés ici, tels qu’un système d’allocation de ressources, de debugging, etc.

Une fois la conception du moteur terminée, j’ai travaillé de pair avec Stan Wilhelm pour réaliser le gameplay du jeu, ainsi que les différentes animations que nous tenions à implémenter. Le moteur s’est alors révélé très pratique à utiliser, le découpage en Process rendant le travail facile. Au final, les conseils donnés dans Game Coding Complete étaient d’une grande pertinence et je fus impressionné du résultat. Ainsi, coder le gameplay n’aura pris que peu de temps et nous nous sommes ensuite attaqués à la partie IA.

Bien que l’affichage du jeu révèle une pièce d’avance au joueur humain, l’IA ne dispose pas de cette information et doit trouver la meilleure action à effectuer pour chaque nouvelle pièce. Une fois qu’il reçoit l’information de la grille du Tetris et de la nouvelle pièce, le programme de l’IA teste toutes les positions possibles et attribue un score à ces configurations. Il effectue ensuite simplement l’action qui aura obtenu le meilleur score et attend la pièce suivante.

La partie la plus importante de l’IA réside donc dans la façon dont le score de chaque position est déterminé. Il s’agit de vérifier différents critères et d’attribuer un poids à chacun d’entre eux. Les critères utilisés pour cette IA comprennent donc entre autres la hauteur résultante de la grille, le nombre de trous générés (nombre de cases rendues inatteignables pour d’autres pièces), etc. Au final, notre IA aura présenté les meilleurs résultats de notre classe, réussissant à éliminer jusqu’à 15000 lignes avant de perdre.

Ce projet aura été extrêmement enrichissant. Le développement du moteur m’aura permis de mettre en pratique les connaissances que j’avais pu acquérir tout au long de l’été et de vérifier leur utilité. De plus, nous avons pu nous essayer à la programmation d’une IA pour Tetris, et réussir à obtenir des résultats satisfaisants. Au final, de nombreuses améliorations peuvent être apportées au moteur comme au jeu. Je n’ai par exemple pas eu le temps de développer un système sonore, le jeu se trouvant donc sans aucune musique ou bruitage. De plus, l’utilisation du moteur pour coder le jeu m’aura donné des idées d’améliorations, telles que des possibilités de propagation d’événement lorsqu’une animation se termine, par exemple. En tout les cas, j’ai pris un réel plaisir à développer ce jeu, surtout la partie moteur dont je pourrais reprendre certaines parties dans des développements futurs. Le jeu est certes loin d’être abouti mais reste, en termes de code, une des architecture les plus intéressante qu’il m’aura été donné de réaliser.

Reading time !

L’année 2013 m’aura permis de découvrir de nombreux livres très intéressants et j’ai pensé qu’il serait pertinent de les présenter ici. Je commencerais donc par présenter le livre qui m’a servi de référence lors du stage avec OpenGL, avant de vous présenter deux autres livres plus en rapport avec le développement de jeux.

Avant mon stage de l’été 2013, j’avais beaucoup de mal à comprendre les versions OpenGL modernes et c’est pour cette raison que je me suis muni de ce livre. Je ne l’ai pas parcouru dans son intégralité mais de nombreux chapitres m’auront été très utile. Il présentait notamment l’avantage d’être un des seuls livres traitant de fonctionnalités très récentes comme les shaders de Tesselation. Il n’est peut-être plus le seul à l’heure qu’il est, cependant il reste pour moi un livre très instructif et fourni d’exemples très pratiques.

 

 

Ce second livre m’aura énormément appris sur le C++. Il est très bien écrit et très détaillé sur toutes les fonctionnalités qu’offrent le langage. Je m’attendais à ce que certains sujets relatifs à la programmation de jeux soient abordés plus en détails, et c’est peut-être mon unique reproche. Cependant, il reste très centré sur le jeu vidéo car il décrit chaque fonctionnalité du langage avec diverses anecdotes et en restant orienté sur les objectifs de développement d’un jeu : mémoire, performance, astuces de développement dans un studio… C’est un livre qui m’aura donné de bons réflexes et qui aura grandement amélioré ma connaissance du langage et de la programmation orientée objet.

 

Ce dernier livre aura été le plus enrichissant de tous et je le considère comme une véritable mine d’or. Il traite de très nombreux sujets du développement de jeux (graphisme, physique, langages de script, etc.) en détaillant la mise en place d’un moteur de jeu. Un code source de ce moteur est d’ailleurs disponible afin de permettre au lecteur de suivre les différents chapitres tout en comprenant l’implémentation en C++. J’ai passé la plupart de mon temps libre à lire ce livre lors de l’été 2013 et ç’aura été une incroyable découverte. J’ai d’ailleurs suivi le livre tout en reprenant moi-même le code afin d’être certain de ne perdre aucune subtilité dans l’implémentation des divers composants. J’ai aussi adoré l’approche des auteurs qui consiste à ouvrir le lecteur au travail en équipe et ainsi aux divers métiers du jeu vidéo (un programmeur ayant nécessairement besoin de communiquer avec artistes, game designers, etc.). Ce livre aura clairement changé mon approche dans la programmation de jeux. J’ai adopté la plupart des recommandations des auteurs et je ne saurais trop les remercier de partager leur expérience.

Au final, chacun de ces livres m’aura été d’une aide précieuse. Je pensais éprouver des difficultés à lire de tels ouvrages (qui plus est en Anglais) mais j’ai au contraire trouvé beaucoup de plaisir pour ce genre de lecture. J’espère avoir l’occasion de lire des livres tout aussi intéressants à l’avenir.

Stage ICube

Début : Mai 2013
Durée : 2 mois
Langage : C++
Bibliothèques/Outils : OpenGL 4

Lien vers le rapport de stage détaillé

À la fin de ma seconde année en Licence à Strasbourg, j’éprouvais le besoin de trouver un stage afin d’acquérir des connaissances utiles à la création de jeux vidéo et d’obtenir une expérience professionnelle. J’en parlais alors à l’un de mes professeurs qui me conseilla de regarder les offres de stage du laboratoire ICube, situé à Illkirch, non loin de Strasbourg. C’est en discutant avec un des chercheurs, M. Thery, que je décidais d’y faire un stage, le sujet traitant de programmation 3D en utilisant OpenGL « moderne ».

Avant d’entreprendre ce stage, j’avais déjà passé beaucoup de temps à l’apprentissage d’OpenGL. J’avais pour cela suivi plusieurs tutoriels, expérimenté la création de quelques scènes 3D basiques et lu plusieurs articles sur l’utilisation des dernières versions d’OpenGL.

Le but du stage concernait « l’évaluation et le rendu de surfaces de Bézier via calcul GPU« . Il m’était alors demandé d’utiliser plusieurs fonctionnalités d’OpenGL afin de proposer plusieurs versions du calcul de surfaces. J’ai donc pu réaliser 4 versions différentes :

• Une version « standard » n’utilisant aucune fonctionnalité avancée d’OpenGL. Cette version était nécessaire pour effectuer une comparaison avec les autres techniques.
• Une version utilisant un calcul effectué grâce au Vertex Shader.
• Une version utilisant un calcul effectué grâce au Tessellation Shader.
• Une version utilisant le « Transform Feedback« .

Il m’aura aussi été demandé de réaliser plusieurs méthodes de rendu comme le Gouraud Shading ou Phong Shading. Plus de détails concernant mon travail et les descriptions complètes des diverses versions développées sont disponibles dans mon rapport de stage.

Ce stage m’aura énormément apporté. J’ai pu largement consolider mes connaissances en programmation 3D, découvrir des méthodes de rendu ainsi que des fonctionnalités avancées d’OpenGL. Je garde un très bon souvenir de ce stage, qui m’aura permis d’éprouver mes limites et de m’améliorer en programmation 3D et orientée objet.

Filtre de Sobel

Début : Mars 2013
Durée : 2 semaines
Langage : Assembleur MIPS
Bibliothèques/Outils : MARS MIPS Simulator

Lien vers le code source

Ce travail a été réalisé dans le cadre du cours « Architecture des Ordinateurs » que j’ai pu suivre à l’université de Strasbourg. Stan Wilhelm et moi-même avons travaillé en binômes sur ce projet. L’objectif était de réaliser un programme en langage assembleur permettant d’appliquer un renforcement des contours sur une image. Celle-ci devait avoir un format BMP et ses couleurs devaient être codées sur 8 bits.

Afin de renforcer les contours d’une image,  il est nécessaire d’utiliser des matrices de convolution. Ces matrices servent à obtenir deux gradients, qui sont en fait deux images contenant des informations concernant la dérivée horizontale et verticale en chaque point. L’addition de ces deux images et un seuillage des couleurs permet d’obtenir le résultat suivant :

                    

Nous avons fait en sortes que ce programme fonctionne aussi avec les images dont les couleurs sont codées sur 4 bits et 1 bit. Nous avons aussi réalisé d’autres filtres rapides, qui n’impliquaient qu’une légère modification des matrices de convolution.

Ce projet aura vraiment été très intense. Nous n’avions en effet que 2 semaines pour appliquer ce que nous apprenions du cours sur le langage MIPS donné dans le même laps de temps. Ainsi, nous avons appris à correctement structurer notre code en blocs de fonctions au milieu du développement, ce qui nous a forcé à reprendre certaines parties du code plusieurs fois. Débugger le programme aura aussi été plus difficile qu’à l’accoutumée, bien que l’utilitaire MARS se soit avéré d’une grande aide.

Au final, je suis content d’avoir pu découvrir un code beaucoup plus bas niveau afin de mieux comprendre le fonctionnement des programmes en général. De plus, j’ai appris quelques bases sur le traitement d’images, via les divers filtres et matrices de convolution. Ce projet aura été vraiment difficile mais s’est avéré être un défi plaisant à relever.