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

Przychodza mi do glowy dwa rozwiazania:
1) Jakas specjalna implementacja KD-Tree, tak aby uaktualnianie
obiektow dodanych wczesniej do KD-Tree mialo niski koszt.
2) Podzielic ekran na N kresek pionowych i M kresek poziomych.
Wyliczyc wsplrzedne skrzyzowan kresek. W kazdym przecieciu
wstawic liste. Potem kulke dodawac do listy w najblizszym
skrzyzowaniu. No i aby szukac kolizji, wystarczy przeszukac
kulki z kilku pobliskich skrzyzowan-list. Dodawanie do listy
to koszt O(1), usuwanie O(1), przegladanie kilku pobliskich
list to srednio... moze 2^D * X / N / M, gdzie X to ilosc kulek,
a D to ilosc wymiarow. Czyli dla 1000 kulek w 2D i podziale
ekranu na 100 kratek, mamy zlozonosc jednej "klatki fizyki"
1000 * 4 * 1000 / 100 = 40tys. Znacznie mniej niz X^2=1mln.
Pozdrawiam







--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/