M.M. <m...@N...gazeta.pl> napisał(a):

> 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
>
>
no pisalem wlasnie o tym - pytanie tylko o najbardziej korzystna
postac tej 'spacjali' dokladnie

chwilowo najprostsza wydaje mi sie chyba wersja z komorkami
10x10 pixeli, wtedy w takiej komorce moze byc najwiecej 4 kulki

kazda kulke przy ruchu wpisywaloby sie do najwiecej 4rech
komorek, podobnie czytaloby sie okolo 4ry komorki, mozna
zrobic na tablicy np

int spacjalaKolizyjna[40][50][4];

raczej proste i raczej szybkie, dzieki temu ze przypadek prosty










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