Wykrywanie kolizji na dużą skalę

Witam,

Mam do was pytanie czysto związane z wydajnością komputera, bo jak wiadomo szybkość w dużej mierze zależy od algorytmu, w każdym razie stoję przed takim problemem.

Otóż powiedzmy że mam kwadrat, w którym zastosowałem wykrywanie kolizji np AABB

jak na filmie (https://www.youtube.com/watch?v=He9bYK87Oqw)

Wszystko wydaje się proste 4 ify sprawdzające w pętli dla każdego prostokąta czy nie zaszła kolizja.

Piszę podobny program sieciowy w którym jest ok tysiąca takich prostokątów, które w dodatku się poruszają i trzeba nie dość, że co pętle pobrać pozycję każdego prostokąta z serwera, to jeszcze w pętli sprawdzić czy któryś przypadkiem nie "kolidował" z innym. Jak sami pewnie zauważyliście jest to straszenie nieefektywne.

Wiem np w grach 3D renderowany jest tylko obraz na który gracz ma ustawioną w danej chwili kamerę więc. Stąd rodzi się pytanie jak takie coś zaimplementować w grafice 2D, oraz czy istnieją jakieś inne sposoby radzenia sobie w sytuacji takiej żeby co obrót pętli gry nie trzeba było robić sprawdzać 1000 kolizji, innymi słowy inne sposoby na wykrywanie kolizji.

Jak np to jest zastosowane w sandboxach? Czy w Minecraft powiedzmy program sprawdza czy gracz nie stoi na jednym z miliona klocków co obrót pętli?
Wydaje się być to wręcz niemożliwe.

 

Pozdrawiam

W szczególności polecam ostatnie hasło i pierwszy link.