algorytm.org Data structures Sztuczna inteligencja Boidy  
Home AlgorithmsData structuresAlgorithmics turorialPractiseDesign patternsIT Law SitemapPortal historyContributors ForumToolsWrite an articleSearch 

Boidy
User Rating: / 2
PoorBest 
Written by Tomasz Lubiński   
Wednesday, 27 July 2005 18:31
There are no translations available.

Boidy stworzone przez Craiga Reynoldsa, wykazują bardzo realistyczne zachowanie się stada (ptaki, ławice ryb). Przypisał on każdemu boidowi następujące reguły postępowania:
  • każdy boid dopasowywuje swoją prędkość i kierunek lotu do sąsiednich boidów,
  • każdy boid stara się być w środku grupy sąsiednich boidów,
  • każdy boid zachowuje bezpieczną odległość od sąsiednich boidów,
  • każdy boid unika przeszkód,
  • każdy boid może opuścić stado, gdy ucieka przed drapieżnikiem lub potrzebuje pożywienie.
Już stosowanie tych prostych reguł spowodowało, że grupa boidów zachowywała się bardzo realistycznie - jak ich żywe odpowiedniki - potrafiąc rozdzielić się na dwie niezależne grupy przy napotkaniu przeszkody, ominąć ją i połączyć się ponownie za nią.
Zacznijmy jednak od początku. W przestrzeni dwuwymiarowej (a taką tutaj się zajmiemy), boid zdefiniowany jest przes 4 wartości: współrzędne x oraz y, a także prędkości dla każdego z wymiarów vx oraz vy. Uściślijmy teraz kto jest sąsiadem boida. Sąsiadami boida będziemy nazywać inne boidy (ewentualnie przeszkody, drapieżniki lub pożywienie), które znajdują się w "zakresie jego zmysłów". Czyli takie, które znajdują się w odpowiednio małej odległości (d) i jednocześnie w polu widzenia boida - który określony jest przez kąt (r). Tak więc sąsiedzi to będzie wszystko to co znajdzie się w poszarzonym polu.

Pole widzenia boidu

Jak sprawdzić czy dany element e o współrzędnych odpowiednio e.x i e.y, jest sąsiadem boida b odpowiednio o współrzędnych b.x i b.y oraz prędkości b.vx i b.vy. Najpierw sprawdzamy, czy element znajduje się w odpowiednio małej odległości, czyli czy sqrt((e.x-b.x)^2+(e.y-b.y)^2)<d, jeżeli nie to nie sprawdzamy już dalej bo element na pewno nie jest sąsiadem boida. Jeżeli tak, to sprawdzamy, czy jest on w kącie widzenia boida. Czyli obliczamy kąt pod którym porusza się boid k1=arctan(b.vy/b.vx), oraz kąt odcinka od boidu do elementu, k2=arctan((e.y-b.y)/(e.x-b.x)) (pamiętaj o zabezpieczeniu przed dzieleniem przez 0). Teraz badamy wartość bezwzględną różnicy kątów i sprawdzamy czy jest mniejsza od r, jeżeli tak to element jest sąsiadem boida, jeżeli nie to nie jest.

Zajmijmy się teraz pierwszym warunkiem - każdy boid dopasowywuje swoją prędkość i kierunek lotu do sąsiednich boidów.

Dostosowywanie kierunku ruchu boidu

Ten warunek jest najłatwiejszy do obliczenia. Należy obliczyć prędkość średnią wszystkich sąsiadów (oddzielnie dla składowej vx i składowej vy). A następnie należy zmodyfikować prędkość boida biorąc pod uwagę wagę z jaką będziemy modyfikować prędkość (np. 0.1), bieżącą prędkość, oraz obliczoną średnią, według wzoru: b.vx=b.vx+(waga*(srednia_vx-b.vx)), b.vy=b.vy+(waga*(srednia_vy-b.vy))

Druga reguła: każdy boid stara się być w środku grupy sąsiednich boidów.

Dostosowywanie odleglosci boidu

By zastosować tą regułę należy obliczyć, średnią odległość od sąsiednich boidów, a następnie, zmodyfikować prędkość boida względem każdego z sąsiadów. Następujący wzór jest wynikiem zastosowania twierdzenia o podobieństwie trójkątów, wykorzystujemy w nim położenie boida, którego prędkość modyfikujemy (b), położenie sąsiada (s), oraz wagę zmiany (np. 0.1): (odl - odległość od boida do sąsiada = sqrt((s.x-b.x)^2+(s.y-b.y)^2)) b.vx=b.vx+waga*(((s.x-b.x)*(odl-srednia_odleglosc))/odl), b.vy=b.vy+waga*(((s.y-s.y)*(odl-srednia_odleglosc))/odl);

Kolejna reguła: każdy boid zachowuje bezpieczną odległość od sąsiednich boidów.

Dostosowywanie odleglosci boidu

Jeżeli boid zbyt bardzo zbliży się do swego sąsiada powinien się od niego oddalić, modyfikując swoją prędkość. Tutaj również wykorzystujemy twierdzenie o podobieństwie trójkątów. Niech b będzie boidem, który zbyt bardzo zbliżył się do sąsiada s. Wówczas dla powyższej reguły stosujemy następujący wzór: b.vx=b.vx-waga*((((s.x-b.x)*(min))/odl)-(s.x-b.x)), b.vy=b.vy-waga*((((s.y-b.y)*(min))/odl)-(s.y-b.y)), gdzie odl jest odleglością pomiędzy boidem a sąsiadem, a min jest zadaną odległością minimalną, której nie powinien przekraczać boid.

Kolejne reguły o przeszkodach, drapieżnikach i pożywieniu można wprowadzić do symulacji boidów, uwzględniając regułę o bezpiecznej odległości.

Dodatkowo, w celu oddania większego realizmu, powinniśmy dodać, losowe zakłócenia ruchu boidów (np. w każdej iteracji dodając do składowych vx oraz vy niewielkiego zaburzenia). Powinniśmy też zauważyć, że każdy boid, może poruszać się z pewną maksymalną prędkością. Jeżeli prędkość boida przekroczy ją, to powinniśmy zmniejszyć jego prędkość np. o 25%.



.

Author Progam language Comment Download Rate
Tomasz Lubiński C/C++ Borland Builder 6
Implementation in C/C++
/ 0
 
Add your implementation for this algorithm
  • Login first
File:
Progam language:
Comment:
  To be able to add your implementation, login first



Last Updated on Thursday, 27 May 2010 19:20
 

Add comment







Danation
Donate us


RSS Channels
Articles
Implementations
Comments
Forum


Bookmarks








Poll
Czy znalazłeś na stronach www.algorytm.org to czego szukałeś?
 

www.algorytm.org (c) 2000-2010