TypeScript : simulation de vols d'oiseaux

Si vous vous intéressez : aux simulations 🖥, au fonctionnement de l'univers 💫, à la façon dont une colonie de fourmis parvient à rassembler 125 kg de nourriture par jour 🐜, à l'émergence des nuées d'oiseaux 🦅, alors la modélisation des systèmes naturels est sans nul doute le sujet qui vous convient.

Les volées d'oiseaux sont un exemple de systèmes naturels. Simuler une volée d'oiseaux est étonnamment simple. Il existe 3 règles de base :

• La cohésion : Les oiseaux vont essayer de se déplacer vers leurs semblables.
• Séparation : Les oiseaux essaieront d'éviter de s'écraser sur d'autres oiseaux.
• Alignement : Les oiseaux essaieront de se déplacer dans la même direction que les autres oiseaux.

En utilisant ces quelques règles, nous pouvons créer des simulations impressionnantes et réalistes.

Les trois règles mentionnées ci-dessus sont connues sous le nom d'algorithme Boids, développé vers la fin des années 80 par Craig Reynolds et mis en œuvre, par la suite, d'innombrables fois. D'après Wikipédia, un boid est défini comme suit :

Le nom « boid » correspond à une version abrégée de « bird-oid object », qui fait référence à un objet ressemblant à un oiseau. « Boid » est également une prononciation du dialecte métropolitain de New York pour « oiseau ».

Cet article est un énième tutoriel sur les phénomènes étonnants des comportements émergents basés sur des règles simples.

1. Structure de base

J'ai créé un « moteur de rendu » pour TypeScript qui me permet de prototyper rapidement des animations en utilisant Canvas HTML5. Vous pouvez le consulter sur Github. C'est ce que je vais utiliser ici.

Créons notre classe boids qui contiendra notre moteur de rendu (rendered), et tous les oiseaux suivis par le système.

Dans notre constructeur, nous définissons d'abord le canevas où les oiseaux seront rendus avec la commande « new RenderingLayer() ».

Nous y ajouterons ensuite quelques centaines d'oiseaux pour effectuer la simulation. Ces oiseaux commenceront à des emplacements aléatoires sur l'écran.

Nous pouvons alors lancer le rendu en appelant la méthode start sur le moteur.

class Boids {
  birds: Array<IBird>;
  engine: IEngine;
  constructor() {
    const birdLayer = new RenderingLayer(LayerIndex.BIRDS, LayerType.DYNAMIC);

    this.birds = [];
    for (let i = 0; i < BIRD_COUNT; i++) {
      // add a bird at a random location in our layer.
      const x = Math.random() * this.birdLayer.getWidth();
      const y = Math.random() * this.birdLayer.getHeight();
      const bird = new Bird(this, x, y, birdLayer.getWidth(), birdLayer.getHeight());

      this.birds.push(bird);
      birdLayer.addEntity(bird);
    }

    this.engine = new Engine();
    this.engine.registerLayer(birdLayer);
    this.engine.start();
  }
}

1.1 Classe d'oiseaux de base

Chaque oiseau a une position, une vitesse et un vecteur d'accélération. Comme nous l'avons appris en physique, la position est calculée à partir de la vitesse, qui à son tour est calculée en fonction de l'accélération. L'accélération est calculée par l'équation suivante :

Force = MasseAccélération donc accélération= force/masse.

Dans un univers où il n'y a pas de masse, la formule utilisée pour notre simulation serait Accélération = Force.

Ici, la vitesse est initialement donnée en fonction d'un angle de départ aléatoire. La composante X de notre vecteur de vitesse peut être trouvée en utilisant le cosinus de notre angle tandis que la composante Y peut être trouvée en utilisant le sinus.

Cependant, comme il s'agit de mathématiques graphiques, les angles ne sont pas donnés en degrés, mais en radians.

Par conséquent, nous devons convertir 0-360° en radians.

Nous normalisons ensuite ce vecteur pour qu'il soit de longueur un. C'est important, car sans cela, les oiseaux qui vont vers des angles de 45° seront déplacés plus loin que ceux qui vont vers des angles de 90° (Indice : a²+b² = c²). Cependant, ce vecteur unitaire signifie que les oiseaux se déplaceront de 1 pixel, toutes les 16 ms (1000 ms / 60 fps = 16 ms par image). Modifions cela en multipliant le résultat par la vitesse de l'oiseau. Cela donnera une vitesse de : 100 px par 1000 ms. Ou 100px/seconde.

