wyznaczanie czasu kolizji dla miliona kul

W temacie o wyznaczaniu kolizji wielu kul, wspomniałem że optymalnym rozwiązaniem byłoby (prawdopodobnie) wyznaczenie od razu listy wszystkich kolizji w zadanych warunkach początkowych.

Zatem mamy zadanie:
jak zbudować/wyznaczyć tę listę kolizji dla n kul, posortowaną wg czasu?

Lista zawiera pary ciał, plus czas ich kolizji:
n, m, t;
ponadto zakładamy, że kule są zamknięte w pudełku, zatem w przypadku braku kolizji danej kuli z inną i tak wystąpi odbicie od ściany - co też nazywamy kolizją.

W związku z tym nietrudno zauważyć, że długość tej listy będzie mieścić się w granicach od n/2 do n.

Minimum = n/2 wystąpi w przypadku braku kolizji ze ścianami, natomiast pełne n otrzymamy gdy kule odbijają się tylko od ścian zbiornika.

Dane startowe (dla wersji 2D): r_i =(x,y), v_i = (vx,vy); i = 1..n;
rozmiary i masy kul są jednakowe: promień dowolny, np. R = 1.

Zatem wynikiem działania algorytmu ma być posortowana lista zderzeń o elementach: (i,j, t),
gdzie: i, j - numery kul od 1..n, ewentualnie: j = 0 dla odbicia od ściany; t - czas (pierwszej) kolizji kuli i.

Z warunków zadania widać że: każde i, jak i j może wystąpić tylko jeden raz w liście (pomijając j=0).

I nadal nic - brak pomysłów?
Coś cieniutko tu z algorytmiką. :)

Proponuję zawody: kto najszybciej wyliczy te milion kul.

Szacunkowe liczby: przy sprawdzaniu każda z każdą, otrzymamy tu złożoność n^3, co dla miliona kul daje: 10^18, czyli procesor 1GHz wyliczy to w czasie 1e9s = miliard sekund = około 30lat.

Kto ma lepszy - szybszy sposób?

Procedura rozwiązywania kolizji jest tu nieistotna, ale podam przykład jak w praktyce można rozwiązywać.

Zakładamy że kule poruszają się prostoliniowo, czyli wg równania:
##r = r0 + vt, po prostu.

zatem biorąc dwie takie kule mamy dwie proste:
##r1 = r01 + v1t oraz r2 = r02 + v2t

z tego musimy wyznaczyć zderzenie, czyli moment gdy odległość wynosi: suma promieni obu kul = p.

Odległość pomiędzy tymi kulami idzie tak:

d = |r1 - r2| = |r+vt|

gdzie: r = r01 - r02, oraz v = v1-v2

zatem warunek zderzenia można zapisać w taki sposób:
d(t) = (r+vt)^2 = p^2

i z tego chcemy wyliczyć czas zderzenia t.
Jest to równanie kwadratowe, więc dość skomplikowane - czasochłonne,
więc zamiast od razu to wyliczać, i tracić czas,
może lepiej najpierw sprawdzić czy te kule w ogóle się zderzą?

Aby się zderzyły muszą się zbliżać do siebie... zatem pochodna z odległości?

d' = 2(r+vt)v < 0, ale t = 0, więc pozostaje nam:
r.v < 0 -> to jest warunek wystąpienia zderzenia w przyszłości;
dla r.v > 0 zderzenia w ogóle nie będzie, bo kule się oddalają.

zatem wystarczy takie coś wyliczyć...
i dopiero gdy jest to spełnione, wtedy rozwiązujemy równanie:

(r+vt)^2 = p^2
v^2t^2 + 2rvt + (r^2-p^2) = 0;

delta = 4(rv)^2 - 4v^2(r^2-p^2) = 4((r.v)^2 - v^2(r^2-p^2))

stąd czas kolizji:

wiemy że r.v < 0, więc taki jest najbliższy czas, w przypadku: +sqrt... byłoby to później, więc to nas nie interesuje.

Przed pierwiastkowaniem należy sprawdzać: delta >= 0.
w przypadku delta < 0 - kule nie zderzą się wcale, jedynie przelatują obok siebie w odl. >= p.

Napiszą tę grę, z twoim algorytmem.
Użyj silnika bo chodzi tu o algorytm, koła zrób kwadratowe jak wolisz i pokaż reszcie co miałeś na myśli.

Do tego już są algorytmy jak R-tree, oct-tree itd, jeżeli dobrze podzielisz przestrzeń np na 5000 nodów to w przypadku idealnego balansu będziesz miał 5000 nodów, a w każdym po 200 kul.
Oznacza to że dla każdej przestrzeni liczysz kolizję osobno czyli kombinacja 200 po 2 = 19900, przestrzeni masz 5000 co daje 10^8 możliwości.
Przestrzeń nie musi być statycznie dzielona, wydajność zależy od tego jak szybko jesteś w stanie dzielić przestrzeń i ją modyfikować tak żeby zawsze była jak najlepiej zbalansowana.

xxx_xx_x napisał(a):

Do tego już są algorytmy jak R-tree, oct-tree itd, jeżeli dobrze podzielisz przestrzeń np na 5000 nodów to w przypadku idealnego balansu będziesz miał 5000 nodów, a w każdym po 200 kul.
Oznacza to że dla każdej przestrzeni liczysz kolizję osobno czyli kombinacja 200 po 2 = 19900, przestrzeni masz 5000 co daje 10^8 możliwości.
Przestrzeń nie musi być statycznie dzielona, wydajność zależy od tego jak szybko jesteś w stanie dzielić przestrzeń i ją modyfikować tak żeby zawsze była jak najlepiej zbalansowana.

Pewnie tak można to zredukować istotnie..
niemniej pozostaje problem przelotu kul pomiędzy obszarami, a i jeszcze gorzej może się zdarzyć!:

wyliczasz kolizje w ograniczonym obszarze, i otrzymujesz tam czas pierwszej kolizji k-tej kuli np. t = 1s;

tylko że kula z sąsiedniego obszaru zderzy się tu wcześniej - szybciej, bo np. po czasie: t = 0.5s.
a nawet nie musi być z sąsiedniego obszaru, lecz z dowolnego: odległa, ale szybka kula = siedem komórek obok, uderza już po 0.4s!!

Chyba trochę za dużo teoretyzujesz. Zawsze lepiej zaczynać od małych kroków. Zrób sobie przykład z 10, 100 a później 1000 kul. Później będziesz to optymalizował. Od momentu powstania wątku jakbyś coś zaprogramował to miałbyś już wersję podstawową i z 10 poprawek. Wracając do meritum.

Szacunkowe liczby: przy sprawdzaniu każda z każdą, otrzymamy tu złożoność n^3, co dla miliona kul daje: 10^18, czyli procesor 1GHz wyliczy to w czasie 1e9s = miliard sekund = około 30lat.

Jak masz zderzenie kuli A z kulą B to nie musisz już sprawdzać zderzenia B z kulą A (licząc 'na piechotę', gdzie dobierasz zderzenia). Szacowanie czasu jest wg. mnie przewymiarowane.
Kolejna sprawa to typ zderzenia. Uwzględniasz zderzenia sprężyste, nie sprężyste? Chyba nie widziałem żebyś o tym pisał. Jeśli kule ulegną zderzeniu to zmieni się ich trajektoria, prędkość. Co wtedy jeśli wyliczasz, że kula A zderzy się z B i C, a po zderzeniu z B zmieni kierunek i do zderzenia z C nie dojdzie. Jeśli dobrze zrozumiałem to liczysz tylko pierwsze zderzenia, a co potem? Kule ulegające zderzeniu nie są już brane pod uwagę? Rozważasz co się stanie jeśli rozpatrujesz zderzenie kul a inna kula o większej prędkości pierwsza dokona zderzenia. Jaki jest współczynnik wypełnienia tego pudełka kulami? Przy milionie kul chcesz rozpatrywać pojedyncze zderzenia i później sprawdzać czy inne zderzenie nie będzie miało miejsca wcześniej? Taki sposób wyliczania czasu zderzenia jest wg. mnie delikatnie mówią bez sensu ze względu na złożoność problemu.

Pisałeś coś wcześniej o 'symulacji' ale ja tu żadnej symulacji nie widzę. Zrób tak jak chcesz czyli zasymuluj. Po pierwsze obliczenia rób na macierzach. Liczenie problemu tego wymiary na równaniach to samobójstwo. Zasymuluj te kule czyli obliczaj położenie po czasie. Sprawdź maksymalną prędkość kul i dobierz odpowiednie delta t. Dla takiej delty wylicz nowe położenie kul. Jeśli zderzenie to modyfikacja wektora ruchu, zapis na listę czasu zderzenie i dalsze obliczenia. Liczysz w pętli dopóki lista (bez powtórzeń) nie będzie równa ilości kul.

