🐦 Boids 3D — Agents en nuée

À chaque image, pour un boid i de vitesse v et de position p, la simulation calcule trois vecteurs de pilotage dans le rayon de perception r : Séparation S = somme de (p_i - p_j) / |p_i - p_j|^2 pour les voisins proches j ; Alignement A = vitesse moyenne des voisins normalisée à la vitesse cible ; Cohésion C = (position moyenne des voisins - p_i) normalisée et mise à l'échelle vers la vitesse cible. La nouvelle vitesse est v' = v + w_s * S + w_a * A + w_c * C, où w_s, w_a, w_c sont les poids des curseurs. Chaque vecteur de force est plafonné à une magnitude maximale (MAX_FORCE) pour garder un mouvement fluide, et la vitesse finale est plafonnée à 1,4 fois la vitesse de base.

Une implémentation naïve vérifie chaque paire de boids pour la proximité, coûtant O(N^2) opérations par image — trop lent pour 600 agents à 60 images/s. Cette simulation utilise une grille de hachage spatial : à chaque image, tous les boids sont répartis dans des cellules de grille de taille égale au rayon de perception. Pour trouver ses voisins, un boid ne vérifie que les 3x3x3 = 27 cellules environnantes au lieu de la liste complète, réduisant le coût moyen à O(N * k) où k est le nombre de boids par cellule locale. Le moteur de rendu WebGL InstancedMesh dessine ensuite tous les cônes en un seul appel de dessin, gardant la charge GPU minimale.

La recherche empirique confirme que le comportement de nuée réel est local et décentralisé, conformément au principe de Boids. Cependant, les études sur les nuées d'étourneaux (notamment par Ballerini et al., 2008) montrent que les étourneaux réels interagissent avec un nombre à peu près fixe de voisins les plus proches — environ six ou sept — quelle que soit la densité, plutôt qu'avec chaque agent dans un rayon fixe. Les animaux réels intègrent aussi des limites d'angle de vision, une tolérance au bruit et des manœuvres d'échappement spécifiques aux prédateurs. Boids est un modèle qualitatif précis du mécanisme émergent mais n'est pas une reconstruction biologique quantitativement exacte.

Craig W. Reynolds, alors chez Symbolics, a présenté l'algorithme Boids dans l'article « Flocks, Herds, and Schools: A Distributed Behavioral Model » à SIGGRAPH 1987. Reynolds a inventé le mot « boid » comme contraction de « bird-oid object ». L'article était révolutionnaire car il montrait qu'un mouvement animal collectif convaincant pouvait naître d'une poignée de règles locales simples plutôt que de trajectoires scriptées, lançant effectivement le domaine de la simulation d'agents autonomes en infographie.

Boids appartient à une famille plus large de modèles à base d'agents et d'essaims. Sont étroitement liés l'optimisation par colonies de fourmis (ACO), où des fourmis virtuelles déposent des pistes de phéromones qui guident la colonie vers la nourriture ; l'optimisation par essaims particulaires (PSO), qui utilise des mises à jour de vitesse de style Boids pour rechercher des solutions optimales ; les comportements de pilotage ultérieurs de Reynolds (rechercher, fuir, poursuivre, esquiver, errer) ; et les automates cellulaires comme le Jeu de la vie de Conway. En biologie, le même cadre est utilisé pour modéliser les essaims de criquets, les bancs de sardines, et même le mouvement collectif des bactéries et des piétons humains.

L'algorithme de Reynolds, ou ses dérivés, est utilisé dans l'IA de foule et de trafic des jeux vidéo (la série Half-Life, les systèmes d'IA d'Unreal Engine), les effets visuels de films pour de grandes foules de créatures (Le Seigneur des anneaux, World War Z), et les simulations architecturales de flux piétonnier pour la sécurité des stades et des pôles de transit. En robotique et en aérospatiale, la coordination d'essaims multi-UAV adopte la même structure séparation-alignement-cohésion pour garder les formations de drones sans collision tout en poursuivant un objectif collectif. Boids apparaît aussi dans la recherche sur le routage réseau, où les paquets sont traités comme des agents naviguant dans la congestion.

Les domaines de recherche actifs incluent les règles d'interaction topologique (voisins définis par rang plutôt que par distance), le comportement de nuée robuste au bruit près de la transition ordre-désordre (un lien avec la physique statistique et la matière active), les boids pilotés par les données calibrés à partir de trajectoires animales suivies par GPS, et les essaims hétérogènes où les agents ont des rôles ou capacités différents. Côté ingénierie, le contrôle décentralisé en temps réel de centaines de drones physiques — n'utilisant que la communication sans fil locale et la détection embarquée — est un problème ouvert qui s'appuie largement sur la théorie de Boids, tout comme la conception d'essaims résilients qui maintiennent leur cohésion quand certains agents tombent en panne.