W dniu 2011-12-06 20:47, Artur Muszyński pisze:
> W dniu 2011-12-06 20:20, M.M. pisze:
>>>> A jakby wyznaczyc dla kazdej kulki pol-prosta ruchu, potem sprawdzic w
>>>> ktorych przecieciach prostych kulki sie zdarza i ostatecznie wybrac
>>>> to zderzenie ktore nastapi najszybciej?
>>>
>>> A co bedzie jak zderzenie nastapi dokladnie w tym samym czasie?
>> Slyszalem od kogos ze to w nastrecza sporo problemow. W sumie to nie
>> wiem co oznacza "ten sam czas". Jesli uzyjemy w symulacji komputerowej
>> liczb 64-bitowych to mozemy sie nie doczekac zderzania 3 kulek w tym
>> samym
>> czasie. Moze w rzeczywistosci jeszcze nigdy nie doszlo do zdrzenia trzech
>> obiektow w tym samym czasie? Nie wiem.


Zderzenia 'trójciałowe' nie wystepują w firowej symulacji,
bo ma tam idealnie sztywne kule (a nie sprężyste).
W takim przypadku takie zderzenie jest 'miary zero' i można
je olać;)


> Jeśli kulka leci po skosie do narożnika, to zderzy się z dwiema ścianami
> jednocześnie, niezależnie od precyzji. Jeśli zderzenie będzie z kilkoma
> obiektami, to chyba wystarczy zsumować cząstkowe wektory z każdego
> zderzenia. Metodę z półprostą kiedyś zastosowałem w prototypie pinballa,
> nie było szansy, żeby kulka wyleciała za bandę :-)


Akurat zderzenie z rogiem idealnie rozkłada się na dwa zderzenia.
Gorzej np z takim przypadkiem, gdzie jedna bila naraz uderza
w dwie pod kątem. Wtedy o przebiegu zderzenia może decydować
właśnie współczynnik sprężystości.


W zabawowych symulacjach, czy nawet ciut poważniejszych,
polecałbym olać takie potrójne zderzenie jako 'nieprawdopodobne',
a ewentualne zdarzenia z tego samego momentu obliczać w kolejności
w jakiej je mamy w kontenerze.


Zresztą, dobre napisanie takiego algorytmu (symulacja n sztywnych
kul w nieważkości) poprzez odhaczanie kolejnych kolizji
jest dość ciekawym zadaniem. Ile średnio operacji musimy
zrobić na jedno zderzenie. Oczywiście chcemy zejść daleko poniżej
O(n^2), a gaz jest dość rzadki (aby nie opłacało się dzielić na regiony,
a rzeczywiście trzymać trajektorie i listę przyszłych kolizji).

Mniej niż O(n) na 'zderzenie' się chyba nie da...

pzdr
bartekltg