Implementar o algoritmo Boids

18

Introdução

O algoritmo de Boids é uma demonstração relativamente simples de comportamento emergente em um grupo. Ele tem três regras principais, conforme descrito por seu criador, Craig Reynolds:

O modelo básico de flocagem consiste em três comportamentos simples de direção que descrevem como um indivíduo faz manobras baseadas nas posições e velocidades de seus companheiros próximos:

  • Separação : orientar para evitar aglomerar companheiros de rebanho locais.
  • Alinhamento : direcione para a direção média dos companheiros de bando locais.
  • Coesão : siga para a posição média dos companheiros de bando locais.

Cada boid tem acesso direto à descrição geométrica de toda a cena, mas o rebanho exige que ele reaja apenas aos companheiros de rebanho dentro de um determinado bairro pequeno ao seu redor. A vizinhança é caracterizada por uma distância (medida a partir do centro do boid) e um ângulo , medido a partir da direção de vôo do boid. Companheiros de rebanho fora deste bairro local são ignorados. O bairro poderia ser considerado um modelo de percepção limitada (como em peixes em águas escuras), mas provavelmente é mais correto pensar nele como definindo a região na qual os companheiros de rebanho influenciam a direção.

Eu não sou perfeito ao explicar as coisas, por isso recomendo verificar a fonte . Ele também tem algumas fotos super informativas em seu site.

Desafio

Dado o número de boids (entidades simuladas) e o número de quadros, produz uma animação da simulação.

  • Os boids devem ser renderizados como um círculo vermelho, com uma linha dentro do círculo mostrando seu cabeçalho, que é a direção em que o boid está apontando:

Desenho bruto de dois "boids", um voltado para a esquerda e outro voltado para a direita.

  • O ângulo de cada boid (como descrito por Reynolds) deve ser de 300 graus. (não 360)
  • O cabeçalho inicial e a posição de cada boid devem ser uniformemente aleatórios (mas semeados, para que a saída ainda seja determinada), bem como a posição.
  • Se o raio do boid for 1, o raio da vizinhança deve ser 3.
  • O número de boids estará entre 2-20.
  • O número de quadros será de 1-5000
  • A animação deve ser reproduzida com no mínimo 10 milissegundos por quadro e no máximo 1 segundo vezes o número de boids. (2 boids = 2 segundos por quadro no máximo, 3 boids = 3 segundos por quadro no máximo, etc.)
  • A animação de saída deve ter pelo menos 5 raios-x por 5 raios-x, vezes a metade do número de boids. Portanto, o tamanho mínimo para 2 boids seria 10 boid-raio por 10 boid-raio, o mínimo para 3 boids seria 15 boid-raio por 15 boid-raio, etc.
  • O raio de cada boid deve ter no mínimo 5 pixels e no máximo 50 pixels.
  • A velocidade de cada boid precisa ser limitada para que não mova mais de 1/5 do seu raio em um quadro.
  • A saída precisa ser determinada, para que a mesma entrada produza a mesma saída se for executada várias vezes.
  • Se um boid atingir uma borda, ele deve voltar para o outro lado. Da mesma forma, a vizinhança em torno de cada boid também deve envolver as fronteiras.

Regras para o algoritmo

Nesse caso, cada boid possui um setor em torno de 300 graus, centrado no cabeçalho do boid. Quaisquer outros boids nesse "bairro" são considerados "vizinhos" ou (para usar o termo de Reynolds) "companheiros de rebanho".

  1. Cada boid deve ajustar seu rumo para evitar colisões e manter uma distância confortável de um raio de boid com seus vizinhos. (Esse é o aspecto "Separação" do algoritmo. O raio de boid pode ser ignorado, mas deve ser como um elástico, voltando ao lugar.)

  2. Cada boid também deve ajustar seu cabeçalho para ficar mais próximo do cabeçalho médio dos outros boids em sua vizinhança, desde que não interfira na primeira regra. (Este é o aspecto "Alinhamento" do algoritmo)

  3. Cada boid deve virar-se para a posição média de seus companheiros de rebanho, desde que isso não cause colisão ou interfira significativamente na segunda regra.

Em seu artigo sobre o assunto , ele explica o seguinte:

Para construir um rebanho simulado, começamos com um modelo boid que suporta vôo geométrico. Acrescentamos comportamentos que correspondem às forças opostas da prevenção de colisões e ao desejo de se juntar ao rebanho. Apresentados resumidamente como regras e em ordem decrescente de precedência, os comportamentos que levam ao flocagem simulada são:

  • Prevenção de Colisão: evite colisões com companheiros de rebanho próximos
  • Correspondência de velocidade: tente combinar a velocidade com companheiros de bando próximos
  • Centragem no rebanho: tente ficar perto de companheiros de rebanho próximos

