Boids: jak 3 proste reguły tworzą zachowanie stadne

Craig Reynolds i narodziny Boids

W 1986 roku badacz grafiki komputerowej Craig Reynolds postawił sobie za cel animowanie stada ptaków do filmu. Zamiast ręcznie animować każdego ptaka albo pisać skrypt kontrolujący ich pozycje, zadał inne pytanie: jakich reguł faktycznie przestrzega każdy pojedynczy ptak?

Opublikował wynik w 1987 roku w pracy SIGGRAPH zatytułowanej „Flocks, Herds, and Schools: A Distributed Behavioral Model”. Symulowane agenty nazwano Boids — skrótem od „bird-oid objects” (obiekty ptakopodobne). Praca stała się jedną z najczęściej cytowanych w grafice komputerowej, a opisany w niej algorytm jest używany do dziś, blisko cztery dekady później.

Głębokie odkrycie było takie: nie potrzeba złożonych reguł koordynacji, by wytworzyć złożone, skoordynowane zachowanie. Trzy proste lokalne reguły wystarczają, by wygenerować realistycznie wyglądające zachowanie stadne z dowolnej liczby niezależnych agentów.

Trzy reguły

Każdy boid patrzy na swoich sąsiadów w promieniu percepcji i stosuje jednocześnie trzy siły sterujące:

Reguła 1: Separacja

Steruj z dala od zbyt bliskich sąsiadów.

Dla każdego boida znajdź wszystkich sąsiadów w promieniu „zbyt bliskim” (zwykle mniejszym niż promień percepcji). Oblicz wektor odpychania skierowany od każdego takiego sąsiada, ważony tym, jak blisko się znajduje — bliżsi sąsiedzi popychają mocniej. Zsumuj te wektory, by uzyskać siłę sterującą separacją.

Bez separacji boidy zapadają się w jeden punkt. Przy samej separacji boidy dryfują od siebie w nieskończoność. Reguła ta utrzymuje przestrzeń osobistą i zapobiega kompresji stada w nierealistycznie gęstą masę.

Reguła 2: Wyrównanie

Steruj w kierunku średniego kierunku pobliskich sąsiadów.

Każdy boid oblicza średni wektor prędkości wszystkich boidów w swoim promieniu percepcji. Następnie kieruje swoją własną prędkość w stronę tej średniej. Siła sterująca jest proporcjonalna do różnicy między obecną prędkością a docelową średnią.

Wyrównanie sprawia, że stado porusza się jako spójna grupa, a nie chmura osobników idących w losowych kierunkach. Bez niego boidy klastrują się razem, ale poruszają się chaotycznie.

Reguła 3: Kohezja

Steruj w kierunku średniej pozycji pobliskich sąsiadów.

Każdy boid oblicza środek masy swoich widocznych sąsiadów i delikatnie kieruje się w jego stronę. To reguła, która utrzymuje stado razem — bez kohezji separacja i wyrównanie produkują dryfujące małe grupy, które nigdy się nie łączą.

Implementacja reguł w kodzie

Podstawowa pętla aktualizacji dla pojedynczego boida wygląda tak:

dla każdego boida b:
    sąsiedzi = znajdź_sąsiadów(b, promień_percepcji)

    sep = siła_separacji(b, sąsiedzi)
    ali = siła_wyrównania(b, sąsiedzi)
    coh = siła_kohezji(b, sąsiedzi)

    b.prędkość += sep * w_sep
                + ali * w_ali
                + coh * w_coh

    b.prędkość = ogranicz(b.prędkość, max_prędkość)
    b.pozycja += b.prędkość * dt

Prostota jest uderzająca. Bez centralnego kontrolera, bez przekazywania wiadomości, bez stanu globalnego. Każdy boid zna tylko swoje najbliższe otoczenie. A mimo to uruchom to dla 500 boidów i otrzymasz zachowanie nie do odróżnienia od prawdziwej murmuracji.

Emergentna złożoność z lokalnych reguł

Filozoficzne znaczenie Boids sięga poza animację. Zademonstrowało ono ogólną zasadę, obecnie centralną dla nauki o złożoności: emergencję — pojawienie się wzorców na dużą skalę z interakcji na małą skalę, bez żadnej kontroli odgórnej.

Stado nie jest zaprogramowane. Stado jest zbiorowym zachowaniem osobników podążających za lokalnymi regułami. Nie znajdziesz „stada” w kodzie żadnego pojedynczego boida. Istnieje ono tylko na poziomie agregatu.

