IA - Projet
===========
Guillaume Libersat

RENDU3 - Vendredi 19 Octobre

Changements depuis le dernier rendu :
 - Ajout du Pacman (paquetage "pacman")
 - Classe de chargement d'un niveau pacman
 - Ajout d'un A* contraint
 - Ajout d'un algo de chemin glouton
 - Benchmark pour le pacman
 - Un gros mal de tête.

Changements entre le rendu2 et 3 :
 - Ajout d'une méthode permettant d'avoir les secteurs libres (factorisation)
 - Ajout d'un contrôleur de souris
 - Ajout du jeu ColorsGame (paquetage "colorsgame")
 - Ajout des événements liés aux actions de la souris
 - Ajout d'une classe utilitaire pour l'algorithme A*
 - Ajout d'une classe utilitaire qui détecte les alignements d'objets identiques

Changements entre le rendu1 et 2 :
 - Ajout du modèle de Schelling (paquetage "schelling")
 - Ajout du modèle Wator (paquetage "wator")
 - le paquetage "core" a été rendu plus modulaire
 - Ajout d'une classe pour un environnement torique

1/ Généralités
--------------

Le programme est réalisé à l'aide du langage Python et de la
bibliothèque SDL (module "pygame"). Il ne nécessite rien de plus.

2/ Architecture
---------------

2/a/ Généralités
     
Le programme est construit sur le modèle MVC comme demandé et utilise
le pattern "mediator"[1] pour faire communiquer les couches.

Les classes et fonctions communes sont regroupées dans le paquetage
"core" et réparties dans 4 fichiers :

core
 `- controller : Controleur Clavier, Agent et Processeur
 `- model : L'Agent, l'Environnement, la Simulation, ...
 `- view : La vue graphique
 `- event : Les événements qui servent à faire communiquer le MVC

Chaque composant souhaitant communiquer avec d'autres doit
s'enregistrer auprès de l'"EventDispatcher" qui joue le rôle de
facteur pour les messages.

2/b/ L'environnement

L'environnement est composé de secteurs qui forme une carte
rectangulaire. Chaque secteur est relié à ses 8 voisins (Moore).

3/ Utilisation
--------------

3/a/ Lancement
Pour lancer le programme, il faut exécuter le fichier python ".py"
correspondant au programme. Exemple "sim-wator.py"

Il est possible de déplacer la vue en utilisant les flèches
directionnelles.

Pour chaque programme, il est possible de régler les paramètres dans
ce même fichier.

3/b/ Programme1 : Les balles

$ python sim-balls.py

- SDLView(disp, w=274, h=274, zoom=1) : règle la largeur, hauteur et
zoom de la vue, en pixels

- BallSimulation : paramètre "ball_count" règle le nombre de balles

3/c/ Programme2 : Schelling

Les agents de type1 sont symbolisés par des formes circulaires tandis
que les autres sont représentés par des rectangles.

La taux de satisfaction est calculé par :
   nombre de personnes comme l'agent / nombre de voisins

$ python sim-schelling.py

- SchellingView(disp, w=380, h=380, zoom=0.8) : règle la largeur, hauteur et
zoom de la vue, en pixels

- SchellingSimulation : (disp,
                        env=Environment(disp, 40, 40),
                        a1_count=200, a2_count=250,
                        a1_rate=0.3, a2_rate=0.3)
  * env décrit l'envrionnement (40x40 dans ce cas)
  * a1_count : le nombre d'agents de type1
  * a2_count : le nombre d'agents de type2
  * a1_rate : le taux de satisfaction pour les agents de type1
  * a2_rate : le taux de satisfaction pour les agents de type2

Résultat : On observe bien une ségrégation des agents au bout d'un
certain temps.

3/d/ Programme3 : WaTor

Les poissons sont représentés par des formes circulaires (à dominante
bleue), les requins par des formes rectangulaires (à dominante rouge).

$ python sim-wator.py

- WatorView(disp, w=350, h=350, zoom=1) : règle la largeur, hauteur et
zoom de la vue, en pixels

- WatorSimulation(disp,
                  env=ToricEnvironment(disp, 30, 30),
                  sharks=80, fishes=100,
		  fish_breeding_age=2, shark_breeding_age=10,
                  shark_starvation_time=3)

  * env décrit un envrionnement torique de 30x30
  * sharks : le nombre de requins
  * fishes : le nombre de poissons
  * fish_breeding_age, shark_breeding_age : Temps avant reproduction
  * shark_starvation_time : Temps avant qu'un requin meurt de faim

Résultat : Cycliquement, les poissons se reproduisent en masse puis
la population de requins augmente peu à peu jusqu'à ce qu'ils mangent
la plupart des poissons puis meurent à leur tour (de famine). Les
poissons peuvent alors se redévelopper et ainsi de suite.

3/e/ Programme 4 : ColorsGame

$ python sim-colorsgame.py

Comme demandé, 3 billes viennent s'ajouter par tour et on peut
effectuer au maximum un déplacement d'une bille dans le cas où un
chemin est possible entre le point de départ et le point d'arrivée.
Pour tester ce chemin, le jeu utiliser l'algorithme A* avec comme
heuristique la différence entre les coordonnées des cases.
Les billes peuvent se déplacer selon un voisinage de Moore.

A chaque fois qu'une bille arrive en jeu, le jeu vérifie si un
alignement de 5 billes de la même couleur est réalisé. Si c'est le
cas, elles seront supprimées.

Utilisation :
 - Clic gauche sur une bille pour la sélectionner, puis clic gauche
 sur une case libre pour effectuer un déplacement
 - Recliquer sur une bille sélectionnée la désélectionne
 - Bouton de droite pour passer au tour suivant (dans le cas où on ne
 veut rien déplacer)

3/f/ Programme 5 : Pacman

$ python sim-pacman.py

Simulation de fantômes qui essayent d'attraper le pacman.

Le programme charge une carte contenue dans le fichier
"data/paclev1.map".

Pour le changer, il suffit d'ajuster la valeur dans le fichier
"sim-pacman.py" :
s = PacmanSimulation(disp, "data/paclev1.map")

NOTE: Le fichier doit forcément décrire une carte de 28(H) x 30(W). Un
"#" signifie un mur, "P" un pacman, "G" un fantôme. Tout le reste est
considéré comme du vide.

Stratégies :

Pour les fantômes, on utilise deux stratégies :
 - Attaque : algo glouton pour se déplacer au plus proche du pacman
 - Repos : déplacement aléatoire pendant un cours laps de temps. Cela
 permet d'éviter aux fantômes d'être trop agressifs et d'introduire de
 l'aléa pour que la simulation ne soit pas déterministe.

Pour le pacman, j'ai testé au moins une dizaine de stratégies (il y a
quelques restes dans "pacman/model.py.tests"). La meilleure stratégie
que nous avons trouvée (en conjuguant les idées de plusieurs
personnes) est la suivante :

Pour chaque itération :
 1/ Générer un dijkstra commun aux X fantômes (afin de "noter" chaque
 case selon leur danger pour le pacman)
 2/ Calculer un dijkstra pour le pacman (le coût de ses déplacements)
 3/ Calculer la différence de ces deux dijkstra
  A cet instant, les cases qui ont un score nul ou négatif signifient
  que le pacman meurt s'il passe à cet endroit (on considère toujours
  le meilleur cas, c'est à dire que les fantômes sont le plus
  intelligent possible).
 4/ On cherche le maximum local (meilleur score fantôme, différence positive)
 5/ On effectue une recherche en A* pour atteindre ce point
 6/ On se dirige vers la case trouvée
NOTE: les cartes s'affichent à chaque itération dans le terminal

Résultat :
Le pacman réussi à fuir dans la plupart des cas mais lorsqu'il se fait
prendre en tenaille il est possible qu'il ne puisse pas s'échapper.

Pour tester l'efficacité de l'algo, voir la section benchmark.
NOTE: Deux fichiers déjà générés sont présents :
 - "bench-pacman.png" sur 1H de jeu
 - "bench-pacman2.png" sur 500 déplacements


Amélioration :
- Dans le cas où on n'arrive pas à trouver de chemin, il serait par
  exemple intéressant de lui faire tenter un chemin risqué (valuation à
  0, voire -1 sur la carte des différences) car les fantômes ne sont en
  général pas aussi agressifs qu'on le considère.
- Lorsqu'il se fait manger, c'est pratiquement tout le temps dû au
  fait qu'il va se réfugier dans un coin. Il faudrait ajouter un
  facteur qui l'incite à revenir vers le centre.

NOTE: Le pacman ne peut pas mourir sauf s'il se suicide (déplacement
par sa volonté vers un fantôme). J'ai préféré ne pas le faire pour
pouvoir tester les algos sur une plus longue durée.


4/ Benchmark
------------

4/a/ Vitesse
Comme demandé, vous trouverez le graphique d'évolution de la vitesse
en fonction du nombre de balles dans le fichier "bench-balls.png". Le
programme utilisé pour le réaliser est disponible dans le fichier
"bench-balls.py".

4/b/ Pacman

Pour générer le benchmark, il faut décommenter les lignes annotées
"Benchmark" dans le fichier "pacman/model.py".

Le benchmark trace les courbes d'éloignement des fantômes avec le
pacman et l'inverse.

Pour l'exécuter, il faut taper :
$ gnuplot pacplot

Ceci produit un fichier appelé "bench-pacman.png"

4/ TODO/Bugs
------------

Le système est assez lent à cause du design pattern mediator qui
génère énormément de messages. J'ai préféré y faire une entorse dans
Wator afin d'accélérer la simulation.

[1] http://fr.wikipedia.org/wiki/M%C3%A9diateur_%28patron_de_conception%29