Attention, pour lancer le PloucMan en mode graphique, il vous faudra au minimum la version 2.6.x.x de GTK (téléchargeable sur ce site : www.gtk.org).

Sommaire :Sommaire :

Conclusion sur le projet tutoré

Le programme (acces aux sources)

Sujet :Sujet :

1. Introduction

Tout le monde a le même sujet : il s'agit du défi PloucMan. PloucMan est un jeu dérivé de PacMan. Un personnage (PloucMan) dont nous maîtrisons uniquement la direction de déplacement doit manger un certain nombre de PloucGommes. A chaque fois qu'il en mange une, sa vitesse de déplacement augmente légèrement. Des monstres sont là pour le déranger et à chaque fois que l'un d'eux est trop près, un malus est appliqué. La partie se termine quand toutes les PloucGommes sont mangées. On fait alors le compte :

Du nombre de pas de temps qu'il a fallu (t)
Du nombre de malus (m)

Sachant que l'air de jeu possède une taille T, le score s est calculé ainsi :

Le score est donc d'autant plus grand que le temps et le malus sont faibles.

2. Le défi

Le défi se compose de deux parties :

Une partie jeu où nous devons essayer de faire le meilleur score à notre algorithme.
Une partie interface graphique où nous devons essayer de faire l'interface la plus jolie possible.

2.1. Jeu

Une interface de programmation nous est fournie pour qu'en fonction de :

la position du PloucMan
la position des PloucGommes
la liste des PloucGommes déjà mangées
la position des monstres
la taille de l'aire de jeu
votre vitesse

Nous puissions décider de la direction à prendre (un angle).
L'interface de programmation est fournie en annexe.

2.2. Interface graphique

Un module d'interface graphique nous est fourni pour que nous puissions, en fonction des mêmes paramètres précédents, dessiner dans une zone graphique à l'aide de primitives GTK/GDK. L'interface de programmation nous est fournie en annexe.

3. Notation

La note finale sera composée de quatre parties :

Note technique (score moyen obtenu sur un jeu de tests). Maximum 5 points.
Note de suivi de l'encadrant (5 points). Assiduité et sérieux font partie des critères.
Note esthétique de l'interface (5 points).
Note de présentation finale (5 points). Nous devrons faire une présentation de notre projet tutoré sous la forme d'une page web.

La qualité de présentation, la clarté, ainsi que l'originalité des solutions font partie des critères de notation.

L'équipe :L'équipe :

1. Présentation des membres

1.1. MONTE Nicolas

Chef de projet.
Réalisation de l'interface graphique.
Rédaction et réalisation du compte rendu.
Participation à la mise en place de l'algorithme de recherche.

1.2. VILLAIN Francois

Réalisation de l'algorithme de recherche et participation à la création des schémas pour le compte rendu.

1.2. OLAGNON Loic

Réalisation de l'algorithme de recherche.

2. Les moments forts

Debut février : Création du premier algorithme de recherche. Le PloucMan se dirige vers la gomme la plus proche de lui (score amélioré de plus de 500%).
Mi février : Insertion de la première image dans l'interface graphique.
Fin février : Interface graphique version 1 terminé.
Début Mars : Mise en place des animations dans l'interface graphique. Interface graphique version 2 terminé.
De Mi Mars à Mi Avril: Calme plat sur le projet.
Mi Avril : Première version de l'interface version 3.
Fin Avril : Mise en place du nouvel algorithme de recherche (Panique à bord score maxi de 0.05).
Début Mai : Algorithme presque débogué et commencement de la rédaction du compte rendu.
Mi Mai : Rendez-vous avec notre encadrant, le chef de projet n'est pas présent lors de l'entrevue. Résultat, le PloucMan fait la tête et ne veut pas se lancer sur les PC de la salle 108.
Fin Mai : Réécriture entière de l'algorithme de recherche et amélioration de l'interface graphique.
Début Juin : Optimisation des fonctions d'affichages pour que le PloucMan aille plus vite sur des PC moins puissants. Optimisation de l'algorithme de recherche pour gagner quelques dizièmes de points.

Module de déplacement :Module de déplacement :

1. Partie Technique

