algorytm.org

Boidy



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Boidy
Ocena użytkowników:***** / 171
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 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 \left( \frac{b.vy}{b.vx}\right)
oraz kąt odcinka od boidu do elementu,
k2=\arctan \left( \frac{e.y-b.y}{e.x-b.x}\right)
(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*(vx_{srednia}-b.vx))\\ b.vy=b.vy+(waga*(vy_{srednia}-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 = \sqrt{(s.x-b.x)^2+(s.y-b.y)^2)} \\\\ b.vx=b.vx+waga*\frac{(s.x-b.x)*(odl-odleglosc_{srednia})}{odl} \\\\ b.vy=b.vy+waga*\frac{(s.y-s.y)*(odl-odleglosc_{srednia})}{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:
odl = \sqrt{(s.x-b.x)^2+(s.y-b.y)^2)} \\\\ b.vx=b.vx-waga*\left(\frac{(s.x-b.x)*min}{odl}-(s.x-b.x)\right) \\\\ b.vy=b.vy-waga*\left(\frac{(s.y-b.y)*min}{odl}-(s.y-b.y)\right)
gdzie 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%.

Przykład 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

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 6
Tomasz LubińskiJavaScriptFirefox 3.0+, Safari 3.0+, Chrome 5.0+, Opera 9.5+, IE 6.0+
.js
.js
***** / 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: 15 sierpnia 2012 15:06
Komentarze
photo
+1 # Keluj 2014-01-19 20:33
jak obliczyć średnią prędkość i średnią odległość?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Reven 2014-03-16 18:11
Suma prędkości wszystkich sąsiadów przez ilość sąsiadów.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Sylwek 2017-09-23 14:10
Imponujące. Zastanawiam się jak zmusić boidy, żeby wracały do ustalonego szyku przy braku przeszkód, jak np. tu:

https://youtu.be/AiCFtmdrvHM?t=69

Wydaje się, że potrzebna jest centralnie przechowywana informacja o pożądanym szyku.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz