Introducción

El algoritmo de Boids es una demostración relativamente simple del comportamiento emergente en un grupo. Tiene tres reglas principales, según lo descrito por su creador, Craig Reynolds:

El modelo básico de flocado consta de tres comportamientos de dirección simples que describen cómo un individuo boid maniobra en función de las posiciones y velocidades de sus compañeros cercanos:

• Separación : diríjase para evitar abarrotar a los compañeros locales.
• Alineación : diríjase hacia el rumbo promedio de los compañeros locales.
• Cohesión : dirígete para avanzar hacia la posición promedio de los compañeros locales.

Cada boid tiene acceso directo a la descripción geométrica de toda la escena, pero el agrupamiento requiere que reaccione solo a los compañeros de grupo dentro de un cierto vecindario pequeño a su alrededor. El vecindario se caracteriza por una distancia (medida desde el centro del boid) y un ángulo , medido desde la dirección de vuelo del boid. Los compañeros de manada fuera de este vecindario local son ignorados. El vecindario podría considerarse un modelo de percepción limitada (como el de un pez en aguas turbias), pero probablemente sea más correcto pensar que define la región en la que los compañeros de manada influyen en la dirección de un barco.

No soy perfecto para explicar las cosas, por lo que recomiendo consultar la fuente . También tiene algunas fotos súper informativas en su sitio.

Desafío

Dado el número de boids (entidades simuladas) y el número de cuadros, genera una animación de la simulación.

• Los boids deben representarse como un círculo rojo, con una línea dentro del círculo que muestre su rumbo, que es la dirección en la que apunta el boid:

• El ángulo de cada boid (como lo describe Reynolds) debe ser de 300 grados completos. (no 360)
• El encabezado inicial y la posición de cada boid deben ser uniformemente aleatorios (pero sembrados, de modo que la salida aún esté determinada), así como la posición.
• Si el radio de la boid es 1, entonces el radio de la vecindad debe ser 3.
• El número de boids será de 2 a 20.
• El número de fotogramas será de 1-5000
• La animación debe reproducirse con un mínimo de 10 milisegundos por fotograma y un máximo de 1 segundo por el número de boids. (2 boids = 2 segundos por fotograma máximo, 3 boids = 3 segundos por fotograma máximo, etc.)
• La animación de salida debe ser al menos 5 radios de boid por 5 radios de boid, multiplicado por la mitad del número de boid. Entonces, el tamaño mínimo para 2 boids sería de 10 radios de boid por 10 radios de boid, el mínimo para 3 boids sería de 15 radios de boid por 15 radios de boid, etc.
• El radio de cada boid debe ser un mínimo de 5 píxeles y un máximo de 50 píxeles.
• La velocidad de cada boid necesita ser limitada para que no se mueva más de 1/5 de su radio en un cuadro.
• La salida debe determinarse, de modo que la misma entrada produzca la misma salida si se ejecuta varias veces.
• Si un boid alcanza un borde, debe volver al otro lado. Del mismo modo, el vecindario alrededor de cada boid también debe envolverse alrededor de las fronteras.

Reglas para el algoritmo

En este caso, cada boid tiene un sector a su alrededor que abarca 300 grados, centrado en el encabezado de la boid. Cualquier otro boid en este "vecindario" se considera "vecinos" o (para usar el término de Reynolds) "compañeros de bandada".

1. Cada boid debe ajustar su rumbo para evitar colisiones y mantener una distancia cómoda de un radio de boid con sus vecinos. (Este es el aspecto de "Separación" del algoritmo. Se puede omitir el radio de boid, pero debe ser como una banda elástica, volviendo a su lugar).

2. Cada boid debe ajustar adicionalmente su rumbo para estar más cerca del rumbo promedio de los otros boids en su vecindario, siempre que no interfiera con la primera regla. (Este es el aspecto de "Alineación" del algoritmo)

3. Cada boid debe girar hacia la posición promedio de sus compañeros de manada, siempre que esto no cause colisión o interfiera significativamente con la segunda regla.

En su artículo sobre el tema , explica esto de la siguiente manera:

Para construir una bandada simulada, comenzamos con un modelo boid que admite vuelo geométrico. Agregamos comportamientos que corresponden a las fuerzas opuestas de evitar colisiones y la necesidad de unirse al rebaño. Expresados ​​brevemente como reglas, y en orden de precedencia decreciente, los comportamientos que conducen al flocado simulado son:

• Evitación de colisiones: evite colisiones con compañeros de manada cercanos
• Igualación de velocidad: intente igualar la velocidad con compañeros de banda cercanos
• Centrado de la parvada: intente permanecer cerca de los compañeros de bandada cercanos

Descripción más detallada del movimiento:

• La implementación estándar del algoritmo de Boids generalmente hace un cálculo para cada una de las reglas y las combina.
• Para la primera regla, el boid pasa por la lista de boids vecinos dentro de su vecindario, y si la distancia entre él y el vecino es menor que cierto valor, un vector que empuja el boid lejos de su vecino se aplica al encabezado del boid.
• Para la segunda regla, el boid calcula el encabezado promedio de sus vecinos y agrega una pequeña porción (usaremos 1/10 en este desafío) de la diferencia entre su encabezado actual y el encabezado promedio a su encabezado actual.
• Para la tercera y última regla, el boid promedia las posiciones de sus vecinos, calcula un vector que apunta hacia esta ubicación. Este vector se multiplica por un número aún menor que el que se usó para la regla 2 (para este desafío, se usará 1/50) y se aplica al encabezado.
• El boid se mueve en la dirección de su rumbo.

Aquí hay una útil implementación de pseudocódigo del algoritmo Boids.

Ejemplo de entrada y salida

5, 190 (5 boids, 190 cuadros)

Criterio ganador

Este es el código de golf , por lo que gana la solución más pequeña en bytes.

Procesamiento 3.3.6 (Java) ,932 931 940 928 957 917 904 bytes

^{-1 byte de Jonathan Frech
+11 bytes para que coincida mejor con la especificación
-2 bytes de Kevin Cruijssen
-12 bytes para cambiar args a t ()
+29 bytes porque estaba haciendo un fantasma incorrecto, vea la versión comentada a continuación
-40 bytes para usar para bucles en lugar de llamadas separadas para cada fantasma
-13 bytes para usar frameRate predeterminado, 30}

Bueno, es un comienzo para alguien que no practica 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));}}

No conozco ninguna forma razonable de ingresar datos en Processing, por lo que las dos primeras variables son las entradas (y no conté sus valores (5 bytes) hacia el conteo de bytes). Si esto es un problema, puedo probar otras cosas.

Tampoco conozco una buena forma de permitir probarlo en línea (el proyecto Processing.js no puede manejar este estilo de código) sin alojar las cosas yo mismo; y eso es algo que no estoy ansioso por intentar. Avíseme si hay algo inteligente que pueda hacer.

Código formateado, con comentarios

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));
  }
}

Salida de muestra

n = 15, cuadros = 400:

O, la misma animación, pero mostrando el vecindario de cada boid.

JavaScript (ES6) + HTML5, 1200 bytes

Aquí está mi solución actual usando la API de Canvas. El eval()devuelve una función curry cuya primera entrada es la Boidpoblación, y segundo es el número de cuadros de animación. Puede usar Infinitypara animación continua.

El eval(...)es 1187 bytes y <canvas id=c>es de 13 bytes, lo que hace un total de 1200. La CSS es innecesaria, pero por conveniencia, que le permite ver los bordes de la tela.

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>

Editar

Según lo solicitado, otro fragmento con una entrada para la población 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>