Pracuję na co dzień ze sporymi macierzami i wiem co mówię. Obliczenia iteracyjne (kilkaset iteracji) trwają około minuty. W przypadku Twojego wymiaru problemu obliczenia trwałyby maksymalnie godziny a pewnie dużo krócej (wszystko zależy od ilości wolnej przestrzeni, prędkości kul, początkowego położenia no i użytej metody rozwiązania takiej macierzy). W profesjonalnych pakietach typu ANSYS ludzie codziennie symulują ruch płynów składających się z milionów cząsteczek, gdzie ruch każdej cząsteczki uwzględnia odbicia, tarcia itp. a na obliczenia nie czeka się latami.

Ten temat jest kontynuacją poprzedniego, w którym podałem metodę optymalnej symulacji dużej liczby kul.

Schemat wygląda tak:

A. na starcie generujesz posortowaną listę najbliższych kolizji dla każdej z n kuli.
Długość tej listy wynosi n - co najwyżej.

i o to w tym temacie pytam - jak wygenerować tę listę kolizji!

B. dalszy ciąg symulacji jest teraz uproszczony - do rzędu n zaledwie;
ponieważ mając już posortowaną (po czasie) listę kolizji, wystarczy sprawdzać tylko jedną kulę - pierwszą z listy, a nie aż całe ~n^2 możliwych kolizji, co dla n =milion byłoby nierealne!

C. po stwierdzeniu kolizji, wyznaczamy nowe prędkości dla pary kul (ewentualnie tylko jednej - odbicie od ściany), a następnie wyznaczamy nową kolizję dla tych dwóch kul, co kosztuje zaledwie 2n operacji, a nie n^2! Modyfikujemy listę odpowiednio i wracamy do B.

Szacowany czas budowania takiej listy kolizji wynosi n^3:

1. szukamy najbliższej kolizji dowolnej pary kul, co kosztuje n(n-1) operacji
2. szukamy drugiej kolizji, co kosztuje (n-1)(n-2) operacji
   ...

razem: n(n-1) + (n-1)(n-2) + ... 1 =~ n^3
dokładniej będzie to n^3/3, czyli rząd n^3 tak czy siak!

A - do tego musisz właśnie wyznaczyć iteracyjnie położenie kul w kolejnych chwilach czasowych.
B - jeśli tworzysz listę kolizji to i tak ta lista będzie generowana na podstawie ~n^2 możliwych kolizji, chyba że pomijasz prędkość kul i rozpatrujesz możliwość kolizji tylko na podstawie odległości (czyli uproszczenie)
C - no i doszła kwestia odbicia od ściany, gdzie w A rozpatrujesz odbicie od ściany? Kolizje kul możesz przewidzieć bo znasz ich położenie. A co ze ścianą? Rozpatrujesz jeden punkt na przecięciu prostej wyznaczonej przez kierunek czy ściana to nieskończony zbiór 'nieruchomych kul' i szukać odbicia po najmniejszej odległości?

Zobacz jak robi się symulację zderzenia w profesjonalnych pakietach:
https://www.sharcnet.ca/Software/Ansys/16.2.3/en-us/help/flu_ug/flu_ug_sec_discrete_optional.html#flu_ug_dem_usage
Symulacja po czasie... a nie rozpatrywanie zderzeń w sposób jaki opisałeś.

Pisałem o szacowaniu czasu a nie wymiarze problemu. Jeśli podchodzisz do rozwiązania za pomocą pojedynczych równań to może i wyjdzie 30 lat. Obecnie takie rzeczy liczy się na macierzach. Nie znalazłem niczego lepszego ale porównanie wydajności obliczeń przedstawi się mniej więcej tak jak na obrazku:

1. Metodę detekcji kolizji podałem wcześniej: rozwiązujesz tylko równanie kwadratowe, i do tego dopiero po sprawdzeniu dwóch warunków: v.r < 0, oraz delta > 0, co pozwoli odrzucić z 90% przypadków, albo i więcej.
2. odbicia od ściany wyliczamy zwyczajnie: kula jest w sferze, albo w sześcianie, więc wyliczam czas dojścia do ściany, co wstawiam zwyczajnie do listy potencjalnych kolizji.
3. profesjonalne pakiety są gorsze od opisanej tu metody, bo... to jest optymalna metoda - najszybsza i najdokładniejsza ze znanych metod, opisanych w literaturze fachowej. :)

