Algorytm stada

Algorytm stada

Algorytm stada to technika, która umożliwia grupie obiektów, znanej jako boidy, naśladowanie realistycznego zbiorowego zachowania, przypominającego migrację ptaków, ławicę ryb lub rój pszczół. Opracował ją Craig Reynolds, który po raz pierwszy zaprezentował ten koncept w 1987 roku podczas konferencji SIGGRAPH. Zauważył, że stosując kilka stosunkowo prostych zasad, można uzyskać złożone i realistycznie wyglądające zachowania stadne.

Podstawowe zasady

W najprostszej wersji, zachowanie agenta w symulacji algorytmu jest kontrolowane przez trzy zasady:

• Rozdzielność – zapobiega lokalnym zbiorowiskom.
• Spójność – kieruje w stronę uśrednionego położenia lokalnej grupy.
• Wyrównywanie – prowadzi w kierunku uśrednionego celu lokalnej grupy.

Rozdzielność

Rozdzielność pozwala agentowi utrzymać określoną odległość od innych agentów w lokalnej grupie, co zapobiega tworzeniu się tłumów w jednym miejscu. Jednakże, stosowanie jedynie tej zasady sprawiłoby, że stado rozpraszałoby się w różne strony, uniemożliwiając ponowne skupienie. Dlatego konieczne jest wprowadzenie przeciwnej zasady, jaką jest spójność.

Spójność

Spójność umożliwia agentowi grupowanie się z innymi agentami w lokalnej grupie, co przeciwdziała „rozlatywaniu” się stad. Mimo to, sama spójność nie wystarcza. Stada mogłyby nie rozpraszać się (gdyby działała wyłącznie rozdzielność bez spójności) ani nie tworzyć jednego wielkiego zbiegowiska (sama spójność bez rozdzielności), jednak nadal mógłby występować niepożądany efekt chaotycznego poruszania się stada, spowodowany brakiem wspólnego kierunku ruchu. Dlatego konieczne jest dodanie zasady wyrównania.

Wyrównanie

Wyrównywanie daje agentowi możliwość dostosowania swojego ruchu (tj. zmiany kierunku lub prędkości) do innych agentów w jego lokalnej grupie. Dzięki temu unika się chaosu, gdzie agent mógłby próbować zbliżyć się do jednego obiektu, a następnie nagle się od niego oddalać – co prowadziłoby do sytuacji, w której stado kręciłoby się w kółko. Wprowadzenie zasady wyrównania sprawia, że agenci naśladują kierunek ruchu swoich sąsiadów, spełniając jednocześnie 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-source’owego projektu prowadzonego przez Craiga Reynoldsa, mającego na celu stworzenie implementacji algorytmu stada w języku C++. (ang.).

Przykładowy program ilustrujący działanie algorytmu stada. (ang.).