1.1. L'idée:

Après avoir réalisé un premier algo très simple permettant au PloucMan d'aller manger les gommes les plus proches de lui, nous avons remarqué qu'il se faisait littéralement dévorer par les montres. En étudiant un peu la stratégie de ces monstres, nous avons remarqué que beaucoup étaient limités dans leur déplacement. Certains suivent une trajectoire horizontale, d'autre verticale et ils ne peuvent sortir d'une zone située au centre du jeu.
Nous avons donc décidé de diviser la zone de jeu en neuf zones, elles mêmes divisées en deux pour les zones au bord du plateau et en quatre pour la zone centrale :

L'idée de notre algo est de nettoyer les zones du bord pour prendre de la vitesse en se faisant ainsi moins toucher par les monstres (car beaucoup sont bloqués dans la zone centrale). Puis ensuite, de s'attaquer au nettoyage de la zone centrale avec un PloucMan qui va plus vite que les monstres.

1.2. Description de l'algorithme:

Première étape nous comptons le nombre de cibles par zone en appelant la fonction int ChercheGommeZone(Info * info) qui enregistre le nombre de gommes par zone dans la structure "perso" de "info" dans un tableau d'entiers int nbre_gomme_zone[12].

Ensuite, si l'entier renvoyé par cette fonction est strictement positif cela signifie qu'il reste des gommes dans les zones externes du plateau. Dans ce cas-ci, on appelle la fonction Direction NettoyerZone(Info * info)⁽²⁾ pour manger les gommes des zones externes. Sinon cela signifie qu'il ne reste plus de gommes dans les zones externes, on appelle donc la fonction Direction NettoyerZoneCentral(Info * info)⁽¹⁾ pour finir de manger toutes les gommes du plateau de jeu.

Les fonctions Direction NettoyerZone(Info * info)⁽²⁾ et Direction NettoyerZoneCentral(Info * info)⁽¹⁾ marchent sur le même principe c'est-à-dire informer le PloucMan sur ce qu'il doit faire.

(1) La fonction Direction NettoyerZoneCentral(Info * info) teste s'il y a des gommes dans la zone où se situe le PloucMan. Si c'est le cas, la fonction Direction MangerGommesZone(Info * info, char * zone)⁽³⁾ est appellée avec le paramètre zone égale à la zone où est il se trouve. Et si ce n'est pas le cas, la fonction Direction MangerGommes(Info * info) est appelée pour se diriger vers la gomme la plus proche.

(2) La fonction Direction NettoyerZone(Info * info) commence par tester la zone où se trouve le PloucMan. S'il se trouve dans la zone centrale et qu'il reste des gommes à l'extérieur de cette zone la fonction regarde la vitesse du Ploucman. Si sa vitesse est inférieure à celle des monstres la fonction Direction MangerGommes(Info * info) est appelée sinon on sort de cette zone centrale en appelant la fonction Direction ZonePlusPres(Info * info)⁽⁴⁾. Une fois sortie de cette zone la fonction teste s'il y a des gommes dans la zone où se situe le PloucMan. Si c'est le cas la fonction Direction MangerGommesZone(Info * info, char * zone)⁽³⁾ est appelée avec le paramètre zone égale à la zone où le PloucMan se trouve. Si ce n'est pas le cas plusieurs cas sont testés :

1^er cas : il y a des gommes dans les deux zones adjacentes, la fonction Direction ZonePlusPres(Info * info)⁽⁴⁾ est appelée pour que le PloucMan se dirige vers la zone la plus près de lui.
2^ème cas : il n'y a des gommes que dans une des zones adjacentes, on se dirige vers cette zone en appelant la fonction Direction MangerGommesZone(Info * info, char * zone)⁽³⁾ avec comme paramètre la zone vers laquelle on veut aller.
3^ème cas : aucune zone adjacente ne contient de gomme. Dans ce cas on refait les mêmes tests sur les zones adjacentes +1 c'est-à-dire que par exemple si on est dans la zone 1 on va traiter les zones 3 et 7. Si on arrive encore avec ces deux zones dans le cas 3, on recommence en prenant les zones adjacentes +2 c'est-à-dire dans notre exemple les zones 4 et 6.
4^ème cas : il n'y a pas de gommes dans les zones adjacentes +1 et +2, on se dirige alors vers la zone la plus proche avec la fonction Direction ZonePlusPres(Info * info)⁽⁴⁾.

