---
# System prepended metadata

title: Untitled

---

<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).
