Jak zacząć? Zrób mapę: { zakres_współrzędnych_2d -> kontener_obiektów_w_tym_zakresie }. Przy zmianie współrzędnej obiektu sprawdź czy nie należy go przepisać do innego slotu/klucza mapy (czyli usunąć z kontenera i dodać do innego). Sprawdzenie kolizji będzie ograniczało się do sprawdzenia obecnych w kontenerze (i ew. w przypadkach położenia na krawędzi slotu, sąsiednich slotów/kluczy mapy - tego oczywiście da się także uniknąć).
Na początek może wystarczyć. Zależy jak podzielisz tę mapę, na ile slotów i jakiej wydajności będziesz oczekiwał :-)
A tu masz implementację (na dole) w pseudokodzie:
https://en.wikipedia.org/wiki/Quadtree