(3) La fonction Direction MangerGommesZone(Info * info, char * zone) renvoie la direction vers la gomme se trouvant dans la zone fournit par le paramètre zone et étant la plus proche du PloucMan.

(4) La fonction Direction ZonePlusPres(Info * info) calcule et renvoie la direction de la zone la plus proche du PloucMan.

1.3. Explication sur un exemple

Pour clarifier notre explication nous allons mettre en pratique l'algo sur un exemple simple que nous allons illustrer par des schémas.

Etape 1 :

Le Ploucman est dans la zone 1 et il y a des gommes dans cette zone. Il va donc commencer par manger les gommes présentes dans cette zone. Pour donner au PloucMan la direction de la gomme la plus proche de lui on utilise la fonction Direction MangerGommesZone(Info * info, char * zone) avec comme paramètres Info * info qui prend info et char * zone qui prend "zone1".

Etape 2 :

Le Ploucman est dans la zone 1 et il n'y a plus de gommes dans cette zone. On va alors regarder s'il y a des gommes dans les zones adjacentes c'est-à-dire les zone 2 et 8. Comme il y en a dans les deux zones, on se dirige vers la zone la plus proche du PloucMan en appelant la fonction Direction ZonePlusPres(Info * info). Cette fonction va dire au PloucMan de se diriger vers la zone 2.

Etape 3 :

Le PloucMan mange les gommes de la zone 2 en appelant la fonction Direction MangerGommesZone(Info * info, char * zone). Une fois les gommes de la zone 2 mangées on regarde les zones adjacentes (zone 1 et 3) pour voir s'il y a des gommes. Aucune de ces zones ne contient de gommes, on va donc s'intéresser aux zones adjacentes +1 c'est-à-dire les zone 8 et 4. Comme il y a des gommes dans les deux zones on va vers la zone 4 qui est la plus proche (car on est dans la partie haute de la zone 2). On se dirige vers la zone 4 en disant au PloucMan d'aller vers la zone 3.

Etape 4 :

Une fois le PloucMan arrivé dans la zone 4, il mange les gommes de la zone avec la fonction Direction MangerGommesZone(Info * info, char * zone).

Etape 5 :

Ensuite, on regarde s'il y a des gommes dans les zones adjacentes (zone 3 et 5), comme il n'y en a pas on s'intéresse aux zones adjacentes +1 (zone 2 et 6). Il n'y toujours pas de gommes dans ces zones. On teste alors avec les zones adjacentes +2 (zone 1 et 7) et on trouve qu'il n'y a aucune gomme dans ces zones. On dit alors au PloucMan de se diriger vers la zone la plus proche de lui avec la fonction Direction ZonePlusPres(Info * info) donc vers la zone 5.

Etape 6 :

On refait les mêmes tests que dans la partie précédente (étape 5). Et cette fois on trouve qu'il y a une gomme dans une des zones adjacentes +2 (zone 8) on se dirige donc vers elle en passant par la zone 6 et 7.

Etape 7 :

Une fois la gomme de la zone 8 mangé il n'y a plus de gommes dans les zones externes on va donc s'occuper de la zone centrale. Le PloucMan va se diriger vers la gomme la plus proche grâce à la fonction Direction MangerGommes(Info * info) qui renvoie la direction de la gomme la plus proche c'est-à-dire la direction vers la gomme se trouvant dans la zone bas de la partie centrale.

Etape 8 et ... :

Pour nettoyer les zones de la partie centrale le PloucMan va soit utiliser la fonction Direction NettoyerZoneCentral(Info * info) s'il y a des gommes dans la zone où il se trouve, soit la fonction Direction MangerGommes(Info * info) pour se diriger vers la gomme la plus proche.

1.4. Diagramme d'appel des fonctions

1.5. Difficultés rencontrées