Jest tu problem jedynie z wyliczeniem tej listy kolizji na starcie, choć to i tak zajmie góra: nlog(n), czyli dla miliona wyjdzie około 20 milionów zaledwie, co jest akceptowalne - z sekunda obliczeń na procesorze 1GHz.

https://ieeexplore.ieee.org/document/4722183/?part=1

1. profesjonalne pakiety są gorsze od opisanej tu metody, bo... to jest optymalna metoda - najszybsza i najdokładniejsza ze znanych metod, opisanych w literaturze fachowej. :)

Śmiałe stwierdzenie. Jeśli to na podstawie tego artykułu z linka to będę mógł się odnieść jutro, obecnie nie mam dostępu.

Przedstawie tylko jeden (z wielu) jaskrawy teoretyczny przypadek, który przy takiej ilości kul wystąpi, z powodu interakcji pomiędzy kulami:

Pozostawiam bez komentarza.

Nie wiem co mają reprezentować te ilustracje.

Przy liczeniu najbliższej kolizji dla każdej kuli, nie ma znaczenia że później dana kolizja nie dojdzie do skutku - z powodu wcześniejszych kolizji.

W liście kolizji jedynie ta pierwsza - najwcześniejsza jest pewna, a pozostałe są jedynie potencjalne - ostateczne z możliwych.

Każda (zrealizowana) kolizja modyfikuje tę listę kolizji!

Przykład listy kolizji: 1-2, 3-4, 5-6, 7-8, ...

i po zrealizowaniu kolizji 1-2, może się okazać, że teraz kula 1 zderzy się z 3 wcześniej niż 3 z 4,
tym samym kolizja 3-4 będzie usunięta z listy, natomiast wstawiona nowa: 1-3;

W tym momencie mamy problem: kula 4 nie ma teraz pary - najbliższej kolizji!
Zatem należy to wyliczyć od nowa - najbliższą kolizję dla 4.
...

tylko że my już wyznaczyliśmy kolizję 3-4 jako najbliższą dla 4,
więc to przeliczenie dla 4 jest tu chyba zupełnie zbyteczne, ponieważ: 4 z 1 i 2 będzie i tak obliczane - po kolizji 1 z 2;
natomiast pozostałe kombinacje z czwórką: 4-5, 4-6, ..., były przecież już liczone wcześniej, więc tam nic się nie zmieni.

zatem 4 nie będzie w ogóle w liście kolizji... chyba że w parze ze ścianą - asekuracyjnie.

W przesłanym artykule trochę dokładniej jest opisane to co przedstawiasz. Niemniej dalej jest to zależne od czasu:

1. Find the latest event in the queue, suppose that
   the event’s occurring time is t, the system moves
   forwards time t and update the system state. Since we
   assure that no other event occurs before t, the system’s
   moving forward to time t means that all the spheres
   move forward along their current ballistic trajectories
   for t-t0 where t0 is the current time of the system.
   Computing the new positions of all the spheres needs
   O(n) time.

Tylko ja sugerowałem stały krok czasowy a tu jest zmienny dla wystąpienia zderzenia. Z Twoich wypowiedzi nie wywnioskowałem, że zmieniasz coś po czasie a jedynie czas jest wynikiem obliczeń.

Mój rysunek donosi się mniej więcej do tego:

C. po stwierdzeniu kolizji, wyznaczamy nowe prędkości dla pary kul (ewentualnie tylko jednej - odbicie od ściany), a następnie wyznaczamy nową kolizję dla tych dwóch kul, co kosztuje zaledwie 2n operacji, a nie n^2! Modyfikujemy listę odpowiednio i wracamy do B.

Tak jak masz w artykule nie modyfikujesz jedynie kolizji tych dwóch kul ale również tych, które mogą mięć kolizję z nowo wyznaczonymi.
Przykład: A ma kolizję z B. Wg. tego co piszesz to sprawdzasz nowe kolizje dla A i B. Nie bierzesz jednak pod uwagę, że jeśli A jest teraz w kolizji z C to musisz jeszcze raz sprawdzać kolizję dla C, nie wiesz czy wcześniejsza kolizja z listy będzie tą pierwszą czy jednak obecna z A.

to jest optymalna metoda - najszybsza i najdokładniejsza ze znanych metod, opisanych w literaturze fachowej. :)

Metoda ma swoje plusy ale bez jakichkolwiek porównań nie postawiłbym takiego stwierdzenia. W artykule jest tylko 5 referencji w tym jedynie jednak stricte związana z problematyką zderzeń.

