Wprowadzenie

Algorytm stada Algorytm jest stosunkowo prosta demonstracja zachowania powstającej w grupie. Ma trzy główne zasady, opisane przez jego twórcę, Craiga Reynoldsa:

Podstawowy model flokowania składa się z trzech prostych zachowań sterujących, które opisują, w jaki sposób poszczególne manewry na boisku oparte są na pozycjach i prędkościach jego pobliskich towarzyszy:

• Separacja : steruj, aby uniknąć zatłoczenia lokalnych stad.
• Wyrównanie : kieruj się w stronę średniego kursu lokalnych towarzyszy stad.
• Spójność : kieruj się, aby zbliżyć się do średniej pozycji lokalnych stad.

Każdy boid ma bezpośredni dostęp do opisu geometrycznego całej sceny, ale uciekanie wymaga, aby reagował tylko na towarzyszy w pewnym niewielkim sąsiedztwie wokół siebie. Sąsiedztwo charakteryzuje odległość (mierzona od środka Boida) i kąt mierzony od kierunku lotu Boida. Towarzysze z tej okolicy są ignorowani. Sąsiedztwo można uznać za model ograniczonej percepcji (jak w przypadku ryb w mętnej wodzie), ale prawdopodobnie bardziej poprawne jest myślenie o nim jako o definiowaniu regionu, w którym stada wpływają na sterowanie kablem.

Nie jestem doskonały, kiedy wyjaśniam różne rzeczy, więc bardzo polecam sprawdzenie źródła . Na swojej stronie ma też bardzo ciekawe zdjęcia.

Wyzwanie

Biorąc pod uwagę liczbę boidów (elementy symulowane) i liczbę ramek, wygeneruj animację symulacji.

• Boidy powinny być renderowane jako czerwone kółko, z linią wewnątrz koła wskazującą jego kurs, czyli w kierunku, w którym wskazuje boid:

• Kąt każdej boid (zgodnie z opisem Reynoldsa) powinien wynosić pełne 300 stopni. (nie 360)
• Początkowy nagłówek i pozycja każdego boid powinny być jednakowo losowe (ale zaszczepione, aby wynik był nadal określony), a także pozycja.
• Jeśli promień boid wynosi 1, promień sąsiedztwa powinien wynosić 3.
• Liczba boidów wyniesie od 2 do 20.
• Liczba ramek będzie wynosić od 1-5000
• Animacja powinna być odtwarzana z minimum 10 milisekundami na klatkę i maksymalnie 1 sekundą razy więcej niż boidów. (2 boids = maksymalnie 2 sekundy na klatkę, 3 boids = 3 sekundy na maksymalnie klatkę itp.)
• Animacja wyjściowa powinna wynosić co najmniej 5 boid-promienie na 5 boid-promienie, razy połowę liczby boidów. Tak więc minimalny rozmiar dla 2 boidów wynosiłby 10 promieni boidów na 10 promieni boidów, minimalny rozmiar 3 boidów wynosiłby 15 promieni boid na 15 promienników boid i tak dalej.
• Promień każdej boid musi wynosić minimum 5 pikseli i maksymalnie 50 pikseli.
• Prędkość każdego boida musi być ograniczona, aby nie poruszał się więcej niż o 1/5 promienia w jednej ramce.
• Dane wyjściowe muszą być określone, aby te same dane wejściowe wytworzyły to samo wyjście, jeśli zostaną uruchomione wiele razy.
• Jeśli boid osiągnie granicę, powinien zawinąć się na drugą stronę. Podobnie sąsiedztwo wokół każdego boid powinno również owijać się wokół granic.

Reguły dla algorytmu

W tym przypadku każdy boid ma sektor rozciągający się na 300 stopni, wyśrodkowany na jego główce. Wszelkie inne boidy w tym „sąsiedztwie” są uważane za „sąsiadów” lub (używając terminu Reynoldsa) „flockmates”.

1. Każdy boid powinien dostosować swój kurs, aby uniknąć kolizji i utrzymywać wygodną odległość jednego promienia boid od swoich sąsiadów. (Jest to aspekt algorytmu „separacja”. Jeden promień boid może być ominięty, ale powinien być jak gumka, która wskakuje na swoje miejsce.)

2. Każdy boid powinien dodatkowo dostosować swój kurs, aby był bliżej średniego kursu innych boidów w swoim sąsiedztwie, o ile nie koliduje z pierwszą regułą. (Jest to aspekt algorytmu „Wyrównanie”)

