Sujet du projet Fourmis
Contents
1. Ajouter un appel cette fonction la fin du programme principal pour la tester 7 TD analyse descendante du Projet Dans le TD pr c dent nous avons effectu une analyse ascendante du projet En effet nous avons list les op rations l mentaires n cessaires la simulation des fourmis et nous avons utilis ces op rations basiques pour construire des op rations plus compliqu es elles m mes pouvant tres combin es nouveau Dans ce TD nous allons adopter l approche inverse c est dire effectuer une analyse de scendante du probl me Cela consiste consid rer le probl me dans son ensemble et le diviser en plusieurs sous probl mes plus simples Ces derniers peuvent tre r solus ind pendamment les uns des autres ventuellement par des programmeurs diff rents et peuvent tre eux m mes divis s en sous probl mes Cette analyse descendante peut tre men e jusqu l atteinte des sous probl mes d j trait s dans le TP projet et le TD pr c dent Nous pourrons utiliser toutes les proc dures et fonctions d finies dans le TP projet et le TD pr c dent Il est donc n cessaire de les avoir sous les yeux ainsi que l nonc du projet 7 1 Algorithme principal de la simulation 1 R alisez l algorithme principal de la simulation en supposant disponibles les proc dures sp cifi es ci dessous proc dure initialiserEmplacements R sultat lesFourmis ensFourmis R sultat leSucre2. dure en d pla ant une fourmi de la grille initiale Implementer le pr dicat vide p place l aide de la fonction choisirCoordAleatoirement du TP projet d placer chaque fourmi vers un de ses voisins vides et afficher la grille nouveau It rer 30 fois ce comportement et g n rer un premier film rassemblant les 30 images produites 10 11 12 13 14 4 Initialiser la grille avec l intensit des ph romone de nid associ e chaque case Afficher l intensit en ph romone de nid des cases de la grille dans le terminal pour v rifier que l initialisation a correctement t effectu e Faire en sorte que dans les images g n r es les cases vides soient affich es en d grad de vert repr sentant lintensit des ph romones de nid Impl menter les pr dicats d finis dans la section 1 1 comme des fonctions condi re tournant vrai si la condition de la r gle est v rifi e Impl menter les r gles 1 2 3 et 6 et d placer les fourmis en suivant ces r gles sur 30 it rations On doit observer pisodiquement quelques fourmis qui ram nent du sucre au nid Rajouter les r gles 4 et 5 permettant d acc l rer exponentiellement le rapatriement du sucre Construire un film d environ 300 it rations optionnelle A pr sent lorsque les fourmis ram nent du sucre le tas de sucre doit dimin uer Les fourmis peuvent vider successivement plusieurs tas de sucre sans modifier les r
3. ensCoord R sultat leNid ensCoord Initialise les emplacements des fourmis du sucre et du nid proc dure dessinerGrille Donn e laGrille grille Dessine une image de la grille dans un fichier proc dure mettreAJourEnsFourmis Donn e R sultat laGrille grille Donn e R sultat lesFourmis ensFourmis d place toutes les fourmis en appliquant les r gles de leur comportement Le probl me de la simulation a maintenant t divis en sous probl mes dont certains ont t trait s dans le TD type abstrait et d autres sont trait s par les trois proc dures ci dessus Dans la suite du TD nous traitons le sous probl me le plus difficile savoir la mise jour des positions de l ensemble des fourmis 11 7 2 D placement des fourmis 2 R alisez la proc dure mettreAJourEnsFourmis utilis e dans l algorithme principal en supposant disponible la proc dure sp cifi e ci dessous proc dure mettreAJourUneFourmi Donn e Resultat laGrille grille Donn e R sultat uneFourmi fourmi d place une fourmi en appliquant les r gles de comportement des fourmis NB On dispose pour cela de la structure de contr le suivante pour it rer sur toutes les fourmis f d un ensemble de fourmis ef pour chaque f dans ef faire finpour 3 R alisez la proc dure mettreAJourUneFourmi en supposant disponibles la fonction et la proc dure sp cifi es ci dessous fonction con
4. lt g lt lt lt lt b lt lt w 13 fin de ligne dans l image fic lt lt endl fermeture du fichier fic close int main dessinerDamier return 0 14 Mode d emploi de Beneton Movie GIF Le raccourci est dans le dossier Outils sur le Bureau Au lancement un message appara t c est normal les sons ne sont pas pris en charge Chargement d un lot d images Pour gagner du temps il vaut mieux utiliser l outil de chargement d un lot 0 On doit alors remplir les diff rentes zones de saisie What is the filename prefix of your files The number of the frame must follow that string Put nothing here if your frames are just named by a number le radical des fichiers lt Par exemple fic si les fichiers commencent Put the extension of your files Don t forget the leading dat tous par fic ppm Enter the minimum number of digits after the filename prefix 3 je nombre de chiffres qui suivent le radical os ame 0 to 100 3 si les fichiers sont du genre fic000 ppm fic001 ppm etc Ex le radical des fichiers000 ppm le radica Where are vour files located Browse For Folder He Le dossier o se trouvent les fichiers ppm Choix de la vitesse d animation S lectionner toutes les images un clic sur une des images puis Ctrl A Pr ciser un d lai zone Delay en centi mes de secondes
5. Cr er le fichier de synth se bouton sauvegarde ou Ctrl S on peut cocher Loop ou non Visualisation de l animation En restant dans Beneton Movie GIF bouton Play Utiliser si n cessaire les boutons de zoom On peut aussi faire glisser le fichier gif obtenu dans le programme GifZoom qui se trouve lui aussi dans le dossier Outils ou lancer GifZoom puis ouvrir le fichier gif L avantage de cette deuxi me m thode est que le facteur de zoom est conserv pour la prochaine visualisation
6. Projet L1 S2 2015 Simulation de fourmis Soutenance la semaine du 4 mai 1 Introduction On consid re une grille de 20 lignes 20 colonnes Une case de la grille peut tre vide ou contenir une et une seule des trois choses suivantes une fourmi du sucre ou un l ment de nid Une case ne peut pas contenir en m me temps deux fourmis ou bien du sucre et une fourmi ou bien un l ment de nid et une fourmi Les fourmis doivent donc contourner le sucre et le nid et se contourner entre elles Une fourmi peut ramasser du sucre si elle se trouve cot d une case contenant du sucre Une fourmi peut poser du sucre dans le nid si elle porte du sucre et se trouve cot d une case contenant un l ment de nid Au d but les fourmis cherchent du sucre al atoirement sur la grille Une fois qu une fourmi a trouv du sucre elle le ram ne vers le nid en suivant des ph romones de nid qui indiquent le chemin de retour vers le nid Pendant leur retour du tas de sucre vers le nid les fourmis marquent leur chemin avec des ph romones de sucre qui vont permettre aux autres fourmis de trouver le sucre plus rapidement Les ph romones sont des substances mises par la plupart des animaux et certains v g taux et qui agissent comme des messagers sur des individus de la m me esp ce Extr mement actives elles agissent en quantit s infinit simales si bien qu elles peuvent tre d tect s ou m me transport es plusieurs
7. a fourmi on va beaucoup plus souvent selectionner p2 parmi les cases observ es en premier La simulation ne paraitra alors pas tr s naturelle les fourmis ne se d pla ant pas vraiment al atoirement Par exemple si l on cherche une case voisine vide en commen ant par regarder la case au dessus alors les fourmis se dirigeront tr s souvent vers le haut Lors de l application de la r gle 6 vous devrez donc choisir la case p2 al atoirement parmi les cases voisines vides Ph romones de sucre L intensit des ph romones de sucre est un entier compris entre 0 et 255 qui diminue de 5 chaque it ration de la simulation Lorsqu une fourmi pose des ph romones de sucre elle pose directement 255 2 Affichage On va g n rer une suite d images au format ppm dont les noms seront de la forme f000 f001 f002 repr sentant chaque tape de la simulation On va en suite utiliser le logiciel beneton movie pour les rassembler en un fichier gif anim Il devrait tre install au b timent 336 et est t l chargeable gratuitement l adresse http www benetonsoftware com Beneton_Movie_GIF php Le format des fichiers ppm est donn en annexe il contient essentiellement un tableau de couleurs des pixels On repr sente chaque case de la grille par un pixel color La couleur d pend du contenu de la case les fourmis en noir le sucre en orange le nid en bleu la ph romone de sucre en rouge la ph romone de ni
8. coordonn es dans la grille Pour cela utilisez le type concret coord d fini dans le TP projet Aide 2 Comme une case peut contenir ou non une fourmi il est recommend d associer chaque place un bool en qui dit s il y a une fourmi ou pas Il n est pas n cessaire de stocker un pointeur vers une fourmi dans une case occup e par une fourmi car on n a pas besoin de retrouver la fourmi depuis la case Aide 3 Le type concret de place peut stocker sa propre coordonn e de sorte que lorqu on d place une fourmi on a besoin seulement de passer deux places et on peut lire la nouvelle coordonn e sur la case d arriv e Initialiser une grille 20 x 20 avec au centre un nid de 2 x 2 12 fourmis autour et deux tas de sucre loin du nid L intensit des ph romones de nid sera pour l instant nulle partout Le sch ma suivant est un exemple de situation initiale S fIfIf If f ININ f f ININ f fIflflf f Fourmi N Nid S Sucre Afficher le contenu de cette grille dans le terminal pour v rifier que l initialisation a cor rectement t effectu e Afficher cette grille initiale dans un fichier ppm et le visualiser avec benetton movie crire une proc dure deplacerFourmi qui prend en param tre une fourmi f sa place p1 une place p2 et d place f de p vers p2 Tester cette proc
9. d au maximum NB_COORD coordonn es Coder le type ensCoord avec un type produit Coder la proc dure afficheEnsCoord qui affiche un ensemble de coordonn es Coder la fonction creerEnsCoordVide qui renvoie un ensemble de coordonn es ne con tenant aucun l ment Coder la proc dure ajouterCoord qui prend en param tre un ensemble de coordonn es ec une coordonn e c et ajoute c l ensemble ec Tester ces proc dures et fonctions avec le programme principal suivant int main coord ci creerCoord 2 1 creerCoord 3 4 coord c3 creerCoord 0 0 coord c2 on construit un exemple d ensemble ensCoord exemple creerEnsCoordVide ajouterCoord exemple c1 ajouterCoord exemple c2 ajouterCoord exemple c3 afficherEnsCoord exemple on ajoute encore un element cout lt lt ajout d un element lt lt endl ajouterCoord exemple creerCoord 4 0 afficherEnsCoord exemple return 0 J 11 On s int resse maintenant trouver les coordonn es des voisins d une case dans une grille de TAILLE lignes et TAILLE colonnes Par exemple consid rons la grille ci dessous TAILLE 5 0 0 0 1 0 2 0 3 0 4 1 0 1 1 1 2 1 3 1 4 2 0 2 1 2 2 2 3 2 4 3 0 3 1 3 2 3 3 3 4 4 0 4 1 4 2 4 3 4 4 Les voisins de 2 1 sont 1 0 1 1 1 2 2 2 Les voisins de 3 4 s
10. d en vert Si une case contient plusieurs l ments on affiche en priorit l l ment qui est le plus haut dans la liste ci dessus L am lioration suivante devra tre apport e dans un deuxi me temps les ph romones seront affich es avec un d grad permettant de rendre compte de leur intensit Ainsi les cases seront vert vif pr s du nid et de plus en plus sombre quand la ph romone de nid d cro t De m me les cases seront rouge vif quand une ph romone de sucre vient d tre d pos e et de plus en plus sombre quand celle ci s vapore 3 Impl mentation de la simulation Afin de vous aider r aliser le projet nous vous donnons une analyse de la suite d actions mettre en oeuvre pour impl menter la simulation 1 Sp cifier un type abstrait fourmi un type abstrait place pour les cases et un type abstrait grille contenant toutes les informations n cessaires pour la simulation Aide Le type abstrait ensemble de fourmis est utile car les traitements devront tre faits sur chaque fourmi Rassembler les fourmis dans un ensemble permet d it rer sur les fourmis en utilisant des boucles parcourant les l ments de l ensemble N amnoins il n est pas n cessaire de programmer ce type abstrait il suffit d utiliser un vecteur de fourmis Cette remarque est aussi valable pour manipuler des ensembles de coordonn es D cider des types concrets associ s Aide 1 Une fourmi doit tre associ e ses
11. dition_n Donn e x entier Donn e f fourmi Donn e p1 place Donn e p2 place bool en retourne Vrai si la condition de d placement de la r gle num ro x s applique sur la fourmi f situ e sur la place pl pour un d placement vers la place p2 proc dure action n Donn e x entier Donn e R sultat f fourmi Donn e R sultat pl place Donn e R sultat p2 place applique la proc dure de d placement de la r gle num ro x sur la fourmi f situ e sur la place pl pour un d placement vers la place p2 NB On suposera aussi disponibles la fonction cardinal qui retourne le nombre d l ments d un ensemble de coordonn es ec pass en param tre ainsi que la fonction lireElement qui prend en param tres un ensemble de coordonn es ec et un entier i et retourne le i me l ment de ec 4 Adaptez votre algorithme en prenant en compte la remarque sur la r gle 6 dans l nonc du projet On supposera disponible la fonction sp cifi e ci dessous fonction voisin VideAleatoire Donn e g grille Donn e c coord gt coord retourne les coordonn es dans la grille g d un voisin vide de la case de coordonn es c choisi al atoirement 7 3 R gles de d placement 5 R alisez la fonction condition n et la proc dure action _n en supposant disponibles les fonctions conditionl condition6 qui correspondent aux conditions des r gles 1 6 et les proc dures ac
12. e contient une fourmi fonction contientSucre gt retourne vrai si la place contient du sucre fonction contientNid gt retourne vrai si la place contient un l ment de nid fonction surUnePiste retourne vrai si la place se trouve sur une piste vers du sucre trac e par la pr sence de ph romones de sucre Modifications sur une place proc dure poserSucre pose du sucre sur la place proc dure poserNid pose un l ment de nid sur la place proc dure poserFourmi pose une fourmi sur la place proc dure poserPheroNid pose sur la place une ph romone de nid d intensit fournie en 2 me param tre proc dure poser PheroSucre pose une ph romone de sucre d intensit maximale sur la place proc dure diminuerPheroSucre diminue l intensit en ph romone de sucre sur la place Modification sur deux places proc dure deplacerFourmi ki d place la fourmi fournie en ler param tre qui est sur la place fournie en 2 me param tre vers la place fournie en 3 me param tre Il faut mettre jour les coordonn es de la fourmi 3 Compl tez les sp cifications ci dessus en donnant les ent tes des proc dures et fonctions 4 R alisez un pr dicat vide qui prend une place en param tre et renvoie vrai si la place ne contient ni du sucre ni un l ment de nid ni une four
13. es c d un ensemble de coordonn es ec pour chaque c dans ec faire finpour Remarque une proc dure placerSucre peut tre r alis e suivant le m me principe 7 R alisez une proc dure placerFourmis qui prend une grille et un ensemble de fourmis en param tres et pose l ensemble de fourmis sur la grille NB On dispose pour cela de la structure de contr le suivante pour it rer sur toutes les fourmis f d un ensemble de fourmis ef pour chaque f dans ef faire finpour 8 R alisez une proc dure lineariserPheroNid qui prend une grille en param tre et lin arise l intensit en ph romones de nid des cases de la grille voir la formule dans l nonc du projet On supposera que dans la grille pass e en param tre l intensit en ph romones de nid est maximale sur les places contenant un l ment du nid et nulle partout ailleurs 9 R alisez une proc dure initialiserGrille qui prend en param tre une grille un ensemble de fourmis l ensemble des coordonn es des l ments de sucre et l ensemble des coordonn es des l ments de nid et initialise la grille en pla ant les fourmis le sucre et le nid et en lin arisant les ph romones de nid 10 R alisez une proc dure diminuerPheroSucreGrille qui diminue l intensit des ph romones de sucre sur la grille pour mod liser leur vaporation 6 TP projet Types coordonn es et ensemble de coordonn es Le code crit dans ce TP sera utilis dans le projet I
14. gles du fait que le tas de sucre diminue lorsque les fourmis en chargent Organisation et valuation du projet Deux s ances de TD et deux s ances de TP porteront sur le projet N h sitez pas poser des questions vos encadrants de TP pour r gler les probl mes que vous ne parvenez pas surmonter Il est indispensable de commencer travailler sur le projet d s maintenant L valuation du projet se fera au travers d une soutenance orale pr vue la semaine du 4 mai L organisation de la soutenance est la suivante vous vous installez sur une machine chargez votre programme et v rifiez rapidement que tout fonctionne comme la derni re fois que vous l avez test les deux membres du bin me ont 10 mn pour pr senter ensemble le r sultat de leur tra vail organisation du code visualisation des r sultats discussion sur les probl mes ren contr s ensuite l examinateur a 5 mn pour juger de votre ma trise de la programmation partir de ce moment vous serez consid r s individuellement et un effort important sera fait pour mettre en avant clairement votre implication dans le projet Un tudiant ne peut pr tendre tre not sur un code qu il ne r ussit pas expliquer Un tudiant absent la soutenance aura z ro sur vingt Le principal crit re d valuation est le nombre d actions fonctionnant correctement Nous pren drons galement en compte Qualit de pr sentation Types abst
15. kilom tres Pour simplifier nous supposerons que les ph romones de nid sont pr sentes en permanence et installent un gradient dirig vers le nid Cela signifie que l intensit des ph romones augmente au fur et mesure que l on se rapproche du nid Pour se rapprocher du nid il suffit donc de se d placer vers une case de plus forte intensit en ph romones Les ph romones de sucre elles s vaporent Ainsi les fourmis ne s obstineront pas suivre un chemin de ph romones de sucre vers un tas de sucre qui a t compl tement vid 1 1 Comportement des fourmis Pour d crire le comportement des fourmis nous utiliserons les pr dicats fonctions bool ennes list s ci dessous Pr dicats sur une fourmi f chercheSucre f f ne porte pas de sucre rentreNid f f porte du sucre Pr dicats sur une place une case p contientSucre p p contient du sucre contientNid p p contient un l ment de nid contientFourmi p p contient une fourmi vide p p ne contient ni sucre ni fourmi ni l ment de nid surUnePiste p l intensit des ph romones de sucre sur p est non nulle Pr dicats sur une place p et une place voisine p plusProcheNid p1 p2 l intensit des ph romones de nid sur p est plus impor tante que celle sur p2 plusLoinNid p1 po l intensit des ph romones de nid sur p est moins impor tante que celle sur p2 Pour une place donn e plusieurs pr dicats peuvent tre v
16. l est donc imp ratif de le tester de mani re tr s pouss e pour ne pas introduire de bug dans le projet On cherche manipuler des coordonn es dans une grille c est dire la paire constitu e d un num ro de ligne et d un num ro de colonne 1 2 10 Coder le type produit coord Coder la fonction creerCoord qui prend en param tre un num ro de ligne lig et un num ro de colonne col et retourne une variable de type coord initialis e la coordonn e lig col Coder la proc dure afficherCoord qui prend en param tre une valeur de type coord et affiche cette valeur sous la forme lig col Tester ces fonctions et proc dures en utilisant le programme principal suivant int main coord ci creerCoord 2 1 afficherCoord ci1 cout lt lt endl return 0 J Coder la fonction coordonneesEgales retournant vrai si deux coordonn es sont gales Tester cette fonction avec le programme principal suivant int main coord c1 creerCoord 2 1 coord ci_bis creerCoord 2 1 coord c2 creerCoord 3 4 premier test afficherCoord c1 if coordonneesEgales c1 c1_bis cout lt lt else count lt lt lt gt afficherCoord c1_bis cout lt lt endl second test afficherCoord c1 if coordonneesEgales c1 c1_bis cout lt lt else count lt lt lt gt afficherCoord c2 cout lt lt endl return 0 On souhaite maintenant repr senter un ensemble
17. la couleur rouge sont 255 0 0 et celles de la couleur verte sont 0 255 0 P3 a 4 255 255 0 0 0 255 0 0 255 0 0 255 0 0 255 0 255 0 0 0 255 0 0 255 0 0 255 0 0 255 0 255 0 0 0 255 0 0 255 0 0 255 0 0 255 0 255 0 0 Ce fichier ppm a t g n r par le programme suivant include lt iostream gt pour cout include lt iomanip gt pour setfill setw include lt sstream gt pour ostringstream include lt fstream gt pour ofstream include lt string gt using namespace std variable globale permettant de creer des noms de fichiers differents int compteurFichier 0 action dessinant un damier void dessinerDamier int i j int r g b ostringstream filename creation d un nouveau nom de fichier de la forme img347 ppm filename lt lt img lt lt setfill 0 lt lt setw 3 lt lt compteurFichier lt lt ppm compteurFichier cout lt lt Ecriture dans le fichier lt lt filename str lt lt endl ouverture du fichier ofstream fic filename str ios out ios trunc ecriture de l entete fic lt lt P3 lt lt endl lt lt 4 lt lt M lt lt 4 lt lt lt lt endl lt lt 255 lt lt lt lt endl ecriture des pixels for i 0 i lt 4 i for j 0 j lt 4 j calcul de la couleur if i j r 255 g 0 b 0 else r 0 g 255 b 0 ecriture de la couleur dans le fichier fic lt lt r lt lt lt
18. mi 5 R alisez un pr dicat plusProcheNid qui prend renvoie vrai si la place fournie en ler param tre est plus proche du nid que la place fournie en 2 me param tre Remarque un pr dicat plusLo inNid peut tre r alis suivant le m me principe Le type abstrait grille repr sente la grille Voici un extrait de ses sp cifications Constructeur proc dure chargerGrille Vide R sultat g grille initialise la grille avec une grille vide peut se faire en it rant creer PlaceVide sur toutes les places de la grille Acc s et modifications proc dure chargerPlace Donn e g grille Donn e c coord R sultat p place donne en r sultat la place de la grille situ e aux coordonn es indiqu es proc dure rangerPlace Donn e R sultat g grille Donn e p place met la place dans la grille Si on a stock la coordonn e de la place dans la place ici il n y a pas besoin de passer de param tre coordonn e contrairement chargerPlace Remarque Lorqu on charge une place et qu on la modifie il ne faut pas oublier de la ranger dans la grille sinon la modification ne sera pas enregistr e sur le terrain 6 R alisez une proc dure placerNid qui place des l ments de nid sur la grille pass e en premier param tre l ensemble des coordonn es fournies en 2 me param tre NB On dispose pour cela de la structure de contr le suivante pour it rer sur toutes les coordonn
19. nction chercheSucre retourne vrai si la fourmi cherche du sucre fonction rentreNid gt retourne vrai si la fourmi rentre au nid Modifications proc dure dechargerSucre supprime la charge de sucre port e par la fourmi proc dure chargerSucre ajoute une charge de sucre sur la fourmi 1 Compl tez les sp cifications ci dessus en remplissant les trous dans les ent tes Le type abstrait ensFourmis repr sente un ensemble de fourmis Voici un extrait de ses sp cifications Constructeur proc dure chargerEnsFourmis 3 cr e un ensemble de fourmis positionn es aux coordonn es sp cifi es par l ensemble de coordonn es fourni en 2 me param tre 2 Compl tez les sp cifications ci dessus en donnant les ent tes des proc dures et fonctions 5 3 La grille Le type abstrait place repr sente une case de la grille Il est sp cifi de la mani re suivante Constructeur proc dure creer PlaceVide cr e une place dont les coordonn es sont fournies en param tre ne contenant pas de fourmi ni de sucre ni d l ment de nid Acc s fonction lirePheroNid J gt retourne l intensit en ph romone de nid sur la place fonction lirePheroSucre retourne l intensit en ph romone de sucre sur la place Pr dicats sur une place fonction contientFourmi retourne vrai si la plac
20. ones de nid puis it rer un certain nombre de fois le d placement des fourmis Il faut aussi diminuer p riodiquement l intensit des ph romones de sucre pour tenir compte de leur vaporation Initialisation de la grille avec les ph romones de nid Les ph romones de nid ont une intensit d crite par un r el compris entre 0 et 1 L intensit vaut 1 sur le nid et diminue lin airement quand on s loigne du nid Pour initialiser la grille avec les ph romones de nid on commence par donner l intensit 1 aux cases du nid et l intensit 0 partout ailleurs Ensuite si la grille est constitu e de t lignes et t colonnes on it re t fois la r gle suivante sur toutes les cases 1 Si p lt 1 alors p max m po avec p l intensit des ph romones de nid sur la case consid r e et m la valeur maximale des ph romones de nid sur les cases voisines D placement des fourmis Pour chaque fourmi f sur une case p on essaie d appliquer les r gles une par une de la plus prioritaire la moins prioritaire Pour chaque r gle on cherche une case p2 parmi les cases voisines de p qui v rifient la condition d application de r gle Si l on trouve une telle case on applique la r gle Sinon on passe la r gle suivante Si aucune r gle ne s applique la fourmi ne se d place pas Remarque sur la r gle 6 si l on parcourt le voisinage toujours dans le m me sens pour trouver une case vide p2 o d placer l
21. ont 2 3 2 4 3 3 4 3 Les voisins de 0 0 sont 0 1 1 0 1 1 7 Coder la fonction trouverVoisins qui prend en param tre une coordonn e c et retourne l ensemble des coordonn es des voisins de c Si lig est la ligne de c et col est la colonne de c on peut collecter les coordonn es des voisins de c dans un ensemble ev de la mani re suivante pour i allant de imin imag faire pour j allant de fmin jmaz faire si i j lig col alors ajouterCoordonnees i j ev finsi finpour finpour avec imn Max lig 1 0 imar min lig 1 TAILLE jmin maz col 1 0 imar min col 1 TAILLE Ajouter les instructions suivantes la fin du programme principal pr c dent pour tester la fonction en prenant soin d adapter les noms des champs du type ensCoord aux noms pr c dement choisis on teste la fonction trouverVoisins ensCoord voisins int i 10 for i 0 i lt exemple nbElts i voisins trouverVoisins exemple tablil cout lt lt les voisins de afficherCoord exemple tablil cout lt lt sont afficherEnsCoord voisins 12 Coder une fonction choisirCoordAleatoirement qui prend un ensemble de coordonn es en param tre et retourne une coordonn e au hasard parmi cet ensemble Aide la fonction rand retourne un nombre al atoire Pour obtenir un nombre al atoire entre 0 et n compris il faut donc appliquer un modulo n 1 au r sultat de l appel rand
22. rais par exemple surUnePiste p et vide p Le principe g n ral du comportement des fourmis est le suivant Elles cherchent du sucre en bougeant al atoirement Quand elles trouvent de la ph romone de sucre elles s loignent le plus vite possible du nid tout en restant sur la piste trac e par la ph romone de sucre Quand elles sont c t du sucre elles chargent une partie du sucre puis se rapprochent le plus vite possible du nid tout en posant des ph romones de sucre sur les cases emprunt es Plus formellement le comportement d une fourmi est dict par les r gles nonc es ci dessous par ordre de priorit d croissante R gles Soient f une fourmi p1 la case qu elle occupe et p2 une case adjacente p1 1 Si chercheSucre f et contientSucre p2 alors f charge du sucre et pose une ph romone de sucre sur p1 2 Si rentreNid f et contientNid p2 alors f pose son sucre 3 Si rentreNid f et vide p2 et plusProcheNid p2 p1 alors f se d place sur p et pose une ph romone de sucre sur p 4 Si chercheSucre f et surUnePiste p1 et vide p2 et plusLoinNid p2 p1 et surUnePiste p2 alors f se d place sur po 5 Si chercheSucre f et surUnePiste p2 et vide p alors f se d place sur po 6 Si chercheSucre f et vide p2 alors f se d place sur p 1 2 Simulation La simulation consiste essentiellement initialiser la grille en pla ant les fourmis le nid le sucre et les ph rom
23. raits pertinence choix alternatifs utilisation dans le code Qualit du code modularit lisibilit Ma trise du code Originalit gestion de probl mes rencontr s affichage d informations interm diaires 5 TD Types abstraits du Projet Nous allons tudier les types abstraits d coulant d une analyse du projet de simulation de four mis Les questions qui suivent ont pour but de vous aider dans la r alisation du projet Nous allons consid rer quatre types abstraits un type repr sentant une fourmi un type repr sentant un ensemble de fourmis un type repr sentant une place c est dire une case et un type repr sentant la grille 5 1 Les coordonn es On suppose que l on dispose des types abstraits coord et ensCoord que vous avez impl ment s dans le TP projet Les fonctions utiles au pr sent TD seront fonction creerCoord Donn e x entier Donn e y entier coord cr e la coordonn e x y fonction trouver Voisins Donn e c coord gt ensCoord retourne l ensemble des coordonn es voisines la coordonn e c 5 2 Les fourmis Le type abstrait fourmi repr sente une fourmi Il est sp cifi de la mani re suivante Constructeur fonction creerFourmi cr e une fourmi ne portant pas de sucre partir de ses coordonn es sur la grille Acc s fonction lireCoord gt retourne les coordonn es de la fourmi Pr dicats fo
24. tionl action6 qui correspondent aux actions des r gles 1 6 fonction condition1 Donn e f fourmi Donn e p1 place Donn e p2 place bool en retourne Vrai si la condition d application de la r gle de d placement 1 est v rifi e proc dure action1 Donn e R sultat f fourmi Donn e pl R sultat place Donn e R sultat p2 place applique la r gle de d placement 1 12 8 Annexe Un fichier contient une image d crite par la suite de caract res suivante 1 Un magic number identifiant le type Pour un fichier ppm il s agit des deux caract res P3 2 Des espaces blancs TABs CRs LFs 3 Une largeur L format e avec des caract res ASCII en d cimal 4 Des espaces 5 Une hauteur H galement en ASCII en d cimal 6 Des espaces 7 La valeur de couleur maximale galement en ASCII en d cimal Comprise entre 1 et 65536 8 Un retour la ligne ou d autres caract res espace 9 Un tableau de H rang es allant de bas en haut chaque rang e contient L pixels de gauche droite Chaque pixel est un triplet des composantes RGB c est dire rouge vert bleu de la couleur dans cet ordre Tous les nombres doivent tre pr c d s et suivis d un espace Les lignes ne doivent pas d passer 70 caract res Voici l exemple d un fichier img000 ppm contenant une image de 16 pixels 4 par 4 repr sentant une diagonale rouge sur fond vert les composantes RGB de
Download Pdf Manuals
Related Search