Obsah
Úvod
Modelovanie pohybu kŕdľa
Princípy
Zložitosť
Applet
Applety
Prehľad appletov na webe
Literatúra a linky
O tejto kapitole



Ostatné kapitoly
Výpočtové schopnosti celulárnych automatov
Celulárne automaty - úvod
Samoreprodukujúce sa celulárne automaty
Kryštálove výpocty
HAL
Boidi
Floyi
Aplikácie celulárnych automatov
CAPOW
LIFE - Hra života
Fredkinov biliardový automat


Hlavne menu
 O nás
 Tutoriály
 Archiv


Zložitosť

Implementácia základného algoritmu má kvadratickú časovú zložitosť a je silne závislá na veľkosti populácie. Funkcia reálneho boidu však nie je časovo závislá. Preto aj navigácia by mala byť nezávislá na veľkosti populácie. Výsledný čas je otázkou toho, ako implementujeme boidov na jednom sekvenčnom počítači. Ak použijeme distribuovaný model, tak sa nám úloha rozdelí na x podčastí. Riešením je použitie samostatného procesora na každého boida. Pre prípad naivného algoritmu dostaneme lineárnu časovú závislosť. Ale čas výpočtu je závislý na veľkosti kŕdľa. Preto sa používajú tri prístupy:
  • Dynamické rozdelenie kŕdľa - Boidi sa rozdelia do mriežky zásobníkov podľa ich polohy v priestore . Boid navigujúci sa vo vnútri kŕdľa dostane rýchly prístup k spoluletcom, ktorí sú fyzicky blízko k vyšetrovanému bodu podľa zásobníka.
  • Detekcia kolízie - iný prístup s kvadratickou časovou zložitosťou.
  • Inkrementálna detekcia kolízie resp. testovanie x najbližších. Vychádza sa zo stavu tesne predchádzajúceho, sleduje sa, či nastala kolízia s iným objektom alebo nie, čo je omnoho rýchlejšie, ak sú zmeny polohy boidov malé. Tým sa dosiahne konštantná časová závislosť.

Hore
Kontakty:     webmaster     admin     chief
Valid HTML 4.01! Valid CSS!