Prírodou inšpirované algoritmy

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ť.