Dnia 08-12-2011 o 20:00:49 fir <f...@w...gazeta.pl> napisał(a):

> (i znowu sie zle poczulem, [w zwiazku z horror nudzaca
> glupota ludzka], niewazne)
>
> nigdy poki co nie robilem optymalizacji detekcji kolizji,
> tylko troche sie zastanawialem ->
>
> najprostsza wersja detekcji kolizji jest zlozonsci
> n-kwadrat, ale defakto detekcja kolizji jest/moze byc
> zlozonosci liniowej n-do-pierwszej,
> trzeba tylko dane obiekty przestrzenne 'rejestrowac'
> w jakiejs 'spacjalnej' strukturze (nazywam tu troche
> dla zartu 'spacjalą kolizyjną', nie jest to zupelnie
> od rzeczy nazywac strukture danych o charakterze
> przestrzennym oddzielnym slowem np 'spacjala' bo to
> doprecyzowuje i pomaga)
>
>
> wezmy np wspominane kulki 2d
> [wczesniej zle napisalem ze maja srednice 5 pix, maja
> promien 5 pix a srednice 10 pix, (i kolizja nastepuje tez
> przy dist <= 10 pix],
>
> w tym wypadku tak naprawde nawet mozna by uzyc samego
> rambufora z obrazem okna (jesli pixel == czarny nic nie ma,
> jesli kolor to kolizja) ale jest to może trcohe brzydkie
> i pozatym nie podaje informacji o indeksie tego z czym sie
> zderzamy (czyli przyspieszenie jest polowiczne)
>
> nalezaloby utworzyc odzielną 'spacjalę' i pytanie brzmi
> 'dokladnie jak?'
>
> o ile pileczka ma 10 pix srednicy a okno powiedzmy rozmiar
> 500x400 (lub tez i jakis inny), dana komorka w takiej spacjali
> powinna miec rozmiar gdzies tak pewnie 30pix x 30pix (ale
> dokladnie ile?) Sa tez dwie opcje czy te komorki powinny
> przylegac ale sie nie nakladac (wtedy niezrecznie trzebaby
> czasem sprawdzac jedna komorke a czasem cztery) czy tez
> powinny sie nakladac w taki sposob by zawsze mozna sprawdzac
> tylko jedna komorke, za to przy ruchu przedmiotu trzebaby
> uzupelniec informacja kilka komorek na raz
>
> a moze jednak komorki powinna miec dokladnie 10x10 pix
> i nie nakladac sie, to sie wydaje moze najprostsze?
>
> jakies uwagi ntt?

nie całkiem rozumiem Twój pomysł, ale chyba mi się nie podoba.

mój całkiem nieoptymalny kod analityczny (100 kulek, i czasem nie wyrabia)
wyglądał jakoś tak:
//szkic w notacji C#
delegate void Cont();
Pair<float,Cont>? findCollision(Ball a,Ball b);
//jeśli kulki się nie zderzają, to null,
//zwraca parę -- moment tego zderzenia, i procedurę modyfikująca stan
biorących udział w zderzeniu kulek, jeśli to zderzenie zajdzie
//jeśli mamy kulki a,b i c, to findCollision wołamy dla (a,b), (a,c) i
(b,c), możemy dostać od 0 do 3 procedur, ale wykonujemy najwyżej jedną --
dla pierwszego zderzenia,
//albowiem potem kulki lecą inna trasa, i pozostałe zderzenia są nieważne
(bo zakładają, że kulki lecą po niezmodyfikowanej trasie)
Pair<float,Cont>? zapCol=null;//najblizsza kolizja do wykonania,

w funkcji Update robilem cos takiego

T=now();
while(zapCol==null || zapCol.t<=T){
if(zapCol!=null){
zapCol.proc();
}
zapCol=null;//
Pair<float,Cont>? f=null;//właśnie znaleziona kolizja
for(int i=0;i<balls.length;i++){
f=null;
b=balls[i];
//tu byly testy kolizji ze scianami, pomijam dla czytelnosci
for(int j=0;j<i;j++){
a=balls[j];
f=findCollision(a,b);
if(zapCol==null || (f!=null && f.t<zapCol.t)){//jeśli znaleziona
kolizja jest bliższa w czasie niż zapamiętana
zapCol=f;//to będzie użyta
}
}
}
}

ale to robi O(n^2) dla każdej kolizji, można by znalezione kolizje (f)
zapamiętywać gdzieś, i invalidować tylko te, w których uczestniczyły kulki
dla wykonywanej (proc()) kolizji.

kod iteracyjny też się się da optymalizować, i ktoś się tym pewnie
zajmował, ale ja wolałem się pobawić analitycznym



--
Jordan Szubert