Mamy setki lub tysiące kul w ruchu, które poruszają się z losowymi prędkościami, więc się zderzają dość często - coś jak cząstki gazu w zbiorniku.
Licząc to na piechotę należałoby wyznaczać w każdym kroku n x n = n^2 możliwych kolizji, co jest raczej nierealne dla dużych n, rzędu 1000 lub milion.
Zatem jak to zoptymalizować?
Podzielić obszar na pod-obszary i sprawdzać tylko w jego obrębie?
Tak jak już zostało wspomniane należy podzielić obszar na mniejsze obszary, bardziej ogólnym rozwiązaniem jest już wspomniany wcześniej Kd-tree, ale biorąc pod uwagę że obszar po którym poruszają się kulki jest stały znacznie lepszym pomysłem będzie zastosowanie spatial hashing. Implementuje się niesamowicie prosto w porównaniu z Kd-tree ;)
Nie będzie to dużo lepsze od bezpośredniego sprawdzania: każdego z każdym: n^2.
Zatem jak to przyspieszyć istotnie?
Przecież wystarczy wyliczyć od razu czasy wszelkich kolizji poszczególnych par - tylko raz, no i posortować to w czasie.
Potem wystarczy już tylko sprawdzać pierwszy element z listy, zamiast n x n par...
złożoność = 1, zamiast n^2. :)
Po zrealizowaniu kolizji: a z b, należy zmodyfikować listę kolizji i przesortować ponownie,
ale modyfikujemy tylko te pary z listy, które dotyczą tychże a i b, co daje złożoność 2n - w porywach!, zamiast n^2.