<font size="8pt"><b>BOIDS</b></font> <font size="5pt"><strong>Rapport technique</strong></font> *** ![](https://i.imgur.com/pW7K0Xp.png) --- <font><mark>À l'attention de M. **Senn**, M. **Le Callennec** et Mme. **Rizzotti**</mark></font> <font size="6pt"><b> Java - Projet P2 </b></font> <font size="5pt"><sup>*Juin 2021*</sup></font> <font size="5pt"> **Autheurs :** </font> @Genoiz Ulysse @Marachly Amir @Schmid Aymeric *** <font size="5pt"><b>Table des matières : </b></font> <font size="5pt"> **Abstract** </font> Ce rapport suit la création d'une simulation de nuées d'oiseaux. Il décrit les différentes phases du projet et présente comment les composantes des oiseaux sont représentées et calculées. --- [ToC] ## 1. Introduction Dans le cadre du projet de deuxième année à la HE-Arc, il nous a été demandé de réaliser une application riche en animations en utilisant Java. Nous voulions faire réaliser un logiciel satisfaisant. Après quelques recherches, nous nous sommes tourné vers la simulation des nuées d'oiseaux. Ce projet s'inscrit dans notre apprentissage des languages orientés objets, mais également des interfaces graphiques. Java associé à JavaFX remplissent donc ces deux objéctifs pédagogiques. Le but principal de ce projet est donc de produire une application de simulation de nuées d'oiseaux en Java en utilisant JavaFX. Le projet montre comment des règles simples peuvent amener un comportement de groupe entre des entités. Il indique également comment nous avons résolu des problèmes de performances de notre simulation. Ce rapport suit le développement de cette application, depuis sa conception à sa réalisation. ## 2. Analyse ### 2.1 Inspiration et concept Nous nous sommes basés sur un type de simulation existant. En effet, les boids ont été inventés en 1986 par Craig Reynolds REFTO http://www.red3d.com/cwr/boids. Le mot "Boid" signifie "bird-oid object", et, comme ce nom l'indique, cela consiste à simuler une nuée d'oiseaux. Nous ne voulions pas simplement recréer un programme qui ne faisait rien de plus que les autres. Nous nous sommes alors lancés le défi d'ajouter une dimension de couleur à notre simulation. Cette idée nous est venue en regardant une vidéo de _dante_ dans laquelle nous pouvons voir la couleur des boids changer en formant des groupes. REFTO https://www.youtube.com/watch?v=QbUPfMXXQIY. ### 2.2 Spécificités détaillées #### 2.2.1 Boids ##### 2.2.1.1 Principal Chaque boid possède des caractéristiques propres : une position, une orientation, une vitesse et une accélération. De même, un boid a un différent coefficient pour chaque règle de déplacement. Les déplacements des boids sont donc définis par trois règles. L’application des règles génère un vecteur accélération. Ce vecteur est ensuite intégré afin de changer la position du boids. Les trois règles sont la séparation, l’alignement et la cohésion. Les boids s’éloignent des boids voisins trop proches. Les boids alignent leur orientation à celle de leurs voisins. Enfin, les boids cherchent à se regrouper. Les boids sont mis à jour à chaque delta temps. ##### 2.2.1.2 Secondaires Avant et pendant la simulation il est possible de modifier les paramètres des boids : - la vitesse - le poids des règles : - la cohésion - l’alignement - la séparation - distance de détection Ces derniers sont modifiables grâce à un curseur glissant. Grâce à un clic de la souris, on peut ajouter un boid à la simulation. Les boids ont une 4ème règle de base: la couleur. Un boid apparaît avec une couleur pastel aléatoire. Puis, à chaque rafraichissement, le boid met sa couleur à jour en fonction des boids qu’il détecte aux alentours en faisant la moyenne de ces derniers. La forme d’un boid est un fer de lance. ![](https://i.imgur.com/MZBp751.png) #### 2.2.2 Design L’application possède un thème sombre et un thème clair. Elle comporte un menu de démarrage, un menu de réglage, un menu de paramétrage de simulation ainsi qu’un menu pause. L’utilisateur peut choisir entre un mode plein écran ou fenêtré. Lors de la simulation, un bouton sera disponible dans un coin de l’application. Il ouvre un petit menu qui permet de modifier les poids des règles régissant les boids, leur vitesse et la distance de détection. ![](https://i.imgur.com/zqr147f.png) ##### 2.2.2.1 Menu - Menu principal : - comporte les boutons suivants : - Start : amène sur le menu de paramètre de simulation - Settings : permet de gérer les paramètres de volume, fenêtré/plein écran - Quit : quitte le programme - Menu de paramétrage présimulation : - comporte les boutons suivants : - Start : Lance la simulation - back : renvoie au menu principal - comporte les options suivantes : - la vitesse des boids - la taille des boids - le poids des règles qui régissent les boids - Menu de paramétrage pendant la simulation : - comporte les options suivantes : - la vitesse des boids - la taille des boids - le poids des règles qui régissent les boids - Menu de pause : - comporte les boutons suivants : - Resume: retourne en jeu - Settings: permet de gérer les paramètres de volume, fenêtré/plein écran - Home: renvoie au menu principal #### 2.2.3 Interaction ##### 2.2.3.1 Principal Dans la simulation, lorsque l’utilisateur clique avec la souris, un boid est généré avec une direction, un sens aléatoire et un dégradé de deux couleurs aléatoires sélectionnées dans une palette pastelle. ##### 2.2.3.2 Secondaire L’application propose un design clair et minimaliste, il doit être facile de distinguer les boids les uns des autres. La navigation doit être la plus simple et instinctive. L’application peut être mise en pause. L’utilisateur peut modifier les paramètres des boids en temps réel grâce à un menu caché par défaut. #### 2.2.4 Points Chauds - choix des bibliothèques : libGDX ou javaFX - détection des boids alentours : force brute ou dans une grille - évitement des murs ### 2.3 Planification La planification des tâches comprend deux niveaux de priorités pour le développement de l'application, les tâches primaires, donc minimal au bon fonctionnement du logiciel, et secondaires, considérées comme des extensions pour un meilleur confort lors de l'utilision du logiciel. Toutes les tâches sont représentées sur un diagramme de Gantt REFTOIMAGE(Gantt) sur lequel est noté les différents jalons. Les premières heures que nous avons consacré au projet étaient destinées à la réalisation des différents diagrammes et maquettes ainsi qu'à la résolution des points chauds pour que l'on puisse commencer le développement dans les meilleurs conditions. Nous avons ensuite pu attaquer la partie développement et avancer selon le diagramme de Gantt. Grâce à la bonne organisation et répartition des tâches aucun retard important n'a été à déclarer tout au long du projet. **IMAGE** ![](https://i.imgur.com/W8CWo6c.png) ## 3.Conception ### 4. Description des modules et interfaces #### 4.1 Diagrammes de classes La classe boid est la classe qui va contenir toutes les règles et la manière de se comporter des boids ainsi que la méthode qui permet de les dessiner sur le canvas principal. La classe SimpleContrainer permet de stocker les boids et les obstacles de la simulation, les méthodes clés de la classe sont celles qui permet de retourner la liste des boids et des obstacles qui se trouve à une distance d'un boid tous deux près-défini. Elle est implémenté de manière très naïve. C'est ce qui nous a permis d'avoir un rapide rendu et une possibilité de déterminer les éventuel problème lier à ce genre d'implémentation. L'interface BoidsContainer est venu s'imposer lorsque nous avons décider de changer la structure de donnée pour stocker les boids et les obstacles tout en gardant la même implémentation dans les autres classes. L'interface BoidsContainer est donc l'interface qui va permettre de définire les deux classe SimpleContainer et GridContainer. La classe GridContainer a la même utilité que SimpleContainer cependant elle a une implémentation plus réfléchie qui permet une meilleure optimisation dans la recherche des boids/obstacles au alentours des boids. Nonobstant elle devient vraiment intéressente lorsqu'il y a un minimum de 500 boids en simultané (voir REFTO[5.1 Fonctionnement de la grille]). ![](https://i.imgur.com/R1KjCtu.png) **IMAGEWITHLEGEND**[DIAGRAMME DE CLASSE PARTI LOGIQUE] ![](https://i.imgur.com/OOLLvdp.png) **IMAGEWITHLEGEND**[DIAGRAMME DE CLASSE INTERFACE] #### 4.2 Diagrammes des cas d'utilisation Les cas d'utilisations sont assez évident, ils sont séparé en 3 types d'utilisateurs : L'utilisateur qui n'a pas encore démarer l'application, l'utilisateur qui se trouve dans la page de paramètre générale et l'utilisateur qui a déjà lancer la simulation. | Cas d’utilisation | Affiche tous les paramètres des boids | |-------------------------|-------------------------------------------------------------------------| | Description | L'utilisateur voit tous les paramètres des boids via le bouton SETTINGS | | Acteurs | Utilisateur | | Scénario de base | 1. L’utilisateur démarre l’application | | | 2. L’utilisateur se retrouve sur la page d’accueil | | | 3. Clique sur settings | | | 4. Affiche les paramètres des boids | | | 5. Clique sur la flèche de retour | | | 6. Retourne sur le menu principal | | Variantes | | | Préconditions | L'application est lancée | | Préconditions Variantes | Être dans la simulation | | Postconditions | | | Cas d’utilisation | Démarre la simulation | |-------------------|---------------------------------------------------------------------| | Description | L'utilisateur démarre la simulation en cliquant sur le bouton start | | Acteurs | Utilisateur | | Scénario de base | 1. L’utilisateur démarre l’application | | | 2. L’utilisateur se retrouve sur la page d’accueil | | | 3. Clique sur start | | | 4. Lance la simualtion | | Variantes | 1. L'utilisateur lance la simulation depuis les settings | | Préconditions | L'application est lancée | | Postconditions | | | Cas d’utilisation | Modifie les slider des paramètres généraux | |-------------------|-----------------------------------------------------------------------------------------------------------| | Description | L'utilisateur modifie les paramètre généraux des boids et de la simulation via les sliders des settings | | Acteurs | Utilisateur dans les paramètres | | Scénario de base | 1. L'utilisateur fait glisser les sliders | | | 2. Les valeurs des différent paramètres sont modifier | | | 3. Clique sur Start | | | 4. La Simulation se lance avec les nouveau paramètres | | Variantes | 1. L'utilisateur clique sur la flèche de retour | | | 2. la page d'accueil s'affiche | | Préconditions | Être dans la simulation | | Postconditions | | | Cas d’utilisation | Affiche tous les paramètres de simulation | |-------------------|------------------------------------------------------------------------------| | Description | L'utilisateur affiche les paramètres de simulation via le bouton sandwich | | Acteurs | Utilisateur dans la simualtion | | Scénario de base | 1. L’utilisateur clique sur le bouton sandwich | | | 2. Le menu de simulation s'affiche | | | 3. L'utilisateur modifie les sliders | | | 4. Le comportement des boids change en direct | | | 5. L’utilisateur clique sur le bouton sandwich | | | 6. Le menu de simulation se reduit | | Variantes | | | Préconditions | Être dans la simulation | | Postconditions | | | Cas d’utilisation | Affiche la mode immersion | |-------------------|-----------------------------------------------------------------------| | Description | L'utilisateur mets la simulation en plein écran et cache le HUD | | Acteurs | Utilisateur dans la simualtion | | Scénario de base | 1. L’utilisateur appuie sur ESCAPE | | | 2. Affiche le menu InGame | | | 3. Clique sur Immersion | | | 4. L'application se met en en plein écran et le HUD devient invisible | | | 5. L’utilisateur appuie sur ESCAPE | | | 6. Re-affiche la simulation de base | | Variantes | | | Préconditions | Être dans la simulation | | Postconditions | | ![](https://i.imgur.com/hFuX2m9.png) #### 4.2 Maquettes graphiques des interfaces Lors de la conception, nous avons créer des maquettes qui représente le rendu finale souhaité. Le logiciel est considéré comme une simulation satisfaisante et relaxante à contempler de se fait nous avons opter pour un visuel épuré et apaisant. IMAGE ![](https://i.imgur.com/y0ndf1I.png) IMAGE ![](https://i.imgur.com/cvL5zVD.png) IMAGE ![](https://i.imgur.com/OYoCIP0.png) IMAGE ![](https://i.imgur.com/CZdpuqN.png) ## 5. Réalisation ### 5.1 Fonctionnement des boids Premièrement, regardons le mouvement des boids. Les boids se basent sur 3 règles simples pour se déplacer. Ils regardent les boids voisins, dans un radius donné et adaptent leur vitesse par rapport à eux. Plus concrètement, ces 3 règles sont la séparation, l’alignement et la cohésion. -- Chacune d'elles --- Chaque règle possède également un poids afin de permettre un contrôle du comportement des boids. La séparation est la règle qui permet au boids de ne pas se rentrer dedans. Lorsqu’un voisin est trop près d’un boid, ce dernier va accélérer dans la direction opposée au boid voisin. Dans notre implémentation, il accélère plus vite lorsque le voisin est plus proche de lui, ce qui permet un évitement plus organique. L’alignement permet à un boid d’adapter sa vitesse aux boids voisins. Concrètement, cela veut dire qu’il regarde la moyenne des vecteurs vitesse de ses voisins et accélère ou décélère pour se rapprocher de cette moyenne. Cela inclut non seulement la norme du vecteur vitesse, mais aussi la direction. C’est cette règle qui fait que les boids ne s’arrêtent pas et vont dans le même sens. La cohésion est là pour que les boids essayent de rester en groupe. Pour ce faire, un boid essaye toujours de rester proche du centre du groupe de boids voisins. Donc, il accélère dans la direction de la moyenne des positions des boids alentours. Avec ces 3 règles, nous obtenons une accélération pour chaque boid. Il suffit de l’intégrer deux fois pour obtenir la position. Pour cela, nous utilisons simplement la méthode d’Euler. Autrement dit, à chaque mise à jour, l’accélération est ajoutée à la vitesse avec la pondération du delta temps : $v_{n+1} = v_n + \delta \cdot a_n$. On obtient avec le même principe la position en y ajoutant la vitesse. Il y a quelques détails de plus, par exemple, la norme de la vitesse est limitée. Pour les obstacles, nous aurions pu utiliser un algorithme d’évitement d’obstacles performant, mais c'est compliqué à mettre en place. Nous avons donc choisi de réaliser une fonction bien plus simple. Basiquement, les obstacles sont constitués de points. Les boids essayent de les éviter de la même façon qu'ils le font avec leurs semblables. Ce n’est pas infaillible et les boids se font souvent poussés par le groupe. Mais cela suffit pour donner un joli résultat. De plus, nous avons ajouté des rebonds sur les obstacles avec une méthode très similaire. La seule différence est que le rebond annule les autres règles, afin que le groupe ne pousse pas le boid. Pour que cette méthode un peu simple marche suffisamment bien, il faut être sûr que les obstacles dessinés soient constitués de points suffisamment proches. Si ce n’est pas le cas, nous en ajoutons de nouveaux à la création de l’obstacle. Enfin, dans notre simulation, les boids changent de couleurs selon leur voisin. C’était étonnement compliqué à réaliser. En effet, au départ, nous avions naïvement fait une moyenne RVB, ce qui faisait que les boids finissaient tous gris. Nous avons alors pensé à utiliser des couleurs TSL. REFTO https://fr.wikipedia.org/wiki/Teinte_saturation_lumi%C3%A8re En effet, les couleurs TSL permettent de ne varier que la teinte d’une couleur, ce qui est parfait dans notre cas. La teinte est une valeur sous forme d’angle, nous avons alors essayé de changer la couleur des boids avec une moyenne circulaire. Ce n’était toujours pas parfait, avec des clignotements de couleurs, et les boids finissaient tous avec une couleur semblable à la fin. Et c’est là que nous avons eu une idée un peu étrange, mais qui marche. Nous avons pris la teinte de la couleur non comme un angle, mais comme un vecteur. Et nous appliquons basiquement les mêmes règles de mouvement des boids à ce vecteur couleur. Nous n’appliquons tout de même pas la séparation, car nous voulons que les boids aient la même couleur. Il suffit enfin de prendre l’angle du vecteur et de l’utiliser pour la teinte du boid. Cela permet de réaliser assez simplement ce changement de couleur. De plus, les boids changent de couleur continuellement, grâce à la règle de l’alignement. ### 5.1 Fonctionnement de la grille Les règles de mouvements des boids se basent en grande partie sur les boids environs. Il faut donc que la recherche des voisins soit la plus efficace possible. Il existe beaucoup de stratégies pour cela, nous avons décidé de placer les boids dans une grille. Le conteneur des boids est donc un tableau 2D contenant des listes dynamiques de boids. Chaque cellule du tableau représente un carré de la fenêtre. Les boids sont donc placés dans le carré contenant leur position actuelle. Cela permet une recherche des voisins bien plus rapides. On peut en effet regarder uniquement les cellules alentour, à la place de vérifier tous les boids. L’astuce est de définir la taille des carrés d’une manière intelligente. Dans notre cas, la taille des carrés est la taille du radius de visions des boids. Ainsi, on a simplement besoin de vérifier les 8 cellules autour de celle contenant le boids actuel. Il serait possible de définir des cellules plus petites, afin de devoir vérifier encore moins de boids, mais cela est plus compliqué. Dans tous les cas, après chaque mise à jour de la position des bois, il faut replacer les boids étant sorti de leur carré dans le bon carré. Cette opération de réarrangement est cependant très peu couteuse par rapport à la recherche. La complexité de la recherche naïve est de $O(n)$, avec n le nombre de boids. En effet, la recherche vérifie tous les boids. L’algorithme des boids est donc en $O(n^2)$, car chaque boids appelle en tout cas une fois la recherche. Avec la grille, la recherche passe en $O(s)$, avec s le nombre de boids moyen dans une cellule de la grille. Cela veut dire que l’algorithme dépend grandement de la taille de la cellule, et donc dans notre cas du radius de vision des boids. L’algorithme des boids est donc en $O(n \cdot s)$ et dans le pire cas, où la grille ne contient qu’une seule cellule par exemple, $O(n^2)$. ### 5.2 Déroulement Regardons rapidement l'ordre d'appel des classes et fonctions. Tout d'abord, le *main* transmet au *SceneManager* le stage (la fenêtre) principale. Ensuite il lui demande de passer à la vue "MainMenu" c'est ici que l'utilisateur est invité à appuyer sur start. Ainsi, le *SceneManager* passe à la scène suivante, la *SimulationMenuPane*. Cette dernière superpose 3 éléments : * Le *SimulationPane* * Le *PauseMenuPane* * Le *LiveSettingsMenu* À la création du premier, le *BoidsContainer* est instancié et, comme indiqué dans son nom, il va contenir et gérer les boids. C'est lui qui permettera aux oiseaux de récupérer leurs voisins. Finalement, un timer est démarré. A chaque tick de ce dernier, tous les boids seront mis à jours et, comme les obstacles, redessinés. Toute la base est alors prête à acueillir les oiseaux. L'utilisateur n'a donc plus qu'à les faire apparaître en cliquant et en faisant glisser sa souris à l'intérieur du canvas. Une floppée d'instances de la classe *Boid* sont dessinés à l'écran. Au début, stressés par la proximité de leurs voisins, la régle de séparation les agîte et leur fait prendre leur distance. La situation se stabilise et les autres règles sont rendues plus visibles. En effet, les boids s'alignent et commencent à former des plus ou moins grands groupes. Les couleurs des boids à l'intérieur de ces amas s'harmonisent grâce aux deux règles liées à la couleur. ### 5.3 Fonctions principales Cette section décrit les fonctions principales réalisées pendant ce projet. Les différentes règles qui dirigent les oiseaux sont réalisées par des fonctions visibles dans le fichier *boids.java*. Celles-ci se nomment: * alignement * cohesion * separation * colorCohesion * colorAlignement * avoidObstacles * bounceObstacles * followMouse * avoidMouse Pour la majorité d'entre elles, il est nécessaire que le boids connaisse ses voisins. Pour ce faire, nous utilisons le *BoidsContainer*. ```java= List<Boid> boidsNear = container.getBoidsNear(radius, this); ``` #### 5.3.1 Alignement Comme dit plus haut, la loi d'alignement permet aux individus de choisir une direction commune. Chacun d'eux récupère la vélocité de ses voisins et en fait une moyenne. Puis la différence entre la velocité actuelle et la vélocité moyenne est ajoutée au vecteur d'accélération. ```java= int i = 0; for (Boid boid : boidsNear) { velMean = velMean.add(boid.velocity); ++i; } velMean = velMean.scalarMultiply(1.0 / i); velMean = velMean.subtract(velocity); acceleration = acceleration.add(alignmentCoef, velMean); ``` #### 5.3.2 Cohésion La cohésion permet de regrouper les boids. Contrairement à l'alignement, la cohésion est calculée par la moyenne de position. Mais à part cela, les deux règles sont similaires. ```java= int i = 1; for (Boid boid : boidsNear) { posMean = posMean.add(boid.position); ++i; } posMean = posMean.scalarMultiply(1.0 / i); posMean = posMean.subtract(position); acceleration = acceleration.add(cohesionCoef, posMean); ``` #### 5.3.3 Séparation La séparation agît légèrement différement que les deux autres règles essentielles. Celle-ci ne sert pas à accorder les oiseaux mais à les repousser lorsqu'ils sont trop proches les uns des autres. Bien ajustée elle donne une impression d'équilibre au sein des groupes. Comme pour les autres lois, tous les voisins sont parcourus. Néanmoins, seuls sont traités ceux qui se trouvent à une distance au maximum égale à la moitié du rayon de détection. Seuls les homolohues très proches sont pris en compte. Puis la distance moyenne est calculée et ajoutée à l'accélération. ```java= for (Boid boid : boidsNear) { if (boid.getPosition().distance(position) <= radius / 2) { Vector2D distance = position.subtract(boid.position); if (distance.getNorm() != 0) { distMean = distMean.add(distance.scalarMultiply(radius / 2 / distance.getNorm())); ++i; } } } distMean = distMean.scalarMultiply(1.0 / i); acceleration = acceleration.add(separationCoef, distMean); ``` ## 6. Les tests Nous avons basé nos tests essentiellement sur les fonctionnalités. C’est-à-dire que nous testons chaque nouvelle fonctionnalité individuellement. Nous avons également effectué des tests d’intégrations après chaque merge de branches. Pour la plupart des tests, nous avons utilisé la technique de la boite noire, basée sur les entrées-sorties du code et non sa structure. | Fonctionnalité | Test effectué | Résultat attendu | Résultat obtenu | Remarque | |---------------------------|------------------------------------------------------------------|--------------------------------------------------|--------------------------------------------------|--------------------------------------------------------------------------------| | Performence Algorithmique | 2000 boids - GridContainer | < 5ms en moyenne | 8ms en moyenne | voir graphe | | Performence Algorithmique | 2000 boids - SimpleContainer | 5x plus long que pour GridContainer | 34ms | | | comportemental | boids traversent les obstacles | non | oui | Solution : mettre l'accéleration à 0 | | comportemental | vitesse des boids pas trop élevé | oui | non | Solution : mettre une vitesse max | | ergonomie | fermer la fênetre quitte correctement l'application | oui | non | Solution : Rajouter un event handler sur l'action de fermeture de la fenêtre | | paramétrage | changement effectif grâce au slider dans les paramètres | oui | oui | | | paramétrage | changement effectif grâce au slider depuis le menu de simulation | oui et immédiat | oui et immédiat | | | GUI | resize de la fenêtre | donne plus de place à la simulation | donne plus de place à la simulation | | | GUI | entrer de full screen | cache le HUD | cache le HUD | | | GUI | sorti de full screen | réaffiche le HUD | HUD pas visible | Soulution : ajouter un listener sur l'event full screen de l'application | | ambiance | musique en loop infini | oui | oui | | | ambiance | musique augmente en mode immersion | oui | non | Solution : réglage à 50% de base on remonte à 100% lors de l'immersion | | ambiance | musique diminue en quittant le mode immersion | oui | oui | | | comportemental | évitement de la souris quand l'outil est sélectionné | oui | oui | | | comportemental | suivi de la souris quand l'outil est sélectioné | oui | oui | | | ergonomie | bouton gomme supprime les obstacles | oui | oui | | | ergonomie | les obstacles supprimés n'influe plus la simulation | oui | non | Solution : suppression de toutes les références | | GUI | Le bouton start lance la simulation | oui | oui | | | GUI | Le bouton "Quit" ferme correctement l'application | oui | oui | | | GUI | Le bouton settings affiche les paramètre généraux | oui | oui | | | ergonomie | sélection de l'outil ajout de boids | maintient du clic gauche ajoute des boids | maintient du clic gauche ajoute des boids | | | ergonomie | sélection de l'outil ajout d'obstacles | maintient du clic gauche ajoute des obstacles | maintient du clic gauche ajoute des obstacles | | | ergonomie | sélection de l'outil suivi de la souris | maintient du clic gauche boids suivent la souris | maintient du clic gauche boids suivent la souris | | | ergonomie | sélection de l'outil évitement de la souris | maintient du clic gauche boids évitent la souris | maintient du clic gauche boids évitent la souris | | Pour démontrer que le GridContainer permet une update plus rapide des boids, on a fait deux graphiques. Les données des graphiques sont le nombre de boids sur l'axe horizontal et la moyenne de temps de rafraîchissement en ms. ![](https://i.imgur.com/3x7IEwf.png) **IMAGEWITHLEGEND**[GRAPHIQUE AVEC SIMPLECONTAINER] ![](https://i.imgur.com/1hrS1l5.png) **IMAGEWITHLEGEND**[GRAPHIQUE AVEC GRIDCONTAINER] On voit bien que avec un SimpleContainer la courbe du temps est quadratique alors que celle avec un GridContainer semble presque linéaire. De plus on peut constater que jusque 300 boids le temps de rafraîchissement moyen est plus bas pour la SimpleGrid. On peut expliquer ce phénomène par le fait que à chaque rafraîchissement il faut réarranger tous les boids dans le GridContainer. Ce qui pour un petit nombre de boids est plus couteux que le temps gagné dans la recherche de boids voisins. En revanche dès qu'il y a suffisamment de boids on voit immédiatement que le GridContainer est sans équivoque le plus optimisé en terme de temps. La dispersion plus importante des données sur le graphique avec le GridContainer est dû au fait que le rafraichissement dépend beaucoup de la position des boids. Si tous les boids sont répartis sur toutes les cases du GridContainer alors le temps de rafraîchissement sera plus court, chaque boids aura peu de boids voisins. Tandis que si tous les boids sont regroupés autour d'une seule case alors chaque boids aura tous les boids qui seront considérsés comme boids voisins. ## 7 Problèmes et améliorations Le principal problème que nous avons rencontré durant la réalisation de ce projet est la performance du programme. En effet, dès le début du projet, l’affichage des boids étaient parfois fluide, parfois saccadé, et cela avec peu de boids. Malgré cela, nous avons continué d’ajouter des fonctionnalités, comme l’évitement d’obstacles. Cela n’a bien sûr pas amélioré les performances. Lorsque nous avons décidé que la simulation des boids était suffisamment complète, nous nous sommes penchés sur ces problèmes de performances. Le problème majeur était l’inconsistance des images par seconde. Un moment, l’affichage était fluide, et un autre, pas du tout. Ce qui nous a donc fait penser au garbage collector de Java. En utilisant VisualVM, nous avons bien vu une corrélation entre la fluidité de l’affichage et la quantité de mémoire utilisée par le programme. Ce qui nous a donc amenés à faire des recherches sur la meilleure façon de dessiner en JavaFX. Un article sur Internet nous a alors convaincus d’afficher les boids via le Canvas de JavaFX. REFTO https://edencoding.com/javafx-canvas-vs-pane/. En effet, jusqu’alors, nos boids étaient des Polygon. Ils étaient affichés comme tout panel graphique, ce qui est bien pour un programme statique, mais pas pour une simulation. L’utilisation du Canvas a déjà grandement stabilisé les images par seconde. Mais en nous renseignant justement sur les animations en JavaFX, nous avons découvert l’AnimationTimer. Nous utilisions avant cela la classe Timer de base de Java, mais qui marche donc indépendamment de l’interface. Ce qui fait que lorsque l’interface ne suit plus, le minuteur continuait de mettre à jour la position des boids. C’est aussi cela qui donnait cet affichage très saccadé. L’AnimationTimer est lui lié à l’interface et permet un delta de temps de mise à jour non constant. Avec cela, nous pensions que nous ne pouvions pas faire beaucoup plus d’optimisations au niveau de l’affichage des boids. Les images par seconde n’étaient pas suffisantes pour nous, mais au moins à peu près stables. Il fallait donc maintenant optimiser le calcul des positions des boids. En effet, en regardant le nombre de temps que prenait chaque mise à jour, on obtenait quelque chose comme 25 ms pour 2000 boids. Ce qui ne va pas du tout. Dans l’idéal, ce temps devrait être réduit aux alentours des 1 ms. La première chose qui a été faite est l’utilisation d’une grille comme conteneur. Cela réduit la complexité de l’algorithme de recherche des boids alentour grandement. On passe d’un algorithme en $O(n)$ avec n le nombre de boids, en $O(s)$, avec s le nombre de boids dans une cellule en moyenne. La complexité est donc dépendante de la taille de chaque cellule, et donc du radius de vision des boids. L’ajout de la grille a réduit le temps de calcul des positions par 2, ce qui n’est pas négligeable, mais ce n’est toujours pas 1 ms. L’optimisation d’après a simplement été de n’avoir qu’un radius de vision des boids. En effet, avant cela, les boids avaient un radius différent pour la séparation, la cohésion et l’alignement. Nous faisions donc environ 5 appels à la fonction de recherches des boids alentour par boids. Ce n’était bien sûr pas une bonne idée, et en changeant cela pour un seul appel, le temps de calcul a été divisé par environ 4. Nous avons également essayé d’implémenter une classe de vecteur 2D mutable. En observant le programme avec VisualVM, nous avons bien vu que les vecteurs 2D immutable d’Apache prenaient une bonne partie de la mémoire. Nous avons donc essayé d’implémenter notre propre classe de vecteur mutable, qui réduirait l’impact mémoire. Mais nous avions un problème avec la collision des obstacles que nous n’avons pas réussie à résoudre. Nous avons donc gardé les vecteurs d’Apache. Et nous nous sommes arrêtés là, ne voyant plus quoi faire. Le temps de calcul est en moyenne de 5 ms sur un PC portable. Ce n’est pas les 1 ms espérées, mais c’est déjà bien mieux. La mise à jour des boids est donc bien plus rapide qu’auparavant. Mais le problème est que l’affichage est toujours assez lent. Il prend en moyenne 5 fois plus de temps que la mise à jour et nous ne pouvons rien y faire. L'utilisation de dégradé pour les boids est aussi couteuse en image par seconde. JavaFX n’est en effet pas le meilleur choix d’infrastructure pour construire une simulation comme celle-là. Si nous devions recommencer ou continuer ce projet, nous changerions pour libGDX qui semble bien plus approprié. Nous pourrions également essayer d'implémenter le conteneur des boids avec un arbre quaternaire. Une amélioration possible serait également de faire que la vision des boids est circulaire. C’est-à-dire qu’un boid voit les boids de l’autre côté de l’écran. Cela change beaucoup avec un grand radius de vision, mais nous n’avons pas eu le temps de l’implémenter. ## 8. Conclusion Le produit final de ce projet est une application en Java. Celle-ci permet la simulation d’une nuée d’oiseaux, via le principe des boids. L’application permet donc à un utilisateur de lancer une simulation. Il peut placer des boids à l’aide de la souris. Ceux-ci tentent de s’éviter, mais en même temps de se regrouper. Cela crée un comportement de groupe très joli à regarder. Les boids essayent également d’adapter leur couleur aux boids alentour. L’utilisateur peut changer en direct les facteurs dirigeant les règles de mouvement des bois, ce qui change leur comportement. L’utilisateur peut aussi dessiner des obstacles. Les boids vont alors tenter d’éviter les obstacles, ou vont rebondir dans ceux-ci. Cela permet de voir des effets de groupe, tel que des goulots d’étranglement. Enfin, l’utilisateur peut diriger les boids, en les attirant ou les repoussant avec la souris. Le but principal était de produire une application satisfaisante. Voyons si cet objectif est atteint. La simulation des boids est relaxante en soit. L’ajout des dégradés et de la musique aide également beaucoup. Au niveau de l’esthétique du projet, nous sommes assez satisfaits du résultat. Le problème est en effet la performance de l’application, plus précisément la fluidité. Avant les optimisations réalisées, l’application était littéralement inutilisable. Malgré tous nos efforts, cela ne reste pas génial. L’utilisation de JavaFX semble impacter les performances, comme l’utilisation de dégradé. Nous avons appris cependant beaucoup grâce à ces problèmes, que ce soit de la façon dont le garbage collector marche ou encore comme les boucles prennent du temps. Nous avons aussi vu comment placer des entités dans une grille pour accélérer la recherche des voisins. Pour améliorer le projet, cela vaudrait la peine d’utiliser une autre API de dessin, comme libGDX. Cela n’est certainement pas la seule raison aux problèmes de performances, mais cela impacte tout de même. On pourrait également ajouter des prédateurs aux boids qui tenteraient de manger les boids. L’ajout d’autres règles est en effet assez simple. Pour conclure, ce projet nous a permis de découvrir JavaFX et les boids. L’utilisation de la grille est aussi très utile dans les jeux vidéos. Nous avons vu également la difficulté de réaliser des algorithmes performants. Ce projet a finalement été réalisé avec un grand intérêt et une envie de réaliser une application agréable à utiliser. ## Bibliographie REFTO https://en.wikipedia.org/wiki/Boids#:~:text=Boids%20est%20le%20nom%20d,forme%20d'un%20oiseau).