Algorytm stada

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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ść[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]