introduction

L' algorithme Boids est une démonstration relativement simple du comportement émergent dans un groupe. Il a trois règles principales, décrites par son créateur, Craig Reynolds:

Le modèle de flocage de base se compose de trois comportements de pilotage simples qui décrivent comment un individu boid manoeuvre en fonction des positions et des vitesses de ses compagnons de vol à proximité:

• Séparation : Barrez pour éviter l' encombrement locaux compagnons de groupe.
• Alignement : orientez-vous vers le cap moyen des copains locaux.
• Cohésion : orientez-vous vers la position moyenne des copains locaux.

Chaque boid a un accès direct à toute la description géométrique de la scène, mais le flocage exige qu'il ne réagisse qu'aux copains dans un certain petit quartier autour de lui. Le voisinage est caractérisé par une distance (mesurée à partir du centre du boïd) et un angle , mesuré à partir de la direction de vol du boïd. Les copains en dehors de ce quartier local sont ignorés. Le quartier pourrait être considéré comme un modèle de perception limitée (comme par les poissons dans l'eau trouble), mais il est probablement plus correct de le considérer comme définissant la région dans laquelle les copains influent sur la direction des boids.

Je ne suis pas parfait pour expliquer les choses, donc je recommande fortement de vérifier la source . Il a également quelques photos super informatives sur son site.

Défi

Compte tenu du nombre de boids (entités simulées) et du nombre d'images, sortez une animation de la simulation.

• Les boids doivent être rendus sous la forme d'un cercle rouge, avec une ligne à l'intérieur du cercle indiquant son cap, qui est la direction dans laquelle le boid pointe:

• L'angle de chaque boid (comme décrit par Reynolds) doit être de 300 degrés. (pas 360)
• Le cap et la position de départ de chaque boid doivent être uniformément aléatoires (mais prédéfinis, afin que la sortie soit toujours déterminée), ainsi que la position.
• Si le rayon du boid est 1, alors le rayon du voisinage devrait être 3.
• Le nombre de boids sera compris entre 2 et 20.
• Le nombre d'images sera compris entre 1 et 5 000
• L'animation doit être lue avec un minimum de 10 millisecondes par image et un maximum de 1 seconde le nombre de boids. (2 boids = 2 secondes par image max, 3 boids = 3 secondes par image max, et cetera)
• L'animation de sortie doit être d'au moins 5 rayons boid par 5 rayons boid, multipliée par la moitié du nombre de boids. Ainsi, la taille minimale pour 2 boids serait de 10 rayons boid par 10 rayons boid, le minimum pour 3 boids serait de 15 rayons boid par 15 rayons boid, et cetera.
• Le rayon de chaque boid doit être au minimum de 5 pixels et au maximum de 50 pixels.
• La vitesse de chaque boid doit être limitée afin qu'il ne bouge pas de plus de 1/5 de son rayon dans une image.
• La sortie doit être déterminée pour que la même entrée produise la même sortie si elle est exécutée plusieurs fois.
• Si un boid atteint une bordure, il doit revenir de l'autre côté. De même, le quartier autour de chaque boid devrait également envelopper les frontières.

Règles pour l'algorithme

Dans ce cas, chaque boid a un secteur autour de lui s'étendant sur 300 degrés, centré sur le cap du boid. Tous les autres boids de ce "quartier" sont considérés comme des "voisins", ou (pour reprendre le terme de Reynolds) des "copains".

1. Chaque boid doit ajuster son cap pour éviter les collisions et maintenir une distance confortable d'un rayon de boid avec ses voisins. (Il s'agit de l'aspect "Séparation" de l'algorithme. Le rayon d'un boid peut être contourné, mais il devrait être comme une bande élastique, se remettant en place.)

2. Chaque boid doit en outre ajuster son cap pour être plus proche du cap moyen des autres boids de son voisinage, tant qu'il n'interfère pas avec la première règle. (Il s'agit de l'aspect "Alignement" de l'algorithme)

3. Chaque boid doit se tourner vers la position moyenne de ses copains, tant que cela ne provoque pas de collision ou n'interfère pas de manière significative avec la deuxième règle.

Dans son article sur le sujet , il l'explique ainsi:

Pour construire un troupeau simulé, nous commençons avec un modèle boid qui prend en charge le vol géométrique. Nous ajoutons des comportements qui correspondent aux forces opposées d'évitement des collisions et à l'envie de rejoindre le troupeau. Déclarés brièvement en tant que règles et par ordre de priorité décroissante, les comportements qui conduisent à un flocage simulé sont les suivants:

• Évitement des collisions: évitez les collisions avec les copains voisins
• Correspondance de vitesse: essayez de faire correspondre la vitesse avec les copains voisins
• Centrage du troupeau: essayez de rester près des copains voisins

Description plus détaillée du mouvement:

• L'implémentation standard de l'algorithme Boids effectue généralement un calcul pour chacune des règles et les fusionne.
• Pour la première règle, le boid passe par la liste des boids voisins dans son voisinage, et si la distance entre lui et le voisin est inférieure à une certaine valeur, un vecteur éloignant le boid de son voisin est appliqué à l'en-tête du boid.
• Pour la deuxième règle, le boid calcule le cap moyen de ses voisins et ajoute une petite partie (nous utiliserons 1/10 dans ce défi) de la différence entre son cap actuel et le cap moyen à son cap actuel.
• Pour la troisième et dernière règle, le boid fait la moyenne des positions de ses voisins, calcule un vecteur qui pointe vers cet emplacement. Ce vecteur est multiplié par un nombre encore plus petit que celui qui était utilisé pour la règle 2 (pour ce défi, 1/50 sera utilisé) et appliqué à la rubrique.
• Le boid est ensuite déplacé dans le sens de son cap

Voici une implémentation pseudocode utile de l'algorithme Boids.

Exemple d'entrée et de sortie

5, 190 (5 boids, 190 images)

Critère gagnant

Il s'agit de code-golf , donc la plus petite solution en octets l'emporte.

Traitement 3.3.6 (Java) ,932 931 940 928 957 917 904 octets

^{-1 octet de Jonathan Frech
+11 octets pour mieux correspondre à la spécification
-2 octets de Kevin Cruijssen
-12 octets pour changer les arguments en t ()
+29 octets parce que je faisais du fantôme mal, voir la version commentée ci-dessous
-40 octets pour utiliser pour boucles au lieu d'appels séparés pour chaque fantôme
-13 octets pour l'utilisation du frameRate par défaut, 30}

Eh bien, c'est un début, pour quelqu'un qui ne pratique pas le Java-golf. :)

int n=15,f=400,i,j,z=255,w=500;float d=200./n;PVector m;B[]a=new B[n];void setup(){size(500,500);fill(z,0,0);randomSeed(n);for(i=0;i<n;a[i++]=new B(new PVector(random(w),random(w)),m.fromAngle(random(TAU))));}void draw(){background(z);for(B b:a)b.u();if(frameCount%f<1)setup();}class B{PVector p,v,e,q,r;ArrayList<B>n;B(PVector m,PVector o){p=m;v=o;}void u(){e=v.copy();n=new ArrayList();for(B b:a){if(b!=this)for(i=-w;i<=w;i+=w)for(j=-w;j<=w;j+=w)t(i,j,b);}if(n.size()>0){q=new PVector();r=q.copy();for(B b:n){q.add(b.v);r.add(b.p);if(p.dist(b.p)<=d)e.add(p).sub(b.p);}e.add(q.div(n.size()).sub(v).div(10));e.add(r.div(n.size()).sub(p).div(50));}p.add(e.limit(d/10));v=e.mult(10);p.set((p.x+w)%w,(p.y+w)%w);noStroke();ellipse(p.x,p.y,d,d);stroke(0,0,z);line(p.x,p.y,p.x+v.x,p.y+v.y);}void t(int x,int y,B o){m=o.p.copy().add(x,y);if(2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6)n.add(new B(m,o.v));}}

Je ne connais aucun moyen raisonnable de faire des entrées dans le traitement, donc les deux premières variables sont les entrées (et je n'ai pas compté leurs valeurs (5 octets) vers le nombre d'octets). Si c'est un problème, je peux essayer d'autres choses.

Je ne connais pas non plus de bon moyen de permettre de l'essayer en ligne (le projet Processing.js ne peut pas gérer ce style de code) sans héberger moi-même les choses; et c'est quelque chose que je ne veux pas essayer. Faites-moi savoir si je peux faire quelque chose d'intelligent.

Code formaté, avec commentaires

int n=15, // Number of boids
    f=400, // Number of frames
    i,j,z=255,w=500; // temp*2, and two constants
float d=200./n; // Boid diameter
PVector m; // temp
B[]a=new B[n];
void setup(){ // This is automatically called at startup
  size(500,500); // Can't use variables for this without extra bytes for settings()
  fill(z,0,0);
  randomSeed(n); // seeded from number of Boids, so that n=19 is very different from n=20
  for(i=0;i<n;a[i++]=new B(new PVector(random(w),random(w)),m.fromAngle(random(TAU))));
}
void draw(){ // This is automatically called each frame
  background(z);
  for(B b:a)
    b.u();
  if(frameCount%f<1) // When desired frames length is hit, reset everything.
    setup();         // Could also use noLoop() instead of setup() to just stop instead.
                     // Or, remove this if statement altogether to go on to infinity.
}
class B{ // Boid
  PVector p,v,e,q,r; // Position, Velocity, Next velocity, and two temp vectors
  ArrayList<B>n; // List of neighbors
  B(PVector m,PVector o){
    p=m;
    v=o;
  }
  void u(){ // Update function, does rules and redraw for this Boid
    e=v.copy();
    n=new ArrayList();
    for(B b:a){ // Test a Boid and its eight ghosts for neighborship
      if(b!=this) // Note: Assumes neighborhood diameter < min(width,height)
        // The ghosts are to check if it'd be closer to measure by wrapping
        // We need eight for wrapping north, east, south, west, northeast,
        // northwest, southeast, and southwest. And also the non-wrapped one.
        // The above assumption ensures that each ghost is further apart than
        // the neighborhood diameter, meaning that only one neighbor might be
        // found for each boid. To test this, place a boid in each corner, right
        // to the edge, facing away from center. Each boid should find three
        // neighbors, that are the three other boids.
        for(i=-w;i<=w;i+=w)for(j=-w;j<=w;j+=w)t(i,j,b);
    }
    if(n.size()>0){
      q=new PVector();
      r=q.copy();
      for(B b:n){
        q.add(b.v); // Velocity matching, pt 1
        r.add(b.p); // Flock centering, pt 1
        if(p.dist(b.p)<=d)  
          e.add(p).sub(b.p); // Collision avoidance
      }
      e.add(q.div(n.size()).sub(v).div(10)); // Velocity matching, pt 2
      e.add(r.div(n.size()).sub(p).div(50)); // Flock centering, pt 2
    }
    p.add(e.limit(d/10)); // Update vectors
    v=e.mult(10);
    p.set((p.x+w)%w,(p.y+w)%w); // Wrapping
    noStroke();
    ellipse(p.x,p.y,d,d); // Draw Boid, finally
    stroke(0,0,z);
    line(p.x,p.y,p.x+v.x,p.y+v.y);
  }
  void t(int x,int y,B o){ // Test if a Boid (or a ghost) is a neighbor
    m=o.p.copy().add(x,y);
    if(2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6)
      n.add(new B(m,o.v));
  }
}

Exemple de sortie

n = 15, images = 400:

Ou, la même animation, mais montrant le voisinage de chaque boid.

JavaScript (ES6) + HTML5, 1200 octets

Voici ma solution actuelle utilisant l'API Canvas. La eval()renvoie une fonction curry dont la première entrée est la Boidpopulation et la seconde le nombre d'images d'animation. Vous pouvez utiliser Infinitypour une animation continue.

Le eval(...)est de 1187 octets et <canvas id=c>est de 13 octets, soit un total de 1200. Le CSS n'est pas nécessaire, mais pour plus de commodité, il vous permet de voir les bords de la toile.

eval("L7F7{function B8{t=this,t.a=o8*T,t.x=o8*S,t.y=o8*S}C=this.c,D=C.getContext`2d`,({abs:z,random:o,atan2:k,cos:u,sin:g,PI:P,T=2*P,G={c:_7A[r='filter'](b7b!=t)[i](9)79)),n:_7A[r](b7b!=t)[i](9)7({a,x,y:y-S})),s:_7A[r](b7b!=t)[i](9)7({a,x,y:y+S})),e:_7A[r](b7b!=t)[i](9)7({a,x:x-S,y})),w:_7A[r](b7b!=t)[i](9)7({a,x:x+S,y}))},M=I7[I,I+T,I-T][p]((a,x)7z(x)<z(a)?x:a)}=Math),B.prototype={d8{with(D)save8,translate(x,y),rotate(a),beginPath8,arc(0,0,5,0,T),fillStyle='red',fill8,beginPath8,moveTo(0,0),lineTo(10,0),strokeStyle='blue',stroke8,restore8},n:_7(({c,n,s,e,w}=G),c8.concat(n8,s8,e8,w8)[r](b7(d=b.x-x,f=b.y-y,400>d*d+f*f&&z(z(k(f,d)-a)/P-1)>1/6))),s8{q=(j=t.n8).length,v=t.v8||0,l=t.l8||0,f=t.f8||0,a=t.a=(t.a+v+l/10+f/50)%T,t.x=(x+u(a)+S)%S,t.y=(y+g(a)+S)%S},v:_7([d,f]=j[r](b7225>(b.x-x)**2+(b.y-y)**2)[p='reduce'](([d,f],b)7[x+d-b.x,y+f-b.y],[0,0]),d||f?M(k(f,d)-a):0),l:_7j[i](b7M(b.a-a))[p]((a,x)7a+x,0)/q,f:_7([d,f]=j[p](([d,f],b)7[d+b.x,f+b.y],[-x*q,-y*q]),d||f?M(k(f,d)-a):0)},S=C.width=C.height=50*L,A=Array(L).fill().map(_7new B),R=_7{D.clearRect(0,0,S,S),A[i='map'](b79=b).d8),A[i](b79=t=b).s8),F--&&setTimeout(R,10)},R8}".replace(/[789]/g,m=>['=>','()','({a,x,y}'][m-7]))
(10)(Infinity)

canvas{border:1px solid}

<canvas id=c>

Éditer

Comme demandé, un autre extrait avec une entrée pour la population Boid:

b.onchange=()=>{eval("L7F7{function B8{t=this,t.a=o8*T,t.x=o8*S,t.y=o8*S}C=this.c,D=C.getContext`2d`,({abs:z,random:o,atan2:k,cos:u,sin:g,PI:P,T=2*P,G={c:_7A[r='filter'](b7b!=t)[i](9)79)),n:_7A[r](b7b!=t)[i](9)7({a,x,y:y-S})),s:_7A[r](b7b!=t)[i](9)7({a,x,y:y+S})),e:_7A[r](b7b!=t)[i](9)7({a,x:x-S,y})),w:_7A[r](b7b!=t)[i](9)7({a,x:x+S,y}))},M=I7[I,I+T,I-T][p]((a,x)7z(x)<z(a)?x:a)}=Math),B.prototype={d8{with(D)save8,translate(x,y),rotate(a),beginPath8,arc(0,0,5,0,T),fillStyle='red',fill8,beginPath8,moveTo(0,0),lineTo(10,0),strokeStyle='blue',stroke8,restore8},n:_7(({c,n,s,e,w}=G),c8.concat(n8,s8,e8,w8)[r](b7(d=b.x-x,f=b.y-y,400>d*d+f*f&&z(z(k(f,d)-a)/P-1)>1/6))),s8{q=(j=t.n8).length,v=t.v8||0,l=t.l8||0,f=t.f8||0,a=t.a=(t.a+v/3+l/10+f/50)%T,t.x=(x+u(a)+S)%S,t.y=(y+g(a)+S)%S},v:_7([d,f]=j[r](b7225>(b.x-x)**2+(b.y-y)**2)[p='reduce'](([d,f],b)7[x+d-b.x,y+f-b.y],[0,0]),d||f?M(k(f,d)-a):0),l:_7j[i](b7M(b.a-a))[p]((a,x)7a+x,0)/q,f:_7([d,f]=j[p](([d,f],b)7[d+b.x,f+b.y],[-x*q,-y*q]),d||f?M(k(f,d)-a):0)},S=C.width=C.height=50*L,A=Array(L).fill().map(_7new B),R=_7{D.clearRect(0,0,S,S),A[i='map'](b79=b).d8),A[i](b79=t=b).s8),F--&&setTimeout(R,10)},R8}".replace(/[789]/g,m=>['=>','()','({a,x,y}'][m-7]))(+b.value)(Infinity);b.remove()}

input{display:block}canvas{border:1px solid}

<input id=b><canvas id=c>