Come verificare la collisione 2D senza controllare ogni oggetto

Question

Sono davvero ambizioso e sto lavorando a un gioco 2D Shoot 'em Up che avrà, si spera, centinaia di entità in giro.

Quello che sto avendo problemi a sistemare il mio cervello, è come il proiettile rileverà quando fa una collisione con un oggetto, senza che controlli ogni oggetto sulla mappa. Il motivo è che sento che se ho quattro dozzine di proiettili sullo schermo, ognuno controlla la collisione con ogni entità sulla mappa, ogni ciclo, vedrò una perdita di prestazioni abbastanza significativa.

Quindi quale sarebbe il modo migliore per rilevare le collisioni senza controllare ogni singola entità?

Sono in grado di gestire l'algoritmo di collisione quando ho i miei due oggetti, non riesco proprio a trovare un modo per ottenere quei due oggetti di vedersi senza prima controllare tutti gli altri.

Sto lavorando in Java e OpenGL con (presto strutturato) QUAD.

Answer 1

Si consiglia di indagare su quadtrees; sono spesso usati per una ricerca 2D efficiente.