Descrição mais detalhada do movimento:

  • A implementação padrão do algoritmo Boids geralmente faz um cálculo para cada uma das regras e as mescla.
  • Para a primeira regra, o boid percorre a lista de boids vizinhos em sua vizinhança e, se a distância entre ele e o vizinho for menor que um determinado valor, um vetor que empurra o boid para longe de seu vizinho é aplicado ao cabeçalho do boid.
  • Para a segunda regra, o boid calcula o cabeçalho médio de seus vizinhos e adiciona uma pequena porção (usaremos 1/10 neste desafio) da diferença entre o cabeçalho atual e o cabeçalho médio no cabeçalho atual.
  • Para a terceira e última regra, o boid calcula a média das posições de seus vizinhos e calcula um vetor que aponta para esse local. Esse vetor é multiplicado por um número ainda menor do que o usado na regra 2 (para esse desafio, 1/50 será usado) e aplicado ao cabeçalho.
  • O boid é então movido na direção de seu cabeçalho

Aqui está uma implementação útil de pseudocódigo do algoritmo Boids.

Exemplo de entrada e saída

Entrada:

5, 190 (5 boids, 190 quadros)

Resultado:

Animação de 190 quadros do Algoritmo Boids com 5 boids.

Critério de vitória

Isso é , então a menor solução em bytes vence.

iPhoenix
fonte
7
"É claro que há mais no algoritmo, então eu recomendo verificar a fonte". - tudo é necessário aqui ou não? Caso contrário, eu recomendaria consertar isso.
Jonathan Allan
1
Use a sandbox antes de postar desafios, conforme recomendado na página de solicitação .
flawr
@ JonathanAllan Sim, está tudo aqui, mas explicações mais detalhadas que podem fazer mais sentido para outros usuários estão disponíveis na fonte.
IPhoenix
11
Esse é um desafio interessante (acho os comportamentos de flocagem fascinantes), mas precisará ser bem especificado, especialmente para um código-golfe; caso contrário, a pressão para reduzir o comprimento do código causará todos os desvios possíveis do espírito do desafio. ser incentivado.
precisa saber é o seguinte

Respostas:

7

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

-1 byte de Jonathan Frech
+11 bytes para corresponder melhor à especificação
-2 bytes de Kevin Cruijssen
-12 bytes para alterar args para t ()
+29 bytes porque eu estava fazendo fantasmas incorretos; veja a versão comentada abaixo de
-40 bytes para usar para loops em vez de chamadas separadas para cada fantasma
-13 bytes para usar o frameRate padrão, 30

Bem, é um começo, para alguém que não pratica golfe em Java. :)

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

Como não conheço nenhuma maneira razoável de inserir dados no processamento, as duas primeiras variáveis ​​são as entradas (e eu não contei seus valores (5 bytes) na contagem de bytes). Se isso for um problema, posso tentar outras coisas.

Também não conheço uma boa maneira de permitir a tentativa on-line (o projeto Processing.js não pode lidar com esse estilo de código) sem hospedar coisas; e isso é algo que não estou ansioso para tentar. Deixe-me saber se há algo inteligente que eu possa fazer.

Código formatado, com comentários

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

Saída de amostra

n = 15, quadros = 400:

jibóias

Ou a mesma animação, mas mostrando a vizinhança de cada boid.

Phlarx
fonte
1
Não 2*PIé possível TAUsalvar um byte?
Jonathan Frech 02/02
@JonathanFrech Sim, pode; Eu originalmente tinha PI, PI e eu estava indo por esse caminho, mas fui desviado.
Phlarx 02/02
Meu programa (escrito em js e html) não exportou um gif, mas desenhou uma imagem e usei um programa de captura de tela e converti o vídeo exportado para um gif. Há uma coisa que eu notei, no entanto. Os boids ter um contorno azul, que não segue a especificação :)
iPhoenix
Apenas mais um lembrete amigável, esta resposta não segue as especificações, portanto não receberá a recompensa.
iPhoenix
1
Não sei Processando, mas acho que você pode jogar golfe nas seguintes coisas: ,i,para ,i=0,remover o i=0interior do loop for. (-1 byte); frameCount%f==0para frameCount%f<1(1 byte); &&para &na final if 2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6(-1 byte). Novamente, não tenho certeza se isso é possível, mas como o processamento parece bastante semelhante ao Java, acho que é. Além disso, você pode tentar criar um gif no screentogif.com .
Kevin Cruijssen
4

JavaScript (ES6) + HTML5, 1200 bytes

Aqui está minha solução atual usando a API do Canvas. O eval()retorna uma função de avaliar num cuja primeira entrada é a Boidpopulação, e o segundo é o número de quadros de animação. Você pode usar Infinitypara animação contínua.

São eval(...)1187 bytes e <canvas id=c>13 bytes, perfazendo um total de 1200. O CSS é desnecessário, mas, por conveniência, permite ver as bordas da 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

Conforme solicitado, outro snippet com uma entrada para a população 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
fonte
Os boids não parecem interagir quando eu executar o trecho
Jo Rei
@JoKing deve ser corrigido agora
Patrick Roberts
O problema ocorreu porque o minificador babel sombreava uma variável global em uma função com um nome de parâmetro, e a conversão implícita para um número não gerava um erro; portanto, a função falhou silenciosamente e nunca detectou vizinhos.
Patrick Roberts
Vou tentar fazer uma demonstração interativa amanhã à noite, mas fiquei sem energia hoje à noite.
Patrick Roberts
Apenas uma observação: onde se lê t.a+v+l/10+f/50, se você mudar para t.a+v/3+l/10+f/50, produz um comportamento um pouco mais interessante, mas o programa atual é menor e ainda precisa ser especificado.
Patrick Roberts