Cómo verificar la colisión 2D sin verificar cada objeto

Question

Estoy siendo realmente ambicioso y estoy trabajando en un juego 2D Shoot 'em Up que tendrá, con suerte, cientos de entidades corriendo.

Lo que estoy teniendo problemas para ajustar mi cerebro, es cómo detectará la bala cuando hace una colisión con un objeto, sin que compruebe cada objeto en el mapa. La razón es que creo que si tengo cuatro docenas de balas en la pantalla, cada una de las cuales verifica la colisión con cada entidad en el mapa, cada ciclo, veré una pérdida de rendimiento bastante significativa.

Entonces, ¿cuál sería la mejor forma de detectar colisiones sin consultar todas las entidades?

Puedo manejar el algoritmo de colisión cuando tengo mis dos objetos, parece que no encuentro la forma de hacer que esos dos objetos se vean entre sí sin consultar a todos los demás primero.

Estoy trabajando en Java y OpenGL con QUADS (que pronto se texturizarán).

Answer 1

Debe investigar quadtrees; a menudo se usan para búsquedas 2D eficientes.