wyznaczanie czasu kolizji dla miliona kul

Odpowiedz Nowy wątek
2018-06-19 19:39
wil
0

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).

edytowany 1x, ostatnio: wil, 2018-06-19 19:59

Pozostało 580 znaków

2018-06-23 19:42
wil
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?

edytowany 1x, ostatnio: wil, 2018-06-23 19:58
Pokaż pozostałe 6 komentarzy
A te kulki ile mają mieć wielokątów? - Szalony Programista 2018-06-23 23:58
To są perfekcyjne kule (jak np. atomy), a akcja dzieje się w 3D, nie w płaszczyźnie. - wil 2018-06-24 00:13
Ale świat jest niedoskonały czyli jak chcesz to doskonale przedstawić? - Szalony Programista 2018-06-24 00:15
Możesz się ograniczyć do precyzji float, czyli do miliona trójkątów na kulę, ewentualnie do tryliona - double. - wil 2018-06-24 00:20
@Szalony Programista: jak najbardziej da się przeprowadzić symulacje z wykorzystaniem oraz wyrenderować niemalże idealne kule w 2D / 3D bez wykorzystania milionów wielokątów. Rzuć okiem na pierwszy-lepszy poradnik tworzenia własnego raytracera - przeważnie kule są omawiane nawet zanim się dojdzie do trójkątów, bo obliczenia na tych drugich są nieco bardziej złożone. - Patryk27 2018-06-24 01:30

Pozostało 580 znaków

2018-06-24 00:35
wil
0

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:

t = \frac{(-r\cdot v-\sqrt{(r\cdot v)^2-v^2(r^2-p^2)}}{v^2}

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.

edytowany 1x, ostatnio: wil, 2018-06-24 00:39
Btw, wydaje mi się, że znaczniki <tex>ax^2 + bx + c</tex> powinny funkcjonować poprawnie ;-) - Patryk27 2018-06-24 00:37
raczej gówniano to funkcjonuje - cienkie i niewyraźne. - wil 2018-06-24 00:43
lata temu proponowałem dorzucenie pakietu amsmath defaultowo, bez skutku. - Azarien 2018-06-24 17:28

Pozostało 580 znaków

2018-06-24 00:58
0

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.

to jest symulacja, a nie gra. a silniki są w autach - to takie coś co warczy i smrodzi... - wil 2018-06-24 01:23

Pozostało 580 znaków

2018-06-29 12:01
0

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.

Pozostało 580 znaków

2018-06-29 18:57
wil
0
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!!

edytowany 1x, ostatnio: wil, 2018-06-29 19:04

Pozostało 580 znaków

2018-06-30 10:51
0

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.

Pozostało 580 znaków

2018-06-30 22:23
wil
0

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!

edytowany 2x, ostatnio: wil, 2018-06-30 22:30

Pozostało 580 znaków

2018-07-01 00:40
0

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/Softw[...]ptional.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:
title

Pozostało 580 znaków

2018-07-01 17:28
wil
0
  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

edytowany 3x, ostatnio: wil, 2018-07-01 17:49

Pozostało 580 znaków

2018-07-01 21:01
0
  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:
screenshot-20180701203356.png
Pozostawiam bez komentarza.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0