export default class Bird implements IBird {
  boids: Boids;
  position: Vector2D;
  velocity: Vector2D;
  acceleration: Vector2D;

  constructor(boids: Boids, initialX: number, initialY: number, maxX: number, maxY: number) {
    this.boids = boids;

    this.maxX = maxX;
    this.maxY = maxY;

    this.position = new Vector2D(initialX, initialY);
    const randomAngle = fromDegree(Math.random() * 360);
    this.velocity = new Vector2D(Math.cos(randomAngle), Math.sin(randomAngle))
      .normalize()
      .multiply(BIRD_SPEED);
    this.acceleration = Vector2D.ZERO();
  }
}

Nous pouvons par la suite attacher une fonction de rendu à notre oiseau.

render(context: CanvasRenderingContext2D) {
      this.rotate(context); // rotate to bird's angle.
      context.strokeStyle = 'red';
      context.beginPath();
      context.moveTo(this.position.x1 + BIRD_WIDTH/2, this.position.x2);
      context.lineTo(this.position.x1 - BIRD_WIDTH/2, this.position.x2 + BIRD_HEIGHT/2);
      context.lineTo(this.position.x1 - BIRD_WIDTH/2, this.position.x2 - BIRD_HEIGHT/2);
      context.closePath();
      context.stroke();
      this.unrotate(context); // restore canvas orientation
  }

  rotate(context: CanvasRenderingContext2D) {
      // Move origin point to the center of the bird
      context.translate(this.position.x1, this.position.x2);
      // Rotate about the bird's center by x degrees
      context.rotate(getAngle(this.velocity));
      // Return to the original origin
      context.translate(-this.position.x1, -this.position.x2);
  }

  unrotate(context: CanvasRenderingContext2D) {
      // Move origin point to the center of the bird
      context.translate(this.position.x1, this.position.x2);
      // Rotate about the bird's center by -x degrees (undoing rotation)
      context.rotate(-getAngle(this.velocity));
      // Move origin back to the origin.
      context.translate(-this.position.x1, -this.position.x2);
  }

Puisque nous voulons que notre oiseau ait une orientation basée sur sa vélocité, nous devons faire pivoter le canevas, puis dessiner l'oiseau, puis annuler la rotation afin que le prochain oiseau puisse être affiché correctement.

Ici, un oiseau est représenté par un simple triangle.

J'opte pour une rotation selon les valeurs opposées au lieu de sauvegarder les états du canevas et de restaurer le canevas pour la performance.

Nous nous retrouvons déjà avec un désordre aléatoire intéressant.

1.2 Ajouter de la vélocité!

En utilisant le moteur, nous pouvons facilement ajouter de la vélocité. Nous ajoutons une fonction de mise à jour (qui est une méthode optionnelle sur l'interface IEntity) et prenons en compte le temps depuis le dernier rendu pour obtenir un mouvement fluide. L'utilisation du deltaTime est utile pour les « framerates » qui peuvent ne pas être constant (par exemple, passer de 30 fps à 60 fps entraînerait un mauvais calcul de la position).

La fonction checkBoundary() fait simplement passer l'oiseau de l'autre côté de l'écran.

update(deltaTime: number) {
    this.position.add(
        this.velocity
            .clone()
            .multiply(deltaTime)
    );
    this.checkBoundary();
}

Ajout de la vélocité à la position

Pour obtenir la position, nous utilisons la vélocité et la multiplions par le temps pendant lequel cette vélocité a été maintenue. Dans ce cas, la vitesse sera maintenue pendant environ 16 ms, ce qui signifie qu'à 100 px/s, le boid se sera déplacé de 1,6px.

Et avec cela, nous sommes maintenant prêts à changer leur comportement!

2. Implémentation des règles de boid

Dans mon implémentation, la performance est un facteur important, surtout parce qu'elle est exécutée en JavaScript (nous savons tous que ce n'est pas très performant...).

Le pseudo-code de l'algorithme de Boids est à l'origine de O(rN²) où r est le nombre de règles, dans ce cas 3. J'ai choisi d'augmenter les performances en supprimant les boucles internes consécutives. Cela se fait grâce à des accumulateurs, ils additionnent les valeurs de chaque boid, avant d'être calculés. Cela réduit la complexité à O(N²).

Une nouvelle fonction permettant d'effectuer toutes les manœuvres aidera à séparer notre code :