Ta sama zasada pojawia się w całej przyrodzie i nauce:

• Kolonie mrówek — pojedyncze mrówki podążające za gradientami feromonów zbiorowo rozwiązują problemy najkrótszej ścieżki.
• Przepływ ruchu drogowego — indywidualne decyzje kierowców tworzą emergentne zjawiska, takie jak fantomowe korki bez fizycznej przyczyny.
• Dynamika rynków — indywidualne decyzje handlowe produkują emergentne wzorce cenowe, bańki i krachy.
• Sieci neuronowe — pojedyncze neurony wystrzeliwujące produkują myśl, percepcję i świadomość.

Dostrajanie parametrów

Klasyczny model Boids ma kilka parametrów dostrajalnych, które dramatycznie zmieniają charakter stada:

• Promień percepcji — większy promień oznacza, że każdy boid widzi więcej sąsiadów. Formują się większe stada; zachowanie staje się bardziej skoordynowane, ale mniej reaktywne.
• Waga separacji — zwiększ ją, a osobniki rozpraszają się; stado staje się luźną chmurą. Zmniejsz ją, a boidy pakują się gęsto, przechodząc przez siebie nierealistycznie.
• Waga wyrównania — wysokie wyrównanie produkuje ciasne, zdyscyplinowane formacje. Niskie wyrównanie produkuje wirujące, organiczne klastry.
• Waga kohezji — klej, który trzyma stada razem. Zbyt wysoka, a stado zapada się w punkt; zbyt niska, a rozprasza się.
• Maksymalna prędkość — szybsze boidy wymagają więcej kroków obliczeniowych na jednostkę przestrzeni, by nie przegapić interakcji.
• Pole widzenia — prawdziwe ptaki nie widzą bezpośrednio za sobą. Dodanie martwego pola za każdym boidem czyni zachowanie bardziej realistycznym.

Zastosowania poza animacją

Pierwotnym celem Reynoldsa była animacja filmowa, a Boids były używane w niezliczonych produkcjach — roje nietoperzy w Batman Returns, stado gnu w Lion King i wielu innych. Ale zastosowania sięgają dziś daleko poza rozrywkę.

Robotyka i roje dronów stanowią być może najbardziej bezpośrednie zastosowanie. Systemy wielorobotowe w magazynach, wojskowe formacje UAV i floty dronów poszukiwawczo- ratowniczych — wszystkie czerpią z tych samych zasad rozproszonego stada. Każdy robot podejmuje niezależne decyzje na podstawie lokalnych danych sensorycznych; skoordynowane zachowanie wyłania się bez centralnej koordynacji.

Algorytmy optymalizacji inspirowane Boids obejmują optymalizację rojem cząstek (PSO), gdzie populacja rozwiązań-kandydatów porusza się przez przestrzeń poszukiwań, używając analogów separacji, wyrównania i kohezji. PSO konkuruje z algorytmami genetycznymi w problemach optymalizacji ciągłej i ma przewagę bardzo niewielkiej liczby hiperparametrów do dostrojenia.

Symulacja ruchu drogowego używa modeli wywodzących się z Boids dla dynamiki tłumu pieszych — ewakuacji, tłumów festiwalowych, wyjścia ze stadionów. Paradygmat „osobnik podążający za lokalnymi regułami” naturalnie wychwytuje sposób, w jaki ludzie poruszają się w tłumie.

AI w grach — od nawigacji jednostek w RTS przez zachowanie tłumów NPC po ławice ryb w grach eksploracji podwodnej — w dużej mierze opiera się na algorytmach stadnych wywodzących się z pracy Reynoldsa.

Rozszerzanie Boids

Oryginalny trzy-regułowy model to punkt wyjścia. Badacze i twórcy dodali wiele rozszerzeń:

• Unikanie przeszkód — dodaj siłę odpychania od ścian i przeszkód, ważoną bliskością. Boidy nawigują wokół złożonej geometrii.
• Dynamika drapieżnik-ofiara — dodaj zachowanie „ucieczki” wyzwalane, gdy drapieżnik wejdzie w promień percepcji. Produkuje to realistyczne wzorce rozproszenia i ponownego zebrania.
• Dążenie do celu — dodaj słabą siłę ciągnącą wszystkie boidy w stronę lokalizacji docelowej. Stado migruje, zachowując wewnętrzną strukturę.
• Agenty heterogeniczne — różne gatunki z różnymi regułami mogą współistnieć, produkując mieszane stada międzygatunkowe, jak te widziane w prawdziwych migracjach ptaków.