StartAlgorytmySztuczna inteligencjaBoidy
Baza Wiedzy
Wersja offline serwisu przeznaczona na urządzenia z systemem Android.

Darowizny
darowiznaWspomóż rozwój serwisu


Nagłówki RSS
Kanał artykuły
Kanał implementacje
Kanał komentarze
Kanał forum


Bookmarki









Sonda
Implementacji w jakim języku programowania poszukujesz?
 
Boidy
Ocena użytkowników:++++- / 8
SłabyŚwietny 
Wpisany przez Tomasz Lubiński
środa, 27 lipca 2005 18:31
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%.

Prezentacja w JavaScript:
Promień sąsiedztwa: pikseli
Kąt obserwacji: stopni
Odleglosc minimalna: pikseli
Waga prędkości sąsiadów %
Waga odległości sąsiadów %
Waga odległości minimalnej %
Waga zakłóceń %
Prędkość maksymalna pikseli/krok



Autor Język programowania Komentarz Otwórz Pobierz Ocena
Tomasz Lubiński C/C++ Borland Builder 6
Implementacja w C/C++
Implementacja w C/C++
++++- / 4
Tomasz Lubiński Java Script Firefox 3.0+, Safari 3.0+, Chrome 5.0+, Opera 9.5+, IE 6.0+
Implementacja w Java Script
Implementacja w Java Script
++++- / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie



Poprawiony: sobota, 11 czerwca 2011 18:57

Dodaj komentarz

Kod antysapmowy
Odśwież