• À chaque image, les accumulateurs de règles sont remis à zéro, puis recalculés. L'accélération est définie comme la somme de toutes les règles de boid.
• Les oiseaux ne peuvent voir les autres oiseaux que s'ils sont proches, car les oiseaux ne sont pas omnipotents.
• La vitesse est ensuite calculée à partir de l'accélération.
• En fixant la magnitude de notre vitesse à la vitesse maximale des oiseaux, on s'assure que les oiseaux ne finissent pas par aller à la vitesse de la lumière ⚡

performManeuvers(birds: Array<IBird>) {
    this.resetAccumulators();

    let birdsSeen = 0;
    for(let n = 0; n<birds.length; n++) {
        if(birds[n] !== this) {
            if(birds[n].position.distance(this.position) < BIRD_VISUAL_RANGE) {
                birdsSeen += 1;
                for(let r = 0; r<this.rules.length; r++) {
                    this.rules[r].accumulate(birds[n]);
                }
            }
        }
    }

    for(let r = 0; r<this.rules.length; r++) {
        this.acceleration.add(
            this.rules[r].perform(birdsSeen)
        );
    }

    this.velocity
        .add(this.acceleration)
        .normalize()
        .multiply(BIRD_SPEED);

2.1 La cohésion

La cohésion signifie que les oiseaux vont essayer de se déplacer vers le centre de masse des oiseaux voisins. Pour ce faire, il suffit d'additionner les positions des oiseaux proches, puis de trouver la distance par rapport à la position de l'oiseau actuel.

La position des oiseaux proches est additionnée en cumulant leurs positions.

accumulate(bird: IBird) {
    this.value.add(bird.position);
}

Puis la règle est exécutée en divisant par le nombre d'oiseaux vus, et en trouvant la distance entre l'oiseau actuel et le centre de masse.

performCohesion(birdCount: number): Vector2D {
      return this.cohesionAccumulator
          .divide(birdCount)
          .sub(this.position)
          .divide(BIRD_COHESION_RESISTANCE);
  }

Une constante peut être utilisée pour résister à cette force de cohésion.

Le résultat est déjà une animation relativement satisfaisante.

Cependant, il y a un problème... Tous les oiseaux entrent en collision et ne forment qu'un seul point. C'est là que la deuxième règle entre en jeu...

2.2 La séparation

La séparation corrige le problème apporté par la cohésion, il n'est pas naturel que des oiseaux se heurtent à leur pair et tombent du ciel 💀. Une nouvelle règle - la séparation - est créée pour maintenir les oiseaux à une certaine distance des autres oiseaux.

accumulateSeparation(bird: IBird) {
    const distance = bird.position
        .clone()
        .sub(this.position);

    if (distance.magnitude() < BIRD_SEPARATION_DISTANCE) {
        this.separationAccumulator.sub(distance);
    }
}

Dans ce cas, on cumule la distance entre deux oiseaux (s'ils sont à distance de séparation).

Nous pouvons ajouter cette valeur directement à la vélocité pour obtenir le facteur de séparation.

2.3 L'alignement

Bien que nous ayons résolu le problème de la cohésion en ajoutant la règle de séparation, un nouveau problème se pose... Les oiseaux vont simplement se regrouper en une boule, et finir par annuler le mouvement. Pour résoudre ce problème, nous pouvons ajouter une nouvelle force alignant les oiseaux dans la direction du mouvement.

L'alignement est défini en prenant la vitesse moyenne des oiseaux à proximité, et en y soustrayant notre vitesse:

performAlignment(birdCount: number): Vector2D {
    return this.nearbySumOfVelocities
        .divide(birdCount) // average velocity by dividing
        .normalize()
        .multiply(BIRD_SPEED)
        .sub(this.velocity)     // subtract our velocity to get the force
        .multiply(BIRD_ALIGNMENT_EAGERNESS);
}

La constante d'empressement d'alignement des oiseaux est une métavariable nous permettant de changer le comportement du troupeau à partir d'un fichier de constantes.

Et voilà, nous l'avons. Ajoutez les trois règles ensemble... Changez les valeurs de certaines métavariables... et nous obtenons la simulation de vol.

3. Les extras

1. Recherche originale par Craig Reynolds
2. Boids source code on Github
3. TypeScript Render Engine on Github

Autres idées d'amélioration :

1. La faim, l'épuisement, le changement de vitesse maximum (avant la mort), l'âge;
2. Prédateurs, accouplement, pondération différente des règles en fonction du comportement;
3. Algorithme génétique!

Si vous voulez voir davantage de nos articles, jetez un coup d'œil à la section de notre blog consacrée au développement logiciels.

Je voulais ajouter un fond agréable pour compléter la simulation de vol, donc j'en ai fait un en utilisant le bruit de Perlin