Les Boids, quand l'informatique imite la nature
Vous avez sans doute déjà eu l'occasion d'admirer un groupe d'oiseaux décoller d'un arbre et se déplacer tous ensembles dans un somptueux ballet. J'aimerais dans cet article vous présenter une simulation informatique qui imite ce phénomène et que j'adore : les Boids
Table des matières
Histoire
Nous allons faire un petit bon dans le temps pour revenir en 1986. Craig Reynolds travaille alors comme graphiste chez Symbolics, une entreprise qui fabrique des ordinateurs. Tous les jours, lors de sa pause déjeuner, il a la chance d'admirer des nuées d’oiseaux voler dans le ciel.
Il faut savoir qu’à cette époque, l’informatique fait de nombreux progrès dans le domaine de la vie artificielle. C’est notamment à cette époque que John Conway invente le jeu de la vie, et que Christopher Langton développe sa fourmi informatique.
Craig Reynolds va donc se demander s’il est possible de faire la même chose pour simuler le mouvement collectif de ces oiseaux.
Cette question était alors un sérieux problème sur lequel se heurtaient les biologistes, et là où les scientifiques de l’époque faisaient l’erreur de chercher à identifier un chef de groupe, Reynolds va, au contraire, imaginer un fonctionnement plutôt décentralisé, dans lequel un comportement collectif émerge à partir des interactions entre les oiseaux.
Après quelques recherches, l’informaticien découvre que trois règles comportementales très simples suffisent. Il baptisera alors ses oiseaux numériques les "Boids", contraction de Bird-oid (soit Oisoïde en français).
Fonctionnement
Chaque boid dispose d’un champ de vision sphérique dont il est le centre. Seuls les autres boids qui se situent dans ce champ de vision affectent sa trajectoire.
Chaque boid dispose d’un champ de vision sphérique dont il est le centre. Seuls les autres boids qui se situent dans ce champ de vision affectent sa trajectoire.
Les boids adaptent leurs trajectoires en suivant ces 3 règles :
-
L’évitement : chaque boid s’écarte de ses voisins s’ils sont trop proches pour éviter les collisions.
-
L’alignement : chaque boid s'aligne avec la direction moyenne des voisins.
-
La cohésion : chaque boid se déplace vers la position moyenne des voisins
L'algorithme des Boids fait, en s'appuyant sur un ensemble de règles simples, émerger un comportement global plus complexe. Ce type d’algorithme est nommé algorithme émergent.
Quelques comportements qu'on peut observer en bidouillant les paramètres de l'algorithme :
- Lorsqu'on augmente la force de cohésion, les boids formeront pleins de petits groupes.
- Au contraire, lorsqu'on augmente l'évitement, les boids occuperont plus de place.
- Enfin, lorsqu'on réduit le champ de vision, les boids vont dans tous les sens, et ne parviennent pas à former une structure.
Applications
Le domaine où cet algorithme a été le plus influent est sans doute l'animation de foule de synthèse au cinéma. Les boids furent très vite reconnus comme prometteur car il suffit d'appliquer l'algorithme à une foule et de les laisser faire, sans avoir besoin de s'occuper de chaque individu. Et de fait, ils ont étés utilisés dans des films comme Batman Returns, Le Roi Lion ou encore Jurassic Parc (rien que ça).
Je vous laisse la vidéo de Foulosocopie sur le sujet :
Le modèle attira également l’attention des ornithologues et des biologistes, qui l’utilisent encore aujourd’hui pour étudier la structure des bancs de poissons ou troupeaux de moutons.