Dodatkowo mamy tutaj 'niewielką' próbę 4000 cząstek do zderzeń. Stwierdzenie:

From fig. 6, we can see that the process time for a
single collision is almost linearly proportional to the
total number of the spheres.

jest tutaj pewnym uproszczeniem. Na podstawie tych kilku punktów można wyznaczyć wielomian interpolacyjny

który dla 1mln kul da czas obliczeń dla pojedynczej kolizji na poziomie 16,7mln ms czyli ok 4,5h! A Ty chcesz wyznaczyć kolizje dla wszystkich miliona kul... czyli jakieś pół roku :)

Nie wiem skąd taki fantastyczny wielomian wytrzasnąłeś, który sugeruje złożoność n^3.

Modyfikacja listy kolizji ma raptem rząd: n operacji;
w praktyce wyjdzie może być nawet i nlog(n), co i tak jest o niebo mniejsze od n^3.
nlogn / n^3 = logn / n^2, co dla n = milion daje: 20 / bilion = 2e-11;
zatem z tego twojego szacowanego czasu: 4.5 godz. zostanie mniej od... 1us. :)

Ten jak to określasz, fantastyczny wielomian jest wynikiem interpolacji wyników z artykułu na który się powołujesz. Do jego wyznaczenia wykorzystałem 4 punkty i użyłem aproksymacji za pomocą wielomianu Lagrange'a. Przykro mi ale ja równania interpolacyjnego nie wymyślałem. Nie moja wina, że przy 4 punktach wyszedł wielomian stopnia 3. Całe szczęści, że nie wykorzystałem wszystkich punktów z wykresu... (niestety dla niewielkiej liczby cząstek trudno odczytać czas z wykresu). Żeby nie było, że coś ściemniam to wstawiam rzeczony wykres z artykułu oraz punktu na podstawie których to wyznaczałem.

ID | n | t (ms)
---------------- | -------------------
1| 1000 | 1,6
2 | 2000 | 3.8
3 | 3000 | 6.3
4 | 4000 | 9.2

Jeśli zarzucasz mi jakiś błąd to chętnie dowiem się gdzie go popełniłem. Nie wykluczam, że gdzieś błąd może być. Moje obiektywne wyznaczeni punktów na wykresie może nie był precyzyjne ale nawet jeśli założymy duże uproszczenie -> 1000 cząstek = 2ms, 2000 = 4ms (chociaż wychodzi mniej niż 2ms i 4ms) to dla 4000 powinno wyjść 8 (a jest ponad 9...), a dla miliona cząstek wyjdzie czas 1s. Nie wiem skąd wyszła ta 1µs skoro 3 rzędy mniejszy problem jest liczony w ms i są to wyniki obliczeń a nie teoretyczne rozważania. Pragnę zauważyć, że dane zostały przedstawione dla zegara 2,66GHz (autorzy najwyraźniej walnęli się w opisie jednostki bo P4 nie ma taktowania w MHz), podczas gdzie Ty sugerowałeś to dla zegara 1GHz.
Widzę, że znasz się na algorytmice, podajesz bardzo ładne wzory jednak wszystko to jest teoretyczne. Moje szacowania są natomiast wynikiem interpretacji faktycznych danych (zakładając, że autorzy nie wyciągnęli ich z palca).
Jeśli twierdzisz, że jesteś w stanie osiągnąć sugerowane wyniki to trochę tak jakbyś podważał wyniki z artykułu. Sam do końca nie wiesz jak "optymalnie" tworzyć tą listę kolizji, inaczej nie tworzyłbyś tego wątku. Może jednak jest coś co wpływa na wydłużenie tego czasu.
Ja raczej więcej nie doradzę. Szczerze życzę Ci żeby udało się wykonać te obliczenia z zakładanym czasem, byłby niezły materiał na artykuł biorąc pod uwagę stopień przyspieszenia w porównaniu do artykułu. Fajnie jakbyś podzielił się później wynikami, po zainteresowaniu wątkiem kilka osób pewnie byłoby ciekawych rezultatów.

PS. Jak już rozpracujesz ten algorytm to i tak trzeba by było to porównać z jakimś nie optymalnym rozwiązaniem (pod względem czasowy). Inaczej to co wyjdzie będzie jedynie jakimś wynikiem, bez możliwości potwierdzenia czy wyszło to co miało wyjść.