\documentclass{article}

\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage[french]{babel}


\title{Projet d'IA : Documentation}
\author{Guillaume Libersat}

\begin{document}

\maketitle

\tableofcontents

\section{Généralités}

Le programme est réalisé à l'aide du langage Python\footnote{Le langage Python : http://www.python.org} et de la
bibliothèque SDL\footnote{Bibliothèque SDL : http://www.libsdl.org} (module ``pygame''\footnote{SDL pour Python : http://www.pygame.org}). 

Il ne nécessite pas de dépendances supplémentaires.

Python a été choisi pour sa rapidité de développement, sa liberté, sa bibliothèque riche et ses performances raisonnables. 
De plus, sa machine virtuelle est disponible sur de nombreuses plate-formes (20+).

La SDL quant-à-elle a été choisie car elle fourni une API de bas niveau tout en restant rapide à utiliser sans être contraignante.

Enfin, ayant déjà de l'expérience avec ces outils, je savais qu'ils seraient adaptés aux travaux demandés.

\section{Architecture générale}

\subsection{Coeur de la conception}

Le programme est construit sur le modèle MVC comme demandé et utilise
le pattern ``mediator''\footnote{Patron médiator :
  http://fr.wikipedia.org/wiki/Médiateur\_(patron\_de\_conception)} pour
faire communiquer les couches.


Le pattern ``mediator'' permet d'obtenir une application MVC quasiment
découplée dans le sens où toute la communication est réalisée à
travers l'envoi de messages.

Le ``Dispatcher'', point névralgique du système, va permettre aux
composants souhaitant communiquer de d'abord s'enregistrer pour la
réception des messages et ensuite de pouvoir envoyer ses propres
messages.

La figure \ref{fig:mediator} illustre ce modèle.

\begin{figure}
  \centering
  \includegraphics{images/mediator.png}
  \caption{Répartition dans composants avec MVC/Mediator}
  \label{fig:mediator}
\end{figure}


\subsection{Paquetage utilitaire ``core''}

Les classes et fonctions communes sont regroupées dans le paquetage
``core'' et réparties dans 5 sous-modules :

\paragraph{Controller}

Ce module contient 4 contrôleurs :
\begin{itemize}
\item Clavier : filtre et émet les événements reçus depuis le clavier.
  Le comportement par défaut du clavier est de demander un déplacement
  de la vue lorsqu'une touche directionnelle est enfoncée et de
  demander de quitter lorsque la touche Echap est activée ;
\item Souris : émet les événements des clics en associant leur
  positions ;
\item Processeur : émet des ``ticks'' afin de simuler une horloge
  interne ;
\item Agent : Squelette de base pour la gestion des agents.
\end{itemize}

\paragraph{Model}

Dans le sous-module ``Model'', les squelettes des éléments d'une simulation
sont décrits. On y trouve les classes suivantes :
\begin{itemize}
\item Sector : représente un secteur capable de contenir un autre
  élément et de donner un chemin vers au maximum 8 voisins.
\item (Toric)Environment : représente l'environnement dans lequel les agents
  vont évoluer. Il peut être configuré pour être torique et/ou pour
  simuler un environnement de Moore/Newton.
\item Agent : Squelette de base qui implémente un comportement
  retrouvé dans la plupart des agents ;
\item Simulation : Une classe qui permet de créer une simulation avec
  tous ses composants.
\end{itemize}

\paragraph{View}

Le module ``View'' regroupe tout ce qui est relatif à la visualisation
de la simulation.

Il permet de visualiser la plupart des simulations sans effectuer
beaucoup de changements. Les composants décrits sont :

\begin{itemize}
\item SectorSprite : La représentation d'un secteur. La méthode
  ``draw'' peut être surchargée pour changer l'aspect d'un secteur ;
\item AgentSprite : La représentation par défaut d'un agent (un
  cercle). La méthode ``draw'' peut être surchargée pour changer
  l'aspect de l'agent ;
\item SDLView : Une vue programmée à l'aide de la bibliothèque SDL. Il
  est possible de régler la largeur, hauteur et le zoom de la vue.
\end{itemize}

\paragraph{Event}

Ce module contient tous les événements récurrents lors d'une
simulation. Ils permettent de s'échanger des messages entre les
différents composants. On y retrouve par exemple l'événement
``AgentPlacedEvent'' qui indique d'un Agent vient d'être positionné
dans l'environnement.

Ce module contient aussi le ``Dispatcher'' (classe
``EventDispatcher'') qui permet la distribution de ces messages.

\paragraph{Utils}

Toutes les classes-utiliaires réutilisables sont regroupées dans ce
module. Voici la liste des utilitaires :

\begin{itemize}
\item Alignment : Vérifie si on dispose d'un alignement de longueur X
  dans l'envrionnement ;
\item Dijkstra : Effectue l'algorithme de
  Dijkstra\footnote{L'algorithme de Dijkstra :
    http://fr.wikipedia.org/wiki/Algorithme\_de\_Dijkstra} sur
  l'environnement ;
\item GreedyPath : Recherche un chemin selon un critère glouton ;
\item AStar : Implémentation de l'algorithme A*\footnote{L'algorithme
    A* : http://fr.wikipedia.org/wiki/Algorithme\_A*}
\item ConstrainedAStar : Un A* qui prend en compte une carte de la
  même taille que l'environnement afin de choisir un chemin selon la
  valuation dans cette carte.
\end{itemize}

\section{Les programmes}

\subsection{Programme1 : Les billes}

\verb!$ python sim-balls.py! %$

\begin{figure}
  \centering
  \includegraphics{images/balls.png}
  \caption{Simulation des billes}
  \label{fig:balls}
\end{figure}

Ce programme propose une simulation de billes dans un environnement
clos.

Lorsqu'une bille rencontre une obstacle (une autre bille ou un mur),
elle rebondit.

D'un point de vue programmation, seule la classe Agent a été
surchargée pour donner un comportement spécifique aux billes.

Voici les paramètres modifiables dans le fichier ``sim-balls.py'' :
\begin{itemize}
\item SDLView(disp, w=274, h=274, zoom=1) : règle la largeur, hauteur et
zoom de la vue, en pixels
\item BallSimulation : paramètre ``ball\_count'' règle le nombre de balles
\end{itemize}

\subsection{Programme2 : Schelling}

\verb!$ python sim-schelling.py! %$

\begin{figure}
  \centering
  \includegraphics{images/schelling.png}
  \caption{Modèle de Schelling}
  \label{fig:schelling}
\end{figure}

Ce programme simule le modèle de ségrégation de Schelling.

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

A chaque itération, le taux de satisfaction est calculé et s'il ne
convient pas, un déménagement est effectué par l'agent (déplacement
vers une case libre aléatoire dans l'environnement).

La taux de satisfaction est calculé par :
$\frac{NOMBRE\ DE\ SEMBLABLES\ DANS\ LE\ VOISINAGE}{NOMBRE\ DE\ VOISINS}$

Il est possible de configurer le modèle avec les paramètres suivants
(fichier ``sim-schelling.py'') :

\begin{itemize}
\item SchellingView(disp, w=380, h=380, zoom=0.8) : règle la largeur, hauteur et
zoom de la vue, en pixels ;
\item SchellingSimulation (disp,
                        env=Environment(disp, 40, 40),
                        a1\_count=200, a2\_count=250,
                        a1\_rate=0.3, a2\_rate=0.3)
                        \begin{itemize}
                        \item env : décrit l'envrionnement (40x40 dans
                          ce cas) ;
                        \item a1\_count : le nombre d'agents de type1 ;
                        \item a2\_count : le nombre d'agents de type2 ;
                        \item a1\_rate : le taux de satisfaction pour
                          les agents de type1 ;
                        \item a2\_rate : le taux de satisfaction pour les agents de type2.
                        \end{itemize}
\end{itemize}


\paragraph{Résultat}

On observe bien une convergence de la simulation donc une ségrégation des agents au bout d'un certain temps
(cf. figure \ref{fig:schelling-res}).

\begin{figure}
  \centering
  \includegraphics{images/schelling2.png}
  \caption{Résultat de la simulation de Schelling}
  \label{fig:schelling-res}
\end{figure}

\subsection{Programme3 : WaTor}

\verb!$ python sim-wator.py! %$

\begin{figure}
  \centering
  \includegraphics{images/wator.png}
  \caption{Simulation WaTor}
  \label{fig:wator}
\end{figure}

Cette simulation permet de représenter l'évolution de la population
des poissons et des requins dans un environnement. Elle se déroule
dans un environnement torique avec un voisinage de Moore.

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

Chaque poisson et requin se reproduit à intervalle régulier de manière
spontanée. Seuls les requins ont besoin de manger des poissons
régulièrement pour survivre. Les poissons peuvent survivre aussi
longtemps qu'ils n'ont pas été mangés.

Une reproduction n'est possible que s'il existe un espace libre dans
les secteurs voisins.

Il est possible de configurer le modèle comme suit (fichier
``sim-wator.py'') :

\begin{itemize}
\item WatorView(disp, w=350, h=350, zoom=1) : règle la largeur, hauteur et
zoom de la vue, en pixels ;
\item WatorSimulation(disp,
                      env=ToricEnvironment(disp, 30, 30),
                      sharks=80, fishes=100,
                      fish\_breeding\_age=2, shark\_breeding\_age=10,
                      shark\_starvation\_time=3)
                      \begin{itemize}
                      \item env : décrit un envrionnement torique de
                        30x30 ;
                      \item sharks : le nombre de requins ;
                      \item fishes : le nombre de poissons ;
                      \item fish\_breeding\_age, shark\_breeding\_age
                        : Temps avant reproduction ;
                      \item shark\_starvation\_time : Temps avant qu'un requin meurt de faim.
                      \end{itemize}
\end{itemize}


\paragraph{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.

On a donc bien une auto-régulation du milieu.

\subsection{Programme 4 : ColorsGame}

\verb!$ python sim-colorsgame.py! %$

\begin{figure}
  \centering
  \includegraphics{images/colorsgame.png}
  \caption{Le colorsgame}
  \label{fig:colorsgame}
\end{figure}

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 utilise l'algorithme A* avec comme
heuristique la différence entre les coordonnées des cases (distance de
manathan).


Les billes peuvent se déplacer selon un voisinage de Moore (sinon le
jeu était encore plus difficile ;-) ).

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.

\paragraph{Utilisation}

Voici les actions utilisables pendant le jeu :
\begin{itemize}
\item Clic gauche sur une bille pour la sélectionner, puis clic gauche
 sur une case libre pour effectuer un déplacement ;
\item Recliquer sur une bille sélectionnée la désélectionne
\item Bouton de droite pour passer au tour suivant (dans le cas où on ne
 veut rien déplacer)

\end{itemize}

\subsection{Programme 5 : Pacman}

\verb!$ python sim-pacman.py! %$

Il s'agit d'une simulation de fantômes essayant d'attraper un
pacman, qui lui, essaye de leur échapper.

\begin{figure}
  \centering
  \includegraphics{images/pacman.png}
  \caption{Simulation Pacman}
  \label{fig:pacman}
\end{figure}

Le pacman est représenté par une carré jaune tandis que les fantômes
sont représentés par des carrés rouges (cf figure \ref{fig:pacman}).

L'environnement est torique et chaque secteur possède les 4 points
cardinaux comme voisins.


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 algorithmes sur une plus longue durée.


\paragraph{Les cartes}

Les cartes sont stockées dans un fichier externe (voir le répertoire ``data'').

Par défaut, 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")

Pour créer une carte, il faut respecter les critères suivants :
\begin{itemize}
\item Le fichier doit forcément décrire une carte de 28(H) x 30(W) ;
\item "\#" signifie un mur ;
\item "P" place un pacman ;
\item "G" place fantôme ;
\item Tout autre caractère indique un emplacement libre.
\end{itemize}

\paragraph{Stratégies}

Pour les fantômes, on utilise deux stratégies :
\begin{enumerate}
\item Attaque : algorithme glouton pour se déplacer au plus proche du
  pacman
\item 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.
\end{enumerate}

Ces deux stratégies sont utilisées à tour de rôle de manière à laisser
un peu de chance au pacman de pouvoir s'échapper.


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 :
\begin{enumerate}
\item Générer un dijkstra commun aux X fantômes (afin de "noter" chaque
 case selon leur danger pour le pacman). On obtient alors des ``0'' à
 l'emplacement des fantômes et des valeurs élevées quand ils sont
 loins. Voir la figure \ref{fig:ghostmap} pour un exemple ;
\item Calculer un dijkstra pour le pacman (le coût de ses
  déplacements). Voir la figure \ref{fig:pacmap}. ;
\item 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). Voir la figure \ref{fig:diffmap} ;
\item On cherche le maximum local (meilleur score sur la ghostmap avec
  une valeur positive dans la diffmap). ;
\item On effectue une recherche en A* pour atteindre ce point ;
\item On se dirige vers la case trouvée.
\end{enumerate}

NOTE: Lors de l'exécution, les cartes s'affichent à chaque itération
dans le terminal.

\begin{figure}
  \centering
\begin{verbatim}
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
###  20  19  18  17  16  15  16  17  18  17  16  15 ### ###  18  19  20  21  22  21  20  21  22  23  24  25 ###
###  19 ### ### ### ###  14 ### ### ### ### ###  14 ### ###  17 ### ### ### ### ###  19 ### ### ### ###  24 ###
###  18 ### ### ### ###  13 ### ### ### ### ###  13 ### ###  16 ### ### ### ### ###  18 ### ### ### ###  23 ###
###  17 ### ### ### ###  12 ### ### ### ### ###  12 ### ###  15 ### ### ### ### ###  17 ### ### ### ###  22 ###
###  16  15  14  13  12  11  10   9   8   9  10  11  12  13  14  15  14  13  14  15  16  17  18  19  20  21 ###
###  17 ### ### ### ###  12 ### ###   7 ### ### ### ### ### ### ### ###  12 ### ###  17 ### ### ### ###  22 ###
###  18 ### ### ### ###  13 ### ###   6 ### ### ### ### ### ### ### ###  11 ### ###  18 ### ### ### ###  23 ###
###  19  18  17  16  15  14 ### ###   5   4   3   2 ### ###   7   8   9  10 ### ###  17  18  19  20  21  22 ###
### ### ### ### ### ###  13 ### ### ### ### ###   1 ### ###   6 ### ### ### ### ###  16 ### ### ### ### ### ###
### ### ### ### ### ###  12 ### ### ### ### ###   0 ### ###   5 ### ### ### ### ###  15 ### ### ### ### ### ###
### ### ### ### ### ###  11 ### ###   4   3   2   1   2   3   4   5   6   7 ### ###  14 ### ### ### ### ### ###
### ### ### ### ### ###  10 ### ###   5 ### ### ### ### ### ### ### ###   8 ### ###  13 ### ### ### ### ### ###
 15  14  13  12  11  10   9   8   7   6 ### ### ### ### ### ### ### ###   9  10  11  12  13  14  15  16  17  16
### ### ### ### ### ###  10 ### ###   7 ### ### ### ### ### ### ### ###  10 ### ###  13 ### ### ### ### ### ###
### ### ### ### ### ###  11 ### ###   8 ### ### ### ### ### ### ### ###  11 ### ###  14 ### ### ### ### ### ###
### ### ### ### ### ###  10 ### ###   9  10  11  12  13  14  15  14  13  12 ### ###  14 ### ### ### ### ### ###
### ### ### ### ### ###   9 ### ###  10 ### ### ### ### ### ### ### ###  13 ### ###  13 ### ### ### ### ### ###
### ### ### ### ### ###   8 ### ###  11 ### ### ### ### ### ### ### ###  14 ### ###  12 ### ### ### ### ### ###
###  10  11  10   9   8   7   8   9  10  11  12  13 ### ###  16  16  15  14  13  12  11  12  13  12  11  10 ###
###   9 ### ### ### ###   6 ### ### ### ### ###  12 ### ###  15 ### ### ### ### ###  10 ### ### ### ###   9 ###
###   8 ### ### ### ###   5 ### ### ### ### ###  11 ### ###  14 ### ### ### ### ###   9 ### ### ### ###   8 ###
###   7   6   5 ### ###   4   5   6   7   8   9  10  11  12  13  13  12  11  10   9   8 ### ###   5   6   7 ###
### ### ###   4 ### ###   3 ### ###   8 ### ### ### ### ### ### ### ###  12 ### ###   7 ### ###   4 ### ### ###
### ### ###   3 ### ###   2 ### ###   9 ### ### ### ### ### ### ### ###  13 ### ###   6 ### ###   3 ### ### ###
###   4   3   2   1   0   1 ### ###  10  11  12  13 ### ###  17  16  15  14 ### ###   5   4   3   2   1   0 ###
###   5 ### ### ### ### ### ### ### ### ### ###  14 ### ###  16 ### ### ### ### ### ### ### ### ### ###   1 ###
###   6 ### ### ### ### ### ### ### ### ### ###  15 ### ###  15 ### ### ### ### ### ### ### ### ### ###   2 ###
###   7   8   9  10  11  12  13  14  15  16  17  16  16  15  14  13  12  11  10   9   8   7   6   5   4   3 ###
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
\end{verbatim}
  \caption{Ghostmap}
  \label{fig:ghostmap}
\end{figure}



\begin{figure}
  \centering
\begin{verbatim}
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
###  48  47  46  45  44  43  44  45  46  47  46  45 ### ###  42  41  40  39  38  37  36  37  38  39  40  41 ###
###  47 ### ### ### ###  42 ### ### ### ### ###  44 ### ###  41 ### ### ### ### ###  35 ### ### ### ###  40 ###
###  46 ### ### ### ###  41 ### ### ### ### ###  43 ### ###  40 ### ### ### ### ###  34 ### ### ### ###  39 ###
###  45 ### ### ### ###  40 ### ### ### ### ###  42 ### ###  39 ### ### ### ### ###  33 ### ### ### ###  38 ###
###  44  43  42  41  40  39  40  41  42  43  42  41  40  39  38  37  36  35  34  33  32  33  34  35  36  37 ###
###  43 ### ### ### ###  38 ### ###  43 ### ### ### ### ### ### ### ###  36 ### ###  31 ### ### ### ###  36 ###
###  42 ### ### ### ###  37 ### ###  42 ### ### ### ### ### ### ### ###  37 ### ###  30 ### ### ### ###  35 ###
###  41  40  39  38  37  36 ### ###  41  40  39  38 ### ###  35  36  37  38 ### ###  29  30  31  32  33  34 ###
### ### ### ### ### ###  35 ### ### ### ### ###  37 ### ###  34 ### ### ### ### ###  28 ### ### ### ### ### ###
### ### ### ### ### ###  34 ### ### ### ### ###  36 ### ###  33 ### ### ### ### ###  27 ### ### ### ### ### ###
### ### ### ### ### ###  33 ### ###  36  37  36  35  34  33  32  31  30  29 ### ###  26 ### ### ### ### ### ###
### ### ### ### ### ###  32 ### ###  35 ### ### ### ### ### ### ### ###  28 ### ###  25 ### ### ### ### ### ###
 31  32  33  34  33  32  31  32  33  34 ### ### ### ### ### ### ### ###  27  26  25  24  25  26  27  28  29  30
### ### ### ### ### ###  30 ### ###  33 ### ### ### ### ### ### ### ###  26 ### ###  23 ### ### ### ### ### ###
### ### ### ### ### ###  29 ### ###  32 ### ### ### ### ### ### ### ###  25 ### ###  22 ### ### ### ### ### ###
### ### ### ### ### ###  28 ### ###  31  32  31  30  29  28  27  26  25  24 ### ###  21 ### ### ### ### ### ###
### ### ### ### ### ###  27 ### ###  30 ### ### ### ### ### ### ### ###  23 ### ###  20 ### ### ### ### ### ###
### ### ### ### ### ###  26 ### ###  29 ### ### ### ### ### ### ### ###  22 ### ###  19 ### ### ### ### ### ###
###  30  29  28  27  26  25  26  27  28  27  26  25 ### ###  22  23  22  21  20  19  18  19  20  19  18  17 ###
###  31 ### ### ### ###  24 ### ### ### ### ###  24 ### ###  21 ### ### ### ### ###  17 ### ### ### ###  16 ###
###  32 ### ### ### ###  23 ### ### ### ### ###  23 ### ###  20 ### ### ### ### ###  16 ### ### ### ###  15 ###
###  31  30  29 ### ###  22  21  20  19  20  21  22  21  20  19  18  17  16  17  16  15 ### ###  12  13  14 ###
### ### ###  28 ### ###  23 ### ###  18 ### ### ### ### ### ### ### ###  15 ### ###  14 ### ###  11 ### ### ###
### ### ###  27 ### ###  24 ### ###  17 ### ### ### ### ### ### ### ###  14 ### ###  13 ### ###  10 ### ### ###
###  24  25  26  27  26  25 ### ###  16  15  14  13 ### ###  10  11  12  13 ### ###  12  11  10   9   8   7 ###
###  23 ### ### ### ### ### ### ### ### ### ###  12 ### ###   9 ### ### ### ### ### ### ### ### ### ###   6 ###
###  22 ### ### ### ### ### ### ### ### ### ###  11 ### ###   8 ### ### ### ### ### ### ### ### ### ###   5 ###
###  21  20  19  18  17  16  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0   1   2   3   4 ###
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
\end{verbatim}
  \caption{Pacmap}
  \label{fig:pacmap}
\end{figure}


\begin{figure}
  \centering
\begin{verbatim}
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
### -28 -28 -28 -28 -28 -28 -28 -28 -28 -30 -30 -30 ### ### -24 -22 -20 -18 -16 -16 -16 -16 -16 -16 -16 -16 ###
### -28 ### ### ### ### -28 ### ### ### ### ### -30 ### ### -24 ### ### ### ### ### -16 ### ### ### ### -16 ###
### -28 ### ### ### ### -28 ### ### ### ### ### -30 ### ### -24 ### ### ### ### ### -16 ### ### ### ### -16 ###
### -28 ### ### ### ### -28 ### ### ### ### ### -30 ### ### -24 ### ### ### ### ### -16 ### ### ### ### -16 ###
### -28 -28 -28 -28 -28 -28 -30 -32 -34 -34 -32 -30 -28 -26 -24 -22 -22 -22 -20 -18 -16 -16 -16 -16 -16 -16 ###
### -26 ### ### ### ### -26 ### ### -36 ### ### ### ### ### ### ### ### -24 ### ### -14 ### ### ### ### -14 ###
### -24 ### ### ### ### -24 ### ### -36 ### ### ### ### ### ### ### ### -26 ### ### -12 ### ### ### ### -12 ###
### -22 -22 -22 -22 -22 -22 ### ### -36 -36 -36 -36 ### ### -28 -28 -28 -28 ### ### -12 -12 -12 -12 -12 -12 ###
### ### ### ### ### ### -22 ### ### ### ### ### -36 ### ### -28 ### ### ### ### ### -12 ### ### ### ### ### ###
### ### ### ### ### ### -22 ### ### ### ### ### -36 ### ### -28 ### ### ### ### ### -12 ### ### ### ### ### ###
### ### ### ### ### ### -22 ### ### -32 -34 -34 -34 -32 -30 -28 -26 -24 -22 ### ### -12 ### ### ### ### ### ###
### ### ### ### ### ### -22 ### ### -30 ### ### ### ### ### ### ### ### -20 ### ### -12 ### ### ### ### ### ###
-16 -18 -20 -22 -22 -22 -22 -24 -26 -28 ### ### ### ### ### ### ### ### -18 -16 -14 -12 -12 -12 -12 -12 -12 -14
### ### ### ### ### ### -20 ### ### -26 ### ### ### ### ### ### ### ### -16 ### ### -10 ### ### ### ### ### ###
### ### ### ### ### ### -18 ### ### -24 ### ### ### ### ### ### ### ### -14 ### ###  -8 ### ### ### ### ### ###
### ### ### ### ### ### -18 ### ### -22 -22 -20 -18 -16 -14 -12 -12 -12 -12 ### ###  -7 ### ### ### ### ### ###
### ### ### ### ### ### -18 ### ### -20 ### ### ### ### ### ### ### ### -10 ### ###  -7 ### ### ### ### ### ###
### ### ### ### ### ### -18 ### ### -18 ### ### ### ### ### ### ### ###  -8 ### ###  -7 ### ### ### ### ### ###
### -20 -18 -18 -18 -18 -18 -18 -18 -18 -16 -14 -12 ### ###  -6  -7  -7  -7  -7  -7  -7  -7  -7  -7  -7  -7 ###
### -22 ### ### ### ### -18 ### ### ### ### ### -12 ### ###  -6 ### ### ### ### ###  -7 ### ### ### ###  -7 ###
### -24 ### ### ### ### -18 ### ### ### ### ### -12 ### ###  -6 ### ### ### ### ###  -7 ### ### ### ###  -7 ###
### -24 -24 -24 ### ### -18 -16 -14 -12 -12 -12 -12 -10  -8  -6  -5  -5  -5  -7  -7  -7 ### ###  -7  -7  -7 ###
### ### ### -24 ### ### -20 ### ### -10 ### ### ### ### ### ### ### ###  -3 ### ###  -7 ### ###  -7 ### ### ###
### ### ### -24 ### ### -22 ### ###  -8 ### ### ### ### ### ### ### ###  -1 ### ###  -7 ### ###  -7 ### ### ###
### -20 -22 -24 -26 -26 -24 ### ###  -6  -4  -2   0 ### ###   7   5   3   1 ### ###  -7  -7  -7  -7  -7  -7 ###
### -18 ### ### ### ### ### ### ### ### ### ###   2 ### ###   7 ### ### ### ### ### ### ### ### ### ###  -5 ###
### -16 ### ### ### ### ### ### ### ### ### ###   4 ### ###   7 ### ### ### ### ### ### ### ### ### ###  -3 ###
### -14 -12 -10  -8  -6  -4  -2   0   2   4   6   6   7   7   7   7   7   7   7   7   7   7   5   3   1  -1 ###
### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###
\end{verbatim}
  \caption{Diffmap}
  \label{fig:diffmap}
\end{figure}


\paragraph{Résultats}

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.

Les fantômes, eux, utilisent des chemins assez différents et
travaillent à tour de rôle pour se rapprocher du pacman.

J'ai effectué deux benchmarks sur l'algorithme : d'abord sur 500
déplacements (figure \ref{fig:bench-pacman}), ensuite sur 1H de jeu
(figure \ref{fig:bench-pacman2}).

On remarque qu'en 1H de jeu (environ 4500 itérations), le pacman meure 6 fois.

\begin{figure}
  \centering
  \includegraphics{../bench-pacman2.png}
  \caption{500 itérations du pacman}
  \label{fig:bench-pacman}
\end{figure}

\begin{figure}
  \centering
  \includegraphics{../bench-pacman.png}
  \caption{1H de jeu du pacman}
  \label{fig:bench-pacman2}
\end{figure}

\paragraph{Amélioration}

Voici les améliorations qu'il pourrait être intéressant de développer :
\begin{itemize}
\item 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 ;
\item 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.
\end{itemize}


\appendix

\section{Bugs}

\subsection{Fonctionnalités}

Dans colorsgame, lorsque l'on a deux alignements en un seul placement,
seul un alignement sera supprimé.

\subsection{Profiling}

En utilisant le profiler Hotshot\footnote{Hotshot :
  http://docs.python.org/lib/module-hotshot.html}, j'ai pu déterminer
deux classes de problèmes.

Tout d'abord, le système est assez lent à cause du design pattern
``mediator'' qui génère énormément de messages. Lorsqu'il faut
distribuer énormément de messages, Python doit parcourir la liste des
récepteurs à longueur de temps, ce qui fait chuter radicalement les
performances.

Ensuite, il y a un problème de performances au niveau de l'algorithme
de Dijkstra qui effectue trop d'itérations par rapport au nombre
normalement nécessaire.

\section{Changelog}

Changements entre le rendu 3 et 4 :
\begin{itemize}
\item Ajout du Pacman (paquetage "pacman")
\item Classe de chargement d'un niveau pacman
\item Ajout d'un A* contraint
\item Ajout d'un algo de chemin glouton
\item Benchmark pour le pacman
\end{itemize}

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

Changements entre le rendu 1 et 2 :
\begin{itemize}
\item Ajout du modèle de Schelling (paquetage "schelling")
\item Ajout du modèle Wator (paquetage "wator")
\item le paquetage "core" a été rendu plus modulaire
\item Ajout d'une classe pour un environnement torique
\end{itemize}

\end{document}


