Prírodou inšpirované algoritmy

Kŕdle, stáda, skupiny

Kŕdeľ – je skupina objektov ktoré sa vyznačujú všeobecnou polarizovanosťou (sú otočené rovnakým smerom) a skupinovým pohybom bez kolízií.

Boid – je simulovaný objekt v tvare vtáka (prejavuje sa podobným správaním) ale môže predstavovať v zásade hocičo.

Kŕdeľ pozostáva z diskrétnych objektov (boidov) pohybujúcich sa vizuálne zložitým spôsobom. Zdá sa, že existuje nejaký centrálny pohyb, ale dôkazy nasvedčujú, že tento pohyb je výsledkom individuálnych pohybov objektov.

Ako môžeme teda simulovať pohyby kŕdľov? Možné riešenie: naprogramovaním cesty každého individuálneho objektu, čo by bolo zdĺhavé, náchylné na chyby a skoro nemožné bez kolízií.

V tejto kapitole preberieme iný prístup. Zdá sa, že kŕdeľ je výsledkom interakcií medzi správaním sa rôznych boidov. Takže musíme simulovať správanie sa individuálneho boida. Toto si vyžaduje simuláciu percepčného mechanizmu a určitých vlastností prostredia, napr. aerodynamika. Ak je toto korektne vytvorené, potom nám na vytvorenie kŕdľa stačí vytvoriť viacero inštancií boidov.

Kŕdle sú zovšeobecnením časticových systémov, ktoré sa používajú na simuláciu dynamických fuzzy objektov. V kŕdli sú častice nahradené plným geometrickým tvarom s priestorovou orientáciou. Správanie sa boidovských častíc je komplexnejšie o to, že interagujú navzájom, zatiaľ čo jednoduché častice interagujú navzájom len málo.

Každý z boidov má vnútorný stav a množinu správaní. Tieto správania sú vyjadrené v pravidlách s klesajúcou dôležitosťou:

• Vyhýbanie sa kolízii
• Porovnávanie rýchlostí so susedmi
• Zhlukovanie stáda

Ak boid spraví porovnanie rýchlostí so susedmi, potom sa pravdepodobne vyhne kolízii. Takže statické vyhýbanie sa kolíziám má tendenciu zabezpečiť minimálnu vzdialenosť medzi boidmi a porovnanie rýchlostí ju má udržať.

Zhlukovanie stáda znamená pohyb do ťažiska najbližších susedov. Ak je boid blízko k centru kŕdľa, bude mať toto malý účinok a aj naopak. Keďže každý z boidov sa pozerá primárne na svojich susedov, potom sa kŕdeľ môže rozdeliť kvôli vyhnutiu sa prekážke, čo je využiteľné hlavne pri boidoch s obmedzeným poľom detekcie susedov. Každé z troch správaní dáva požadovaný vektor pohybu, ktoré sa následne navzájom zpriemerujú podľa priority. Je pravda, že môžu nastať určité potencionálne problémy v kritických situáciách.

Zaoberajme sa modelom, kde boidi berú do úvahy len niekoľko susedov. Toto korešponduje s obmedzeným vnímaním vonkajšieho sveta. Toto je presnejšie ako uvažovať s totálnym vnímaním. Ako sa ukazuje, správanie sa reálnych kŕdľov je závislé na obmedzenom vnímaní. Senzitivita boida voči jeho susedom je ovládaná dvomi možnými spôsobmi: sférická senzitivita so stredom, ktorý je samotný boid, alebo inverzná exponenciála vzdialenosti. Zlepšený model by mohol obsahovať vyššiu senzitivitu v priamom smere a/alebo proporcionálne závislú od rýchlosti boida. V súčasnom modeli sú boidi rušení tými, ktorí sú za nimi.

Ak by sme chceli aby sa celý kŕdeľ pohyboval po určitej trajektórii, stačí pridať v každom kroku požadovaný globálny vektor pohybu k aktuálnemu vektoru všetkých boidov, alebo pridať ho boidom vpredu, ktorí budú nasledovaní ostatnými.

Boidi sa v prázdnom prostredí rýchlo ustália do stabilného stavu, teda všetci s malou vzdialenosťou a veľmi podobnou rýchlosťou. Pridaním prekážok do prostredia robí pohyb oveľa zložitejším. Bol použitý model uhýbania sa pre vyhnutie sa prekážke. V tomto modeli je boid ovplyvňovaný len objektmi ktoré sú priamo pred ním. Hneď ako detekuje objekt, nájde okraj jeho siluety najbližší k miestu prieniku jeho trajektórie s objektom a vyhne sa mu o šírku svojho tela. Prekážky brané v úvahu pri simuláciách môžu byť veľmi komplexné geometrické objekty, stromy, mosty atď. Prekážky nemusia byť ani statické, môžu sa pohybovať. Môžu to byť aj predátori, kde je možné zvýšiť prioritu vyhýbania sa.

Zdroj:
http://www.siggraph.org/education/materials/HyperGraph/animation/art_life/flocks.htm