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.