-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!newsfeed.neostrada.pl!unt-exc-02.news.neostrada.pl!unt-spo-b-01.news.n
eostrada.pl!news.neostrada.pl.POSTED!not-for-mail
Content-Type: text/plain; charset=iso-8859-2; format=flowed; delsp=yes
Newsgroups: pl.comp.programming
Subject: Re: petla kolizji -> spacjala kolizyjna
References: <jbr1h1$t2g$1@inews.gazeta.pl>
Date: Thu, 08 Dec 2011 21:31:09 +0100
MIME-Version: 1.0
Content-Transfer-Encoding: Quoted-Printable
From: "Jordan Szubert" <u...@j...us.to>
Organization: HELL inc.
Message-ID: <o...@a...home>
User-Agent: Opera Mail/11.52 (Win32)
Lines: 119
NNTP-Posting-Host: 83.26.234.56
X-Trace: 1323376273 unt-rea-a-02.news.neostrada.pl 5819 83.26.234.56:29161
X-Complaints-To: a...@n...neostrada.pl
Xref: news-archive.icm.edu.pl pl.comp.programming:193980
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 08.12.11 21:05 M.M.
- 08.12.11 21:27
- 08.12.11 21:46
- 08.12.11 21:57
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-12 Warszawa => PC Hardware Expert / Specjalista PC <=
- 2025-07-12 Warszawa => Account Manager - Usługi rekrutacyjne <=
- 2025-07-12 Warszawa => Administrator IT <=
- 2025-07-12 Warszawa => IT Administrator <=
- 2025-07-12 Warszawa => Asystent/tka ds. Administracji <=
- 2025-07-12 Warszawa => Specjalista/stka ds. Organizacji <=
- 2025-07-12 Warszawa => MENA New Business Manager <=
- 2025-07-12 Gdynia => Controlling systems Consultant <=
- 2025-07-12 Warszawa => Developer Microsoft Dynamics 365 Finance & Operations (D36
- 2025-07-12 Warszawa => Programista Microsoft Dynamics 365 Finance & Operations (D
- 2025-07-12 Warszawa => Dyrektor IT <=
- 2025-07-12 Warszawa => IT Director <=
- 2025-07-12 Czy wypowiedź Kaczyńskiego o Braunie jest skarżalna? ["działa z OBCEJ inspiracji"]
- 2025-07-11 Rejestrator temperatur - termopara, siec
- 2025-07-11 DPD, przeniesienie numerów z a2mobile i z Orange