Kolizje 2d wielu obiektow -optymalizacja

No więc mam około miliona kół(ale to może być cokolwiek- kolizje kół najłatwiej było mi zrobić) na 2 wymiarowej przestrzeni. I teraz mam taki problem że w każdej klatce muszę sprawdzić wszystkie koła ze wszystkimi - czy nie zachodzi jakaś kolizja.

Wymyśliłem taki sposób optymalizacji że sortuje listę kół w osi y jeśli jakieś koło się poruszy w osi y sprawdzam czy nastąpiła kolizja z kołem pozycje niżej/wyżej. Potem sprawdzam czy nie nastąpiła kolizja w osi x. Aby to jeszcze przyspieszyć myślę o podziale przestrzeni na kwadraty.

Jak to można jeszcze przyśpieszyć ?

Mozesz jeszcze podzielic przestrzen wokol danego kola na 9 obszarow:

   |   |   
-----------
   | O |   
-----------
   |   |

I w zaleznosci od relacji wspolrzednych x i y (+ ew. wymiary kol) innych kol wzlgledem linii dzielacych przestrzen wokol badanego kola szybko eliminujesz te, z ktorymi sie nie styka (rogowe). Poza tym... jesli kazdy z kazdym to zadbaj o to, by nie badac raz A z B, a potem B z A ;)

[losowa nazwa] napisał:

Poza tym... jesli kazdy z kazdym to zadbaj o to, by nie badac raz A z B, a potem B z A ;)
Moze po prostu tablica obiektow/wskaznikow na obiekty i cos w tym stylu:

for(int i=0;i<iloscObiektow-1; i++) 
for(int j=i+1; j<iloscObiektow; j++) obiekt[i].sprawdzKolizjeZ(obiekt[j]);

Prosty sposob, na to zeby 2 razy nie sprawdzac tego samego.

Oczywiscie oprocz tego wspomniane wyzej optymalizacje.

problem polega na tym że jedne koła są bardzo duże drugie malutkie. Jeśli dostosuje kwadraty do małych/dużych to może się okazać że więcej schodzi mi sprawdzanie pustych kwadratów niż sprawdzanie kolizji.

Moze na etapie przypisywania kol do odpowiedniego kwadratu traktuj kola jak kwadraty(zamiast kola o promieniu r i srodku w punkcie S, masz kwadrat o boku 2r i srodku w tym samym punkcie co srodek kola) ? Powinno to troche przyspieszyc obliczenia, a to tylko "obliczenia pomocnicze", wiec nie musze byc super dokladne.

@cyriel - słyszałem o tym (albo czymś podobnym) i nawet implementowałem - rzeczywiście przyśpiesza obliczania, a polega na tym że dla dużej ilości nieregularnych obiektów (jak kół) nie liczymy od razu za pomocą kosztownych operacji tylko sprawdzamy czy "jest szansa" na zderzenie. Nie umiem tłumaczyć więc machnąłem obrazek w paincie:

Ok czyli zamiast koła mamy kwadrat o "promieniu" R.

Kwadraty są posortowane w dwóch listach , lista Osi X, osi Y.

Obliczenia wygladaja tak :

KoloA_X - KoloB_X < R_AB (suma promieni policzona wcześniej dla każdej kombinacji bez powtórzeń i trzymana w pamięci)
|| KoloA_Y - KoloB_Y < R_AB 

Algorytm tak :

• przemieszczam kwadrat na nowe miesjce
• szukam dla kwadratu nowego zbiornika(badz kilku jesli jest wychodzi poza pole) (taka jak by szachownica w każdym polu lista osi x i osi y)
• usuwam ze starego pola
• wkładam go do sortowanej listy oxi x i osi y na właściwe miejsce
• zaznaczam kolizje kwadratow na osi x
• zaznaczam kolizje kwadratow na osi y
• sprawdzam czy nastąpiła kolizja (czy x_kolizja && y_kolizja == true)

tak, czy jakoś to przyśpieszyć się da ?