\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}