optymalizacja systemu kolizji

witam ostatnio siedze sobie nad takim programikiem ktory to ma wlasny system kolizji i system ruchu fizycznego. Wszystko robilem od podstaw i jestem z niego bardzo zadowolony. Problem w tym ze program niestety ale wydajnoscia nie grzeszy :(

Ogolnie cala sprawa polega na tym ze mozna dodawac na plansze pileczki i to sa oddzielne obiekty. Kazda pileczka ma wskaznik na tablice wskaznikow zawierajaca liste tych pileczek. Operuje na wskaznikach zeby bylo o wiele szybciej itp ale mimo wszystko to nie jest najtrudniejsze. Jesli stworzymy 4 pileczki to ilosc "prob kolizji" wynosi (4-1)*4/2 czyli (n-1)*n/2 dla n-pileczek. Latwo sie domyslic ze dla 1000 pileczek ilosc prob bedzie wynosila okolo 500000 co jest niedopuszczalne dla procesora. Dodam ze kazda pileczka posiada swoje wlasne wspolrzedne ktore poczatkowo chcialem wykorzystac do rozbicia ich na mniejsze "bloki" zeby pomijac te pilki ktore sa absurdalnie daleko zeby wykonywac obliczenia z nimi.

Zeby przyblizyc zapodam linka (od razu widac jak zwalnia caly silnik fizyczny przy wiekszej ilosci pileczek http://www.netgods.xt.pl/project1.rar

Mam nadzieje ze ktos mi <ort>wskarze </ort>jakies sensowne rozwiazanie tego problemu (albo potwierdzi rozbicie obiektow do mniejszych kontenerow opartych o ich wspolrzedne)

Pozdro...

Możesz podzielić obszar na pola o rozmiarze nieco większym od piłeczki (2-3x). Wtedy kolizje sprawdzasz tylko dla 9 takich kwadratów na raz (środkowy i 8 na około), co znacznie ograniczy ilość obliczeń kolizji dla poszczególnych kulek.

Tak myslalem o tym zeby w ten sposob podzielic obszar i po prostu przekazywac pileczki z jednego "kwadratu" do drugiego ale zastanawialem sie tez co z tymi wiekszymi obiektami. W programie nie mam limitu wielkosci na obiekt (nie bedzie) wiec jak zrobic zeby taki duzy obiekt nalezal do wielu kwadratow na raz? Troche zagmatwalem ale prosciej chyba nie umiem wyjasnic

Masz lokalizację obiektu, masz jego promień. Sprawdzasz czy promień nie jest większy od odległości do dowolnego wierzchołka aktualnego obszaru szukania, jak tak, to dodajesz wskaźnik na tenże obiekt do wszystkich kwadratów sąsiadujących z tym wierzchołkiem (i ew powiększasz obszar o następną otoczkę i sprawdzasz dalej).

Sprawdzanie lokacji (tj kwadrat/y z przypisanym wskaźnikiem ) i jej otoczki pozwoli Ci ominąć konieczność sprawdzania przecięcia z krawędziami.

Ok wielkie dzieki w sumie podsunales mi dobra mysl. Jeszcze tylko posiedze nad tym zeby doszlifowac do perfekcji i powinno byc git :)

Jakby ktos znalazl lepszy sposob to tez niech napisze bo moge wprowadzic oczywiscie 2 metody do obliczania kolizji ktore by byly wykorzystywane w najoptymalniejszych przypadkach. Wiadomo ze nie oplaca sie przeszukiwac wszystkich "kwadratow" w przypadku 3 obiektow nachodzacych kazdy na 100 kwadratow :) pozdro...

http://pl.wikipedia.org/wiki/Drzewa_ósemkowe ?
Tak to się zazwyczaj robi. ;)

Owszem, gdy przeważają statyczne obiekty. W tym przypadku to drzewo trzeba by było generować co cykl.

BTW tu akurat to raczej drzewo czwórkowe byłoby bardziej na miejscu. ;)