La plus grosse difficulté fut d'arriver à trouver tous les tests que nous devions réaliser pour que le PloucMan ne se bloque pas. La division en neuf zones du plateau de jeu nous a imposé de prendre en compte de nombreux cas particuliers. En effet, pour que le PloucMan n'entre pas dans des conditions contradictoires nous avons été forcés de prendre en compte les zones entourant celui-ci ainsi que les zones entourant ces dernières (voir l'exemple ci-dessus pour bien cerner le problème).
L'autre difficulté que nous avons rencontrée fut de comprendre comment fonctionnait la structure Perso.

2. Partie Résultat

./ploucman 500 10 10 100 0
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1225.17
Malus moyen :  101.18
Score       :    4.47

./ploucman 500 15 15 100 0
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1284.00
Malus moyen :  139.12
Score       :    3.74

./ploucman 500 20 20 100 0
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1312.50
Malus moyen :  100.58
Score       :    4.31

./ploucman 500 10 10 100 58
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1211.71
Malus moyen :   97.41
Score       :    4.57

./ploucman 500 15 15 100 58
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1282.25
Malus moyen :  124.10
Score       :    3.96

./ploucman 500 20 20 100 58
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1321.19
Malus moyen :  113.82
Score       :    4.07

./ploucman 500 10 10 100 100
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1217.13
Malus moyen :   92.26
Score       :    4.67

./ploucman 500 15 15 100 100
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1295.65
Malus moyen :  134.80
Score       :    3.78

./ploucman 500 20 20 100 100
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1325.04
Malus moyen :  117.64
Score       :    4.00

./ploucman 500 10 10 100 150
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1235.16
Malus moyen :  107.62
Score       :    4.33

./ploucman 500 15 15 100 150
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1297.77
Malus moyen :  163.40
Score       :    3.41

./ploucman 500 20 20 100 150
Simulation :   100
Identification : Groupe 2.4  
Temps moyen : 1328.08
Malus moyen :  114.50
Score       :    4.04

./ploucman 500 10 10 100 200
Simulation :   100
Identification : Groupe 2.4
Temps moyen : 1221.50
Malus moyen :  111.22
Score       :    4.29

./ploucman 500 15 15 100 200
Simulation :   100
Identification : Groupe 2.4
Temps moyen : 1292.74
Malus moyen :  156.10
Score       :    3.50

./ploucman 500 20 20 100 200
Simulation :   100
Identification : Groupe 2.4
Temps moyen : 1323.22
Malus moyen :  119.79
Score       :    3.97

Moyenne sur ces 15 tests:

Temps moyen : 1277.87
Malus moyen :  119.57
Score moyen :    4.07

Interface graphique :Interface graphique :

1. Partie Technique

1.1. Problématique

Pour pouvoir réaliser la plus jolie interface graphique possible, il nous a été nécessaire de procéder en plusieurs étapes. Nous avons donc commencé par nous poser différentes questions pour définir exactement ce que nous avions à réaliser. Ci-dessous les questions majeures que nous nous sommes posés :

Comment insérer des images ?
Comment animer nos images ?
Mettre une animation différente selon le contexte ?
Création de la charte graphique, que choisir ?
Comment optimiser notre programme ?

1.2. Comment insérer des images ?

A l'aide du code source fourni et de la documentation de GTK nous avons orienté nos recherches vers l'insertion de PixMap. Après quelques tests, notre première image fut insérée. Seulement les PixMaps possèdent de très gros inconvénients :

ils sont très lourds en poids car chaque pixel est codé sur un octet (R G B)
et ils ne gèrent pas la transparence.

Pour pallier à ce problème, nous avons décidé de chercher une autre solution pour l'insertion d'images dans cette interface graphique. Suite au premier rendez-vous et à un mail de Eric Guérin "Pour insérer des images, une bonne idée consiste à utiliser les pixbuf." nous avions enfin trouvé notre solution: Les PixBuf.

Les PixBuf gèrent la transparence
et peuvent s'utiliser avec tous types de fichiers graphiques (gif, png, jpg ...) donc possibilité d'optimiser le poids de nos images.

1.3. Comment animer nos images ?

Toujours à l'aide de la documentation de GTK nous avons essayé de trouver une solution pour animer les objets constituant notre interface. Ne trouvant rien de satisfaisant, nous avons opté pour une solution utilisant un compteur (nous en utilisons en fait deux) que nous initialisons au démarrage du programme à 0. Ensuite, à chaque appel de la fonction affichage.c nous incrémentons nos compteurs. Il suffit alors d'afficher la portion d'image correspondant au numéro du compteur (pour mieux comprendre vous pouvez aller faire un petit tour dans la partie résultat). Pour que la même image s'affiche pendant 3, 4, 5, ... appels (de suite) de la fonction d'affichage nous effectuons des tests sur les compteurs avec des calculs de modulos.

1.4. Mettre une animation différente selon le contexte ?

Une fois les images chargées et animées il nous restait à trouver comment afficher une animation différente pour le PloucMan suivant le contexte dans lequel il se trouvait. Nous désirions afficher une animation différente quand il se trouvait proche d'une gomme, qu'il se faisait toucher par un monstre ou en fonction de la direction dans laquelle il se dirigeait. Nous avons vite trouvé une solution : il suffisait de stocker la direction renvoyée par la fonction 'deplacement.c' dans la structure perso. Ce qui nous a posé le plus de problèmes, fut de comprendre comment faire communiquer la fonction 'deplacement.c' et 'affichage.c'. En effet, il ne suffisait pas seulement d'ajouter un champ dans la structure puis de l'utiliser; Il nous a fallu aussi faire de multiples tests afin de comprendre que la fonction affichage.c était appellée avant la fonction 'deplacement.c', ce qui signifiait qu'il fallait initialiser notre structure (au premier appel de la fonction) dans 'affichage.c' (pour l'éxécutable xploucman) et dans 'deplacement.c' (pour l'éxécutable plouman).

1.5. Création de la charte graphique, que choisir ?

La création de l'environnement graphique s'est effectuée petit-à-petit tout au long du développement du PloucMan. De la première version de notre interface, il ne reste actuellement que les gommes dont nous étions tombés amoureux. Notre PloucMan s'est ainsi transformé d'un smiley trouvé sur un forum, en un smiley comique trouvé sur un site de pixelart, pour arriver à un mario. Pour ce qui est des monstres, d'un triangle rouge ils se sont mutés en abeilles piquant notre PloucMan pour essayer de le ralentir. Dernières améliorations, un texte s'affiche lorsque le PloucMan se fait toucher par un monstre et lorsqu'il mange une gomme. Les monstres qui ont un déplacement limité à la zone centrale en horizontal et vertical sont rouges de colère. Pour détecter quels monstres sont concernés par cette limitation il nous a fallu effectuer quelques tests pour découvrir que les monstres étaient organisés selon cet ordre : un montre qui suit le PloucMan en vertical (limité à la zone centrale), un qui le suit en horizontal (toujours limité à la zone centrale), un qui le suit de partout et un qui fait n'importe quoi. Il y a donc 4 stratégies différentes pour les monstres.

1.6. Comment optimiser notre programme ?

Une fois notre PloucMan, les gommes et les monstres implantés il ne nous restait plus qu'à optimiser notre interface pour qu'elle tourne mieux sur de petites configurations (pour info notre config de test est un AMD Athlon 2400+ avec 768 MO de Ram, une Ati Radeon 8500 et la distribution Fedora Core 3).

Suite au premier rendez-vous de ce projet tutoré et avec une idée donnée par notre encadrant, nous avons changé un peu notre méthode de chargement d'image. Au lieu de créer (physiquement) une image pour chaque frame de l'animation, nous avons regroupé ces images en une seule image contenant toutes ces frames. Ainsi, selon la frame que l'on désire afficher, on sélectionne la zone appropriée dans l'image. Cette technique nous permet de ne charger plus qu'une seule image pour chaque objet à la place d'une image par frame d'animation de chaque objet.

Nous avons ensuite optimisé le poids de nos images en mettant le fond en jpg par exemple (taille du fichier divisé par 10).

Afin d'encore optimiser la vitesse d'exécution nous avons essayé d'implanter plusieurs fonctions qui se sont révélées insatisfaisantes. En particuler, une fonction nous permettant de ne redessiner que les parties du décors modifiées à l'instant t-1. Le problème de cette fonction vient qu'on ne gère plus les différents plans et que l'on perd ainsi l'intérêt de la transparence qui s'en trouve sévérement altérée.

Autre optimisation, stocker dans la structure perso les pixbuf. Etape qui nous as pris le plus de temps car il nous as fallu comprendre comment déclarer des pointeurs sur GDKPixbuf alors que gdk.h n'est pas inclus dans struct.h. Solution donnée par un autre groupe déclarer des pointeurs sur void et les forcer en PixBuf lors du chargement. L'énorme avantage de charger les images dans la structure est de n'avoir à charger qu'une seule fois les images en mémoire lors du premier appel de la fonction affichage.c.

Dernière optimisation utiliser des tableaux pour stocker nos variables dans la structure afin de limiter le nombre de variables présent dans la structure.

2. Partie Résultat

2.1. Les différents objets

Le fond d'écran :

Les Gommes :

Les Monstres :

(monstres qui suivent le PloucMan)

(monstres pas contents)

Le PloucMan :

(direction bas droite)
(direction bas gauche)
(direction haut droite)
(direction haut gauche)
(direction bas)
(direction haut)
(direction droite)
(direction gauche)
(quand il s'approche d'une gomme)
(quand il se fait toucher par un monstre)

Les Textes :

(PloucMan prend de l'énergie)
(PloucMan se fait piquer par un monstre)

2.2. Screenshots

Interface Version 1 :

Interface Version 2 :

Interface actuelle :

Conclusion sur le projet tutoré :Conclusion sur le projet tutoré :

Durant cette année, nous avons pu appréhender la gestion d'une équipe, du temps avec tous les impératifs et les imprévus que cela entraîne.

Tout d'abord, ce projet tutoré nous a donné un premier aperçu des enjeux du travail en équipe. En effet, afin de réaliser les objectifs définis en début de projet ( programmer un algorithme de recherche, une interface graphique et rédiger un compte rendu) il a fallu nous organiser et répartir les différentes tâches.

Après la gestion des troupes, celle du temps est primordiale. Afin d'en perdre le moins possible, lorsque l'on travaille en équipe, il est important de coder proprement et de commenter son code pour que le reste de l'équipe puisse utiliser notre travail. Nous avons aussi compris qu'il était nécessaire de séparer le programme en plusieurs modules (fonctions qui mangent les gommes et fonctions qui détectent dans quelle zone le PloucMan se trouve par exemple). L'avantage de travailler ainsi permet un gain de temps énorme car il est possible de concevoir plusieurs fonctions simultanément et de les assembler à la fin en ayant enlevé les bugs dans chacune d'elles.

D'autre part, nous avons appris à utiliser des documentations (GTK en particulier). En effet, lorsque l'on rencontre un problème technique (insérer une image par exemple), la seule solution est de se plonger dans la documentation pour voir s'il n'existe pas une fonction qui nous ferait gagner du temps.

Maintenant que ce projet est terminé, nous pensons que si nous avions le temps de recommencer, nous n'opterions pas pour les mêmes solutions en ce qui concerne l'algorithme de recherche. En effet, nous optimiserions l'algorithme allant à la gomme la plus proche. Notre idée serait de mettre sur chaque gomme des pondérations c'est-à-dire un gros malus pour les gommes du centre, un malus en plus pour les gommes proches de monstres et on ajouterait à ce malus la distance du PloucMan. Ensuite, le PloucMan irait manger la gomme possédant le moins de malus. En optimisant un peu cet algorithme, nous pensons que nous effectuerions des meilleurs scores qu'avec l'algorithme que nous avons réalisé.

Enfin, le projet tutoré nous a permis de mettre en application sur un cas pratique et ludique ce que nous avions appris au cours de cette année (Langage C, GTK, algorithmie et HTML), ce qui est très intéressant. Il nous a aussi été indispensable d'apprendre à travailler en équipe et à gérer notre temps. On pourrait peut-être juste regretter que cette année, le sujet nous ait été imposé car nous aurions certainement été plus motivés si nous l'avions choisi.