3. Każdy boid powinien obrócić się w kierunku średniej pozycji swoich stad, o ile nie spowoduje to kolizji ani nie zakłóci znacząco drugiej reguły.

W swoim artykule na ten temat wyjaśnia to w następujący sposób:

Aby zbudować symulowane stado, zaczynamy od modelu boid, który obsługuje lot geometryczny. Dodajemy zachowania, które odpowiadają przeciwstawnym siłom unikania kolizji i chęci dołączenia do stada. Krótko określane jako reguły, w kolejności malejącego pierwszeństwa, zachowania prowadzące do symulowanego uciekania są następujące:

• Unikanie kolizji: unikaj kolizji z pobliskimi towarzyszami stad
• Dopasowywanie prędkości: próba dopasowania prędkości do pobliskich towarzyszy stad
• Centrowanie stada: próba pozostania blisko pobliskich towarzyszy

Bardziej szczegółowy opis ruchu:

• Standardowa implementacja algorytmu Boids zwykle wykonuje obliczenia dla każdej reguły i łączy je ze sobą.
• Zgodnie z pierwszą regułą, boid przechodzi przez listę sąsiednich boidów w swoim sąsiedztwie, a jeśli odległość między sobą a sąsiadem jest mniejsza niż pewna wartość, wektor odsuwający boid od sąsiada jest stosowany do jego pozycji.
• W przypadku drugiej reguły, boid oblicza średni kurs swoich sąsiadów i dodaje niewielką część (użyjemy 1/10 w tym wyzwaniu) różnicy między jego bieżącym i średnim kursem do bieżącego kursu.
• Dla trzeciej i ostatniej reguły, boid uśrednia pozycje swoich sąsiadów, oblicza wektor wskazujący tę lokalizację. Ten wektor jest mnożony przez jeszcze mniejszą liczbę niż ta, która została użyta dla reguły 2 (w tym wyzwaniu zostanie użyta 1/50) i zastosowana do nagłówka.
• Boid jest następnie przesuwany w kierunku jego kursu

Oto przydatna implementacja pseudokodu algorytmu Boids.

Przykład wejścia i wyjścia

5, 190 (5 boidów, 190 ramek)

Kryterium wygranej

To jest golf golfowy , więc wygrywa najmniejsze rozwiązanie w bajtach.

Przetwarzanie 3.3.6 (Java) ,932 931 940 928 957 917 904 bajty

^{-1 bajt Jonathana Frecha
+11 bajtów, aby lepiej pasować do specyfikacji
-2 bajty Kevina Cruijssena
-12 bajtów na zamianę argumentów na t ()
+29 bajtów, ponieważ źle robiłem ghosting, zobacz komentarz poniżej wersji
-40 bajtów na zapętla zamiast osobnych wywołań dla każdego widma
-13 bajtów w celu użycia domyślnej frameRate, 30}

Cóż, to początek dla kogoś, kto nie gra w golfa 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));}}

Nie znam żadnego rozsądnego sposobu wprowadzania danych wejściowych w Przetwarzaniu, więc pierwsze dwie zmienne są danymi wejściowymi (i nie policzyłem ich wartości (5 bajtów) w kierunku liczby bajtów). Jeśli to jest problem, mogę spróbować innych rzeczy.

Nie znam też dobrego sposobu na przetestowanie go online (projekt Processing.js nie radzi sobie z tym stylem kodu) bez samodzielnego hostowania rzeczy; i nie chcę tego próbować. Daj mi znać, jeśli mogę coś mądrego zrobić.

Sformatowany kod z komentarzami

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

Próbka wyjściowa

n = 15, ramki = 400:

Lub ta sama animacja, ale pokazująca sąsiedztwo każdego boid.

JavaScript (ES6) + HTML5, 1200 bajtów

Oto moje obecne rozwiązanie wykorzystujące Canvas API. eval()Zwraca curry funkcji którego pierwsze wejście jest Boidpopulacji, a po drugie jest liczba klatek animacji. Możesz użyć Infinitydo ciągłej animacji.

Ma eval(...)1187 bajtów i <canvas id=c>13 bajtów, co daje w sumie 1200. CSS jest niepotrzebny, ale dla wygody pozwala zobaczyć krawędzie płótna.

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>

Edytować

Zgodnie z żądaniem, kolejny fragment kodu z danymi wejściowymi dla populacji 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>