Implemente el algoritmo Boids

18

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:

Dibujo crudo de dos "boids", uno hacia la izquierda y el otro hacia la derecha.

  • 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

Entrada:

5, 190 (5 boids, 190 cuadros)

Salida:

Animación de 190 cuadros del algoritmo Boids con 5 boids.

Criterio ganador

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

iPhoenix
fuente
77
"Por supuesto, hay más en el algoritmo, por lo que recomiendo consultar la fuente". ¿Es todo lo necesario aquí o no? Si no, recomendaría arreglar eso.
Jonathan Allan
1
Utilice el sandbox antes de publicar desafíos, como se recomienda en la página de preguntas .
flawr
@JonathanAllan Sí, todo lo necesario está aquí, pero en la fuente hay disponibles explicaciones más detalladas que pueden tener más sentido para otros usuarios.
iPhoenix
11
Este es un desafío interesante (encuentro fascinantes los comportamientos de congregación) pero necesitará estar bien especificado, especialmente para un código de golf, de lo contrario, la presión para reducir la longitud del código causará cada desviación posible del espíritu del desafío. ser incentivado
trichoplax

Respuestas:

7

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:

boids

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

Phlarx
fuente
1
No 2*PIse puede llegar TAUa guardar un byte?
Jonathan Frech
@ JonathanFrech Sí, puede; Originalmente tenía -PI, PI y yo iba por ese camino, pero me desvió.
Phlarx
Mi programa (que estaba escrito en js y html) no exportó un gif, pero dibujó una imagen y usé un programa de captura de pantalla y convertí el video que exportó a un gif. Sin embargo, hay una cosa que noté. Los boids tienen un contorno azul, que no sigue las especificaciones :)
iPhoenix
Solo otro recordatorio amistoso, esta respuesta no sigue las especificaciones, por lo que no obtendrá la recompensa.
iPhoenix
1
No sé de procesamiento, pero creo que se puede jugar golf las siguientes cosas: ,i,a ,i=0,y retire el i=0interior del bucle para. (-1 byte); frameCount%f==0a frameCount%f<1(1 byte); &&a &en el final if 2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6(-1 byte). Nuevamente, no estoy seguro de si esto es posible, pero dado que Processing parece bastante similar a Java, creo que lo es. Además, puedes intentar crear un gif con screentogif.com .
Kevin Cruijssen
4

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>

Patrick Roberts
fuente
Los boids no parecen interactuar cuando ejecuto el fragmento
Jo King
@JoKing debería arreglarse ahora
Patrick Roberts
El problema se debió a que el minificador de babel sombreó una variable global en una función con un nombre de parámetro, y la conversión implícita a un número no arrojó un error, por lo que la función simplemente falló en silencio y nunca detectó ningún vecino.
Patrick Roberts
Trataré de hacer una demostración interactiva mañana por la noche, pero me he quedado sin vapor por esta noche.
Patrick Roberts
Solo una nota: donde se lee t.a+v+l/10+f/50, si cambia eso a t.a+v/3+l/10+f/50, produce un comportamiento algo más interesante, pero el programa actual es más pequeño y aún no se ha especificado.
Patrick Roberts