Algorytm stada

Algorytm stada – technika, która daje grupie obiektów (ang. boids) realistyczne zbiorowe zachowanie, podobne do stada ptaków, ławicy ryb albo roju pszczół. Został wymyślony przez Craiga Reynoldsa, który po raz pierwszy przedstawił go światu w roku 1987 na konferencji SIGGRAPH. Zauważył on, że łącząc kilka względnie prostych reguł można symulować bardzo skomplikowane, realistycznie wyglądające zachowania stadne.

W najbardziej podstawowej wersji, zachowanie agenta w świecie symulacji algorytmu kontrolują trzy zasady:

1. Rozdzielność – sterowanie zapobiegające lokalnym zbiorowiskom.
2. Spójność – sterowanie w kierunku uśrednionego położenia lokalnej grupy.
3. Wyrównywanie – sterowanie w kierunku uśrednionego celu lokalnej grupy.

Rozdzielność

Rozdzielność daje agentowi możliwość utrzymania pożądanej odległości od innych agentów z lokalnej grupy, a tym samym zapobiega tworzeniu tłumu w jednym miejscu. Z drugiej strony, zastosowanie samej rozdzielności spowodowałoby, że stado rozlatywałoby się na wszystkie strony, bez możliwości ponownego skupienia. Stąd wynika potrzeba wprowadzenie przeciwnej reguły spójności.

Spójność

Spójność daje agentowi możliwość grupowania się z agentami z lokalnej grupy, czyli zapobiega „rozlatywaniu” się stad. Jednak nawet wprowadzenie tej zasady nie jest wystarczające. Stada może i by się nie rozlatywały (gdyby działała sama rozdzielność bez spójności) i nie byłoby jednego wielkiego zbiegowiska (sama spójność bez rozdzielności), ale ciągle może występować bardzo niepożądany efekt kotłującego się na wszystkie strony stada, spowodowany brakiem wspólnego kierunku ruchu. Zaszła więc potrzeba dodania zasady wyrównania.

Wyrównanie

Wyrównywanie zapewnia agentowi możliwość dostosowania swojego ruchu (tzn. zmiany kierunku ruchu lub prędkości) do innych agentów z jego lokalnej grupy. Zapobiega to chaosowi typu „muszę być jak najbliżej X lecz jednocześnie gdy to mi się uda, muszę wykonać zwrot i się od niego oddalić” – w takiej sytuacji dostalibyśmy stado, które wręcz dosłownie kręciłoby się w kółko! Rozwiązaniem jest wprowadzenie wyrównywania, które nakaże agentom naśladować kierunek ruchu sąsiadów oraz jednocześnie spełniać wymagania spójności i rozdzielności.

Bibliografia

• Boidy – algorytm i struktura danych. [dostęp 2011-12-02].
• Oficjalna strona Craiga Reynoldsa dotycząca algorytmu. (ang.).

Linki zewnętrzne

• Strona open-sourcowego projektu kierowanego przez Craiga Reynoldsa, mającego na celu stworzenie implementacji algorytmu stada w języku C++. (ang.).
• Przykładowy program przedstawiający algorytm stada w akcji. (ang.).