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”.
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.)
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”)
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
Wejście:Wynik:5, 190 (5 boidów, 190 ramek)
Kryterium wygranej
To jest golf golfowy , więc wygrywa najmniejsze rozwiązanie w bajtach.
źródło
Odpowiedzi:
Przetwarzanie 3.3.6 (Java) ,
932931940928957917904 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. :)
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
Próbka wyjściowa
n = 15, ramki = 400:
Lub ta sama animacja, ale pokazująca sąsiedztwo każdego boid.
źródło
2*PI
nie możeszTAU
zapisać bajtu?,i,
do,i=0,
, a następnie usunąći=0
wewnątrz pętli for. (-1 bajt);frameCount%f==0
naframeCount%f<1
(1 bajt);&&
do&
końcowego if2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6
(-1 bajt). Ponownie, nie jestem pewien, czy są one możliwe, ale ponieważ przetwarzanie wydaje się dość podobne do Java, myślę, że tak. Możesz także spróbować utworzyć gif za pomocą screentogif.com .JavaScript (ES6) + HTML5, 1200 bajtów
Oto moje obecne rozwiązanie wykorzystujące Canvas API.
eval()
Zwraca curry funkcji którego pierwsze wejście jestBoid
populacji, a po drugie jest liczba klatek animacji. Możesz użyćInfinity
do 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.Edytować
Zgodnie z żądaniem, kolejny fragment kodu z danymi wejściowymi dla populacji Boid:
źródło
t.a+v+l/10+f/50
, jeśli zmienisz to nat.a+v/3+l/10+f/50
, spowoduje to nieco bardziej interesujące zachowanie, ale obecny program jest mniejszy i wciąż jest sprecyzowany.