Szukam pomysłu na utworzenie managera kolizji w świecie 2D. Zależy mi na tym, aby był możliwie prosty w realizacji i wystarczająco wydajny, by nie udusić gry przy 200 obiektach (w tym 50 ruchomych).
Co byś mi wskazał?
0
0
odległość < suma promieni
0
200 obiektów bez kłopotu pójdzie naiwnym algorytmem kwadratowym. Jeżeli chcesz zoptymalizować, to mogę zaproponować techniki stosowane w modelowaniu chemicznym. Pierwszą metodą jest zrobienie listy sąsiedztwa, czyli raz na jakiś czas lecisz po wszystkim kwadratowo i tworzysz dla każdego obiektu listę obiektów z którymi może się zderzyć przez określony czas i po jego upływie znowu tę listę aktualizujesz. Inną metodą jest stworzenie np. kwadratowej siatki, gdzie w każdej komórce przechowywane są wskaźniki na obiekty, wtedy dla każdego obiektu sprawdzasz zderzenia z obiektami w tej i sąsiedniej komórce. Przy ruchu aktualizujesz stan odpowiednich komórek. Często stosuje się obydwie metody, tzn. tworzy się listę sąsiedztwa na podstawie siatki.
W przypadku 2d taka siatka pewnie jest wystarczająca, szczególnie że patrzysz tylko na zderzenia, nie masz innych oddziaływań między obiektami. Dodatkowo w 2d masz tylko 27% procent narzutu w ilości obiektów w porównaniu z listą sąsiedztwa, w 3d to już 91%.
0
Sporo algorytmów na to powstało, zależy jak dużej skalowalności potrzebujesz i jak wiele czasu na to chcesz przeznaczyć...
Regular Grid - najprostsza wersja - czyli dzielisz przestrzeń na pewną ilość kwadratowych/prostokątnych pól i dla każdego pola sprawdzasz kolizje między obiektami znajdującymi się w nim - wbrew pozorom bardzo szybkie w większości przypadków i prawdopodobnie Ci wystarczy.
Quadtree - trochę ciekawsza wersja Regular Grid, dzielisz rekurencyjnie przestrzeń na 4 części - http://en.wikipedia.org/wiki/Quadtree
Główna przewaga nad pierwszym to fakt że dużo lepiej sobie radzi z nierównomiernie rozmieszczonymi obiektami. Dalej proste.
KD-tree - w zasadzie bardziej zaawansowany algorytm, ale nie polecam Ci, ponieważ 1) jest relatywnie trudny do napisania i 2) nie jest przystosowany do takich operacji - dłużej się tworzy i dużo, dużo trudniej rebalansuje, co niweczy zalety które daje to że ma szybszy czas odpytywania: http://en.wikipedia.org/wiki/Kd-tree
Wszystkie powyższe opierają się na dzieleniu przestrzeni (Space Partitioning). Coś z innej beczki to na przykład http://en.wikipedia.org/wiki/Sweep_and_prune - polega na 'kreatywnym sortowaniu' obiektów wobec ich położenia na osi X i Y.
Z wiki jak zwykle trudno się uczyć - http://en.wikipedia.org/wiki/Sweep_and_prune - ja kiedyś pisałem w oparciu o http://www.gamedev.net/topic/473529-sweep-and-prune-sort-and-sweep/ .