Projet Pac-Man

Le jeu utilisera le module Pyxel, qui s'appuie lui-même sur la bibliothèque SDL2, très performante.

Cahier des charges

Pour bien séparer le travail à faire, et pouvoir ensuite maintenir facilement le jeu, il sera séparé en 4 classes :

classe Labyrinthe pour gérer toutes les opérations relatives à la grille dejeu
classe Pac_man
classe Ghost, et des classes qui en héritent pour gérer les fantômes
classe Jeu pour le jeu lui-même

Il faudra réfléchir aux attributs et méthodes que devront posséder chacun de ces classes; ces attributs et méthodes pourront être introduits au fur et à mesure des besoins.

Rien ne vous empêche de créer d'autres classes additionnelles si vous en éprouvez le besoin : plus le script est modulaire, meilleur c'est !

Penser également à respecter le principe d'encapsulation des attributs en POO : les attributs d'une classe sont considérés comme privés, et ne peuvent donc pas être directement lus/modifiés par "l'extérieur" de la classe; il faudra donc prévoir des méthodes d'accès ( accesseur ou getter ) et de modification ( mutateur ou setter ) de ces attributs si besoin est...

Les fantômes, qui tentent d'attraper le Pac-Man, sont au nombre de quatre, chacun ayant une couleur et un comportement différent :

l'un se déplace complètement aléatoirement dans le labyrinthe
le deuxième se déplace en ligne droite et change de direction lorsqu'il rencontre un obstacle ( mur ou bifurcation )
le deuxième et le troisième poursuivent le Pac-Man avec des stratégies différentes : recherche du chemin le plus court pour l'un, et minimisation de la distance entre lui et le Pac-Man pour l'autre.

Vous pourrez bien sûr réfléchir à d'autres stratégies de comportement...

Le jeu pourra être plus ou moins élaboré selon le temps/les capacités du groupe : affichage plus élaboré, déplacements plus fluides, gestion d'un score, jeu multi-niveaux avec niveaux stockés dans des fichiers,...

Ébauche de code

Cette ébauche de code est fournie de manière à ne pas démarrer de 0...
Elle contient la structure de l'animation qui fera "tourner" le jeu, ainsi que le code créer et afficher le labyrinthe.

Il contient également des ressources à utiliser au besoin ( images ).

Déroulement du projet

Le labyrinthe

Le labyrinthe est représenté par une grille de 31 cases de haut par 28 de large.

Ce labyrinthe est codé par le tableau de tableau laby qui contient pour chaque case les valeurs suivantes :

0 pour une case vide
1 pour un mur
2 pour une gomme normale
3 pour une super-gomme ( qui déclenche le mode panique des fantômes )

Étudier le code de la méthode affiche de la classe Laby pour comprendre le fonctionnement de l'affichage du tableau de tableaux vers Pyxel; le principe mis en œuvre pourra être aussi utilisé pour l'affichage des autres éléments du jeu.

Le système de coordonnée de Pyxel a son origine dans le coin supérieur gauche de la fenêtre; l'axe des abscisses est orienté vers la droite, l'axe des ordonnées vers le bas.

Gestion du du Pac-Man

Principe

Le Pac-Man se déplace dans le labyrinthe à l'aide de 4 touches du clavier.

Il ne doit bien entendu pas pouvoir traverser les murs...par contre, de chaque côté du labyrinthe se trouvent deux zones qui lui permettent de passer directement de l'autre côté du labyrinthe.

Dans un premier temps, les déplacements ne se feront cependant pas "au pixel près" mais "à la case" de la grille, plus simple pour la détection de collisions.

Travail à faire

Compléter la classe Pac_man et le reste du code pour pouvoir afficher et déplacer le Pac-Man dans le labyrinthe.

Étudier dans la documentation de Pyxel la manière de tester l'appui sur une touche du clavier.

Dans le "vrai" jeu, Pac-Man avance automatiquement dans une direction tant qu'il ne rencontre pas un mur : il n'y a donc pas besoin d'appuyer constamment sur une touche pour le déplacer, mais uniquement pour le faire changer de direction; dans la méthode update de la classe Jeu, il doit donc y avoir un code qui fait "automatiquement" avancer le Pac-Man tant qu'il n'a pas changé de direction...

Les fantômes

Le gros du projet !

C'est là que vous allez mettre à profit vos connaissances sur les graphes et les parcours de graphes...

Principe

Dans le jeu original, il y a 4 fantômes qui ont chacun une couleur différente et une stratégie de déplacement qui leur est propre.

Blinky, le fantôme rouge, traque Pac-Man en le suivant partout à travers le labyrinthe.
Pinky, le fantôme rose, cherchera toujours à se placer DEVANT lui pour lui tendre une embuscade
Inky, le fantôme bleu, a la même stratégie que Pinky.
Clyde, le fantôme orange, a un déplacement purement aléatoire

Chacun de ces fantômes correspondra à une instance de la classe Ghost, dont hérite 3 autres classes ( vous pouvez en rajouter bien sûr...)

Les fantômes se trouvent initialement dans la "prison" au centre du labyrinthe. Ils se déplacent dans les couloirs mais ne mangent pas les gommes !

Les fantômes doivent se déplacer seuls dans le labyrinthe : c'est donc la fonction update qui va être chargée d'appeler régulièrement ( la "vitesse" est réglable ) les méthodes de déplacement des fantômes.

C'est pour les déplacements des fantômes que la vision du labyrinthe comme un graphe peut être utile : on peut procéder autrement, mais si vous voulez être proche du cours, il peut être intéressant de créer une structure de données de type graphe non orienté, où le sommets sont les cases du labyrinthes, et les relations le fait que l'on puisse passer d'une case à une autre.

Cette structure de données sera particulièrement utile pour connaître les déplacements possibles des fantôme ( ce seront les sommets voisins de la position actuelle du fantôme ).
De plus, cette structure de données sera créée une fois pour toute au début du jeu et non modifiée par la suite.

Algorithmes de déplacement

Pour simplifier un peu, on pourra utiliser les stratégies suivantes :

Déplacements aléatoire : le plus simple à coder. A chaque pas d’exécution, on choisit un sens de déplacement au hasard du fantôme.
Le risque : que le fantôme fasse plutôt du sur-place qu'un vrai déplacement...mais c'est très facile à coder !
Déplacements en ligne droite avec changement de direction à la rencontre d'un obstacle/d'une bifurcation : déjà un peu plus réaliste.
Le fantôme se déplace dans les couloirs tant qu'il ne rencontre pas un mur et/ou une bifurcation; à ce moment, il change aléatoirement de direction.
Le risque : que le fantôme fasse des aller-et-retours dans un même couloir et reste cantonné à une petite portion du labyrinthe.
Déplacement avec minimisation de la distance : l'idée est de calculer à chaque pas d’exécution la distance "à vol d'oiseau" ( donc sans tenir compte des obstacles ) entre le fantôme et le Pac-Man, et recherche la direction dans laquelle aller pour minimiser cette distance.
On peut utiliser le calcul de la distance de Manhattan, qui correspond bien à un déplacement dans une grille avec 4 directions possibles ( comme c'est le cas ici ), et qui est rapide à calculer.
Déplacement avec "traque" : le plus délicat...l'idée est d'utiliser un algorithme pour déterminer le plus court chemin qui existe entre le Pac-Man et le fantôme, et le faire suivre à ce dernier.

L'algorithme utilisée dans le "vrai" jeu pour la "traque" est l'algorithme A*, celui qui sert également dans les appareils GPS pour trouver le plus court chemin entre deux lieux.
C'est un dérivé de l'algorithme de Dijkstra, qui, lui, donne le plus court chemin entre un sommet et tous les autres sommets d'un graphe.

Vous pouvez vous essayer à l'implémentation de A*...ou utiliser l'algorithme de détermination du plus court chemin vu en cours !

Mais le plus court chemin complet ne nous intéresse pas ici, puisqu'il va changer à chaque fois que le Pac-Man va se déplacer; il nous faut simplement savoir dans quelle direction doit se diriger le fantôme pour se rapprocher du Pac-Man.
Voici une méthode :

à chaque déplacement du Pac-Man, on va établir une "carte des distances" du labyrinthe : on associe à chacune de de ses cases ( donc à chaque sommet du graphe ) sa distance la plus petite au Pac-Man.
Cette distance sera calculée en "nombre de cases à parcourir", et déterminée logiquement ( pourquoi ? ) par un parcours BFS du graphe.
pour se déplacer, le fantôme choisira alors d'aller sur une case accessible et dont la distance au Pac-Man est plus petite que la case sur laquelle il est actuellement.
en mode "panique", le fantôme choisira logiquement de s'éloigner du Pac-man, donc à aller sur une case de distance plus élevée !

C'est une méthode facile à implémenter, mais pas très efficace puisqu'il faut recalculer la "carte des distances" à chaque déplacement du Pac-Man...mais ça marche pas mal pour des labyrinthes ( et donc des graphes ) pas très gros comme c'est le cas ici.

Prolongements

Si vous étés arrivés là, c'est déjà bien !

Si vous avez du temps, vous pouvez implémenter les améliorations possibles : déplacement "au pyxel", score, autre labyrinthe, etc...