W dniu 06.05.2011 09:11, kenobi pisze:
> int_pair* collision = dish_up_collisions(Spheric_entity* object );
Mogę dać funkcję wykrywającą wszystkie pary kolizyjne, ale o sygnaturze:
std::vector<std::pair<boost::shared_ptr,boost::share
d_ptr> >
detect_collisions(std::vector<boost::shared_ptr>);

--
Pozdrawiam
Michoo

do góry

> W dniu 06.05.2011 09:11, kenobi pisze:

> > int_pair* collision = dish_up_collisions(Spheric_entity* object );

> Mogę dać funkcję wykrywającą wszystkie pary kolizyjne, ale o sygnaturze:
> std::vector<std::pair<boost::shared_ptr,boost::share
d_ptr> >
> detect_collisions(std::vector<boost::shared_ptr>);


konkurs polega na tym zeby zapodac kod ktory bedzie dzialal
szybciej niz inne podane (np zeby uciaglal jak najwieksza
tablice wejsciowa w 30 milisekund)

mozna dac squerowego loopa

int_pair* dish_up_collisions(Spheric_entity* object )
{

int t=0;

for(int j=0; j<objects_length; j++)
for(int i=0; i<objects_length; i++)
{
if( object_distance(i,j) < object[i].radius + object[j].radius )
{
collision[t].i = i;
collision[t].j = j;
t++;
}

}

}

ale bedzie tu mulic jak cholera

jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy - wstepny
podzial na sektory, oznaczanie w kazdej klatce bitflagami tych
objektow ktore sie poruszyly i sprawdzanie tylko ich

za jakis czas bede potrzebowac takiej funkcyjki - choc tez jak mysle
takie ogolne rozwiazania sa z definicji wolne i tak naprawde moze
nalezy uzyc szczegolowych

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

W dniu 2011-05-07 07:40, kenobi pisze:

>
> jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy - wstepny
> podzial na sektory, oznaczanie w kazdej klatce bitflagami tych
> objektow ktore sie poruszyly i sprawdzanie tylko ich


Stawiam dolary przeciw orzechom, ze sztuczki nie dadza ulamka tego, co
którys z uznanych algorytmów na bazie matematyki, ale to trzeba wiecej
czytac niz kodowac sztuczki.

do góry

On Sat, 07 May 2011 11:26:05 +0200 Jacek Czerwinski <...@...z.pl> wrote:

> W dniu 2011-05-07 07:40, kenobi pisze:
> > jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy -
> > wstepny podzial na sektory, oznaczanie w kazdej klatce bitflagami
> > tych objektow ktore sie poruszyly i sprawdzanie tylko ich
>
> Stawiam dolary przeciw orzechom, ze sztuczki nie dadza ulamka tego,
> co którys z uznanych algorytmów na bazie matematyki, ale to trzeba
> wiecej czytac niz kodowac sztuczki.

Akurat "podział na sektory" jest dobrą, algorytmiczną metodą. :)

w,

do góry

W dniu 07.05.2011 07:40, kenobi pisze:
> ale bedzie tu mulic jak cholera
Bo to jest algorytm do niczego.


> jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy - wstepny
> podzial na sektory, oznaczanie w kazdej klatce bitflagami tych
> objektow ktore sie poruszyly i sprawdzanie tylko ich
Sortujesz wektor obiektów po x,y,z. Przeglądasz liniowo ten wektor
sprawdzając czy dwie współrzędne środków różnią się o mniej niż promień
(czyli robisz test na kolizję 2 sześcianów. Jeżeli tak to robisz
dokładny test liczeniem pierwiastków. Całość masz w
O(n*(log(n)+1))=O(n*logN).

W momencie gdy całość trzymasz już posortowane w ten sposób w jakimś
drzewie koszt jeszcze może spaść bo zmieniasz układ (w O(log(n)) tylko
gdy doszło do zmiany w porządku sortowania danego obiektu.

Jak masz dane w octtree to też można optymalizować.

--
Pozdrawiam
Michoo

do góry

Errata:

> O(n*(log(n)+1))=O(n*logN).
Przy założeniu, że kolizje są _rzadkie_ w stosunku do liczby obiektów.
Bo w sytuacji gdy każdy obiekt koliduje z każdym nie da się przeskoczyć
tego, że to generuje (n*(n-1)/2) par.

--
Pozdrawiam
Michoo

do góry

W dniu 2011-05-07 11:44, Wojciech Muła pisze:
> On Sat, 07 May 2011 11:26:05 +0200 Jacek Czerwinski<...@...z.pl> wrote:
>
>> W dniu 2011-05-07 07:40, kenobi pisze:
>>> jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy -
>>> wstepny podzial na sektory, oznaczanie w kazdej klatce bitflagami
>>> tych objektow ktore sie poruszyly i sprawdzanie tylko ich
>>
>> Stawiam dolary przeciw orzechom, ze sztuczki nie dadza ulamka tego,
>> co którys z uznanych algorytmów na bazie matematyki, ale to trzeba
>> wiecej czytac niz kodowac sztuczki.
>
> Akurat "podział na sektory" jest dobrą, algorytmiczną metodą. :)
>
ok, zwracam honor ... przyznam, odpuscilem sobie nieco psychoanalityczne
szczególy.

do góry

> W dniu 07.05.2011 07:40, kenobi pisze:

> > ale bedzie tu mulic jak cholera
> Bo to jest algorytm do niczego.
>
>
> > jakie sztuczki optymalizacyjne? mi przychodza dwie do glowy - wstepny
> > podzial na sektory, oznaczanie w kazdej klatce bitflagami tych
> > objektow ktore sie poruszyly i sprawdzanie tylko ich
> Sortujesz wektor obiektów po x,y,z. Przeglądasz liniowo ten wektor
> sprawdzając czy dwie współrzędne środków różnią się o mniej niż promień
> (czyli robisz test na kolizję 2 sześcianów. Jeżeli tak to robisz
> dokładny test liczeniem pierwiastków. Całość masz w
> O(n*(log(n)+1))=O(n*logN).
>
> W momencie gdy całość trzymasz już posortowane w ten sposób w jakimś
> drzewie koszt jeszcze może spaść bo zmieniasz układ (w O(log(n)) tylko
> gdy doszło do zmiany w porządku sortowania danego obiektu.
>
> Jak masz dane w octtree to też można optymalizować.
>
no wreszcie jakas konstruktywna wypowiedz

- no sa rzadkie - to dotyczy sceny w kosmosie (mw 50 kilkometrow
na 50 kilometrow na 50 kilometrow) z mw kilkoma-kilkunastoma
tysiacami rozmaitego latającego tałatajstwa (asteroidy, scigacze,
pociski, rakiety)

Dokladny test z sqr nie jest mi chyba defakto potrzebny
wystarczy szescienny

jak rozumiem musialbym co ramke robic trzy sorty x,y,z i trzymac
wyniki w oodzielnych tablicach indeksow - a jaki to sort? quicksort?
ktos wie w ile milisekund da rade wyrobic sie z trzema sortami
tablicy np 10000 struktur ?

wszystko trzymam w zwyklych tablicach, trzymanie tego w jakichs
drzewach skomlikowaloby kod i musialby byc czesto 'uzgadniane' bo
na tej scenie duzo sie rusza - tak ze nie wiem czy to by bylo
lepsze - zreszta nie mam z tym doswiadczenia i nie bardzo widze
jak mialoby wygladac to drzewo;

wersja z trzema quicksortami co ramke tak naprawde wyglada
na bardzo prosta (lepsza niz sektory) i dobra - o ile procek to
szybko uciagnie - pomierze to za jakis czas, tnx






--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

tj, stanelo na tym ze sprobuje jak to dziala z trzysortami
ale gdyby ktos chcial wypowiedziec sie na temat wad czy zalet
zrobienia tego przy pomocy drzew to zachecam - mz temat jest
ciekawy (a mi obcy)

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

W dniu 07.05.2011 13:44, kenobi pisze:
> jak rozumiem musialbym co ramke robic trzy sorty x,y,z i trzymac
> wyniki w oodzielnych tablicach indeksow - a jaki to sort? quicksort?
> ktos wie w ile milisekund da rade wyrobic sie z trzema sortami
> tablicy np 10000 struktur ?
Opłaca się sortować same wskaźniki - zamieniasz wtedy tylko pojedyncze
słowa procesora a nie całe struktury.

Tu masz sprawozdanie, które popełniłem z kumplem na pierwszym roku:
http://prowizorka.da.ru/~michoo/sprawozdanie.pdf
Przy okazji na końcu masz porównanie o ile udało mi się ulepszyć
heapsort kompilując go ręcznie - zajęło mi to 'tylko' ~tydzień
projektowania "przy okazji" i 3 godziny kodowania w pociągu. A
optymalizacje obejmowały m.i. testowania które zmienne i w jakiej
kolejności umieścić pod [esp], [esp+4], [esp+8].

--
Pozdrawiam
